We study a shoe made from \(D\) decks. Each deck contains \(S \cdot R\) ordinary cards and \(J\) jokers. An ordinary card carries three labels: its deck, its suit, and its rank. A joker contributes only to its deck label, not to any suit or rank. After a uniform random shuffle, cards are revealed from the top until every required deck, every required suit, and every required rank has appeared at least once.
For the Project Euler instance,
$$D=10,\qquad S=4,\qquad R=13,\qquad J=2,$$
so the shoe contains
$$M=D(SR+J)=10(4\cdot 13+2)=540$$
cards in total. The task is to compute the expected stopping time exactly enough to print eight decimal places.
The implementations evaluate a closed inclusion-exclusion formula. The key is to count, for each family of still-missing categories, how many cards are allowed to appear before that family is broken.
Let \(T\) be the draw index at which all required categories have been seen for the first time. Because no more than \(M\) cards can be drawn, the tail-sum identity gives
$$\mathbb E[T]=\sum_{n=0}^{M-1}\Pr(T>n).$$
So we only need a formula for the probability that after \(n\) draws at least one required deck, suit, or rank is still missing.
Fix three sets of missing categories: \(s\) suits, \(r\) ranks, and \(d\) decks. There are
$$\binom{S}{s}\binom{R}{r}\binom{D}{d}$$
ways to choose them.
If those categories are all still unseen after \(n\) draws, then every revealed card must avoid the missing sets. Only the remaining \(D-d\) decks may appear. Inside such a deck, an ordinary card is allowed only if its suit lies among the \(S-s\) allowed suits and its rank lies among the \(R-r\) allowed ranks. Jokers in the surviving decks are always allowed, because they carry no suit or rank label. Therefore the number of allowed cards is
$$A(s,r,d)=(D-d)\bigl((S-s)(R-r)+J\bigr).$$
The complementary number of forbidden cards is
$$B(s,r,d)=M-A(s,r,d).$$
After a random shuffle, the first \(n\) cards form a uniformly random \(n\)-subset of the whole shoe. Hence, for fixed missing sets, the probability that all first \(n\) cards lie among the \(A(s,r,d)\) allowed cards is
$$\frac{\binom{A(s,r,d)}{n}}{\binom{M}{n}},$$
with the understanding that the expression is \(0\) when \(n>A(s,r,d)\).
Now apply inclusion-exclusion over all nonempty choices of missing suits, ranks, and decks:
$$\Pr(T>n)=\sum_{\substack{0\le s\le S\\0\le r\le R\\0\le d\le D\\s+r+d>0}}(-1)^{s+r+d+1}\binom{S}{s}\binom{R}{r}\binom{D}{d}\frac{\binom{A(s,r,d)}{n}}{\binom{M}{n}}.$$
The sign is positive when an odd number of category families is declared missing and negative when it is even.
Insert the previous formula into the tail-sum expression for \(\mathbb E[T]\) and exchange the order of summation:
$$\mathbb E[T]=\sum_{\substack{0\le s\le S\\0\le r\le R\\0\le d\le D\\s+r+d>0}}(-1)^{s+r+d+1}\binom{S}{s}\binom{R}{r}\binom{D}{d}\sum_{n=0}^{A(s,r,d)}\frac{\binom{A(s,r,d)}{n}}{\binom{M}{n}}.$$
The inner sum is classical. If \(B=M-A\) cards are marked as forbidden, then in a random permutation the expected position of the first marked card is
$$\frac{M+1}{B+1}.$$
The same quantity is equal to
$$\sum_{n=0}^{A}\frac{\binom{A}{n}}{\binom{M}{n}}=\frac{M+1}{M-A+1}=\frac{M+1}{B+1}.$$
So each inclusion-exclusion term collapses to a single rational factor.
Substituting \(B(s,r,d)=M-(D-d)\bigl((S-s)(R-r)+J\bigr)\), we obtain
$$\boxed{\mathbb E[T]=\sum_{\substack{0\le s\le S\\0\le r\le R\\0\le d\le D\\s+r+d>0}}(-1)^{s+r+d+1}\binom{S}{s}\binom{R}{r}\binom{D}{d}\frac{M+1}{B(s,r,d)+1}.}$$
This is exactly the quantity evaluated by the implementations. The formula also handles reduced variants: if suits, ranks, or decks are not required, the corresponding summation range collapses to the single value \(0\).
One implementation checks the simpler case \(D=1\), \(S=4\), \(R=13\), \(J=2\), where only the \(13\) ranks matter. Then
$$M=1(4\cdot 13+2)=54.$$
There is no summation over suits or decks, so only \(r\) remains. For a chosen set of \(r\) missing ranks, the allowed cards are
$$A(r)=4(13-r)+2=54-4r,$$
hence the forbidden cards are
$$B(r)=54-(54-4r)=4r.$$
The expectation becomes
$$\mathbb E[T]=\sum_{r=1}^{13}(-1)^{r+1}\binom{13}{r}\frac{55}{4r+1}.$$
Evaluating the sum gives
$$\mathbb E[T]\approx 29.05361725,$$
which matches the numerical checkpoint used by the implementation.
The C++, Python, and Java implementations all evaluate the closed form directly. They first compute the total shoe size \(M\), then iterate over the possible counts of missing suits, missing ranks, and missing decks. For each triple \((s,r,d)\), they compute the binomial multiplicity, the parity sign from \(s+r+d\), the allowed-card count \(A(s,r,d)\), and the forbidden-card count \(B(s,r,d)\), then add the signed contribution
$$\binom{S}{s}\binom{R}{r}\binom{D}{d}\frac{M+1}{B(s,r,d)+1}.$$
The same framework also handles reduced modes by fixing a disabled category count to \(0\). The C++ implementation adds two sanity checks before printing the final answer: the rank-only checkpoint above, and a tiny shoe with \(D=S=R=2\) and \(J=0\), where the closed formula is compared against an exact exhaustive expectation.
Let \(S_0\), \(R_0\), and \(D_0\) denote the active category sizes: each is either the full size or \(0\), depending on whether that category type is required. The closed-form evaluation uses
$$O\bigl((S_0+1)(R_0+1)(D_0+1)\bigr)$$
signed terms and \(O(1)\) memory. The implementations compute binomial coefficients with short multiplicative products, so there is only a tiny extra factor linear in the category size. For the actual Project Euler parameters, the full computation visits just
$$ (4+1)(13+1)(10+1)=770 $$
terms, which is easily fast enough.
Wir betrachten einen Schuh aus \(D\) Kartendecks. Jedes Deck enthält \(S \cdot R\) gewöhnliche Karten und \(J\) Joker. Eine gewöhnliche Karte trägt drei Merkmale: Deck, Farbe und Rang. Ein Joker trägt nur sein Deck, aber weder Farbe noch Rang. Nach einer gleichverteilten Zufallspermutation werden Karten von oben aufgedeckt, bis jedes geforderte Deck, jede geforderte Farbe und jeder geforderte Rang mindestens einmal erschienen ist.
Für die konkrete Project-Euler-Instanz gilt
$$D=10,\qquad S=4,\qquad R=13,\qquad J=2,$$
also insgesamt
$$M=D(SR+J)=10(4\cdot 13+2)=540$$
Karten. Gesucht ist der Erwartungswert dieses Stoppzeitpunkts mit genügend Genauigkeit für acht Nachkommastellen.
Die Implementierungen werten eine geschlossene Inklusions-Exklusions-Formel aus. Zentral ist die Frage, wie viele Karten erscheinen dürfen, solange bestimmte Kategorien noch vollständig fehlen.
Sei \(T\) die Ziehnummer, bei der zum ersten Mal alle geforderten Kategorien gesehen wurden. Da höchstens \(M\) Karten gezogen werden können, liefert die Schwanzsummenformel
$$\mathbb E[T]=\sum_{n=0}^{M-1}\Pr(T>n).$$
Wir brauchen also eine Formel für die Wahrscheinlichkeit, dass nach \(n\) Ziehungen mindestens ein gefordertes Deck, eine geforderte Farbe oder ein geforderter Rang noch fehlt.
Fixiere Mengen fehlender Kategorien: \(s\) Farben, \(r\) Ränge und \(d\) Decks. Diese Auswahl kann auf
$$\binom{S}{s}\binom{R}{r}\binom{D}{d}$$
Arten getroffen werden.
Sollen diese Kategorien nach \(n\) Ziehungen noch unsichtbar sein, dann müssen alle gezogenen Karten sie vermeiden. Es dürfen also nur Karten aus den verbleibenden \(D-d\) Decks erscheinen. Innerhalb eines solchen Decks ist eine gewöhnliche Karte nur dann erlaubt, wenn ihre Farbe zu den \(S-s\) erlaubten Farben und ihr Rang zu den \(R-r\) erlaubten Rängen gehört. Die Joker der verbleibenden Decks sind immer erlaubt, weil sie weder Farbe noch Rang tragen. Damit ist die Zahl der erlaubten Karten
$$A(s,r,d)=(D-d)\bigl((S-s)(R-r)+J\bigr).$$
Die Zahl der verbotenen Karten ist das Komplement
$$B(s,r,d)=M-A(s,r,d).$$
Nach einer zufälligen Permutation bilden die ersten \(n\) Karten eine gleichverteilte \(n\)-Teilmenge des gesamten Schuhs. Daher ist für feste fehlende Mengen die Wahrscheinlichkeit, dass alle ersten \(n\) Karten unter den \(A(s,r,d)\) erlaubten Karten liegen, gleich
$$\frac{\binom{A(s,r,d)}{n}}{\binom{M}{n}},$$
wobei der Ausdruck als \(0\) verstanden wird, falls \(n>A(s,r,d)\).
Mit Inklusion-Exklusion über alle nichtleeren Wahlen fehlender Farben, Ränge und Decks ergibt sich
$$\Pr(T>n)=\sum_{\substack{0\le s\le S\\0\le r\le R\\0\le d\le D\\s+r+d>0}}(-1)^{s+r+d+1}\binom{S}{s}\binom{R}{r}\binom{D}{d}\frac{\binom{A(s,r,d)}{n}}{\binom{M}{n}}.$$
Das Vorzeichen ist positiv bei einer ungeraden Zahl fehlender Kategorienfamilien und negativ bei einer geraden.
Setzt man die vorige Formel in die Darstellung von \(\mathbb E[T]\) ein und vertauscht die Summen, so erhält man
$$\mathbb E[T]=\sum_{\substack{0\le s\le S\\0\le r\le R\\0\le d\le D\\s+r+d>0}}(-1)^{s+r+d+1}\binom{S}{s}\binom{R}{r}\binom{D}{d}\sum_{n=0}^{A(s,r,d)}\frac{\binom{A(s,r,d)}{n}}{\binom{M}{n}}.$$
Die innere Summe ist klassisch. Markiert man die \(B=M-A\) verbotenen Karten, dann ist die erwartete Position der ersten markierten Karte in einer Zufallspermutation
$$\frac{M+1}{B+1}.$$
Genau dieselbe Größe ist
$$\sum_{n=0}^{A}\frac{\binom{A}{n}}{\binom{M}{n}}=\frac{M+1}{M-A+1}=\frac{M+1}{B+1}.$$
Damit schrumpft jeder Inklusions-Exklusions-Term auf einen einzigen rationalen Faktor zusammen.
Mit \(B(s,r,d)=M-(D-d)\bigl((S-s)(R-r)+J\bigr)\) folgt
$$\boxed{\mathbb E[T]=\sum_{\substack{0\le s\le S\\0\le r\le R\\0\le d\le D\\s+r+d>0}}(-1)^{s+r+d+1}\binom{S}{s}\binom{R}{r}\binom{D}{d}\frac{M+1}{B(s,r,d)+1}.}$$
Genau diese Größe wird in den Implementierungen berechnet. Die Formel deckt auch reduzierte Varianten ab: Wenn Farben, Ränge oder Decks nicht gefordert sind, wird der jeweilige Summationsbereich einfach auf den Einzelwert \(0\) reduziert.
Eine der Implementierungen prüft den einfacheren Fall \(D=1\), \(S=4\), \(R=13\), \(J=2\), bei dem nur die \(13\) Ränge relevant sind. Dann ist
$$M=1(4\cdot 13+2)=54.$$
Es gibt also keine Summation über Farben oder Decks, sondern nur über \(r\). Für eine gewählte Menge von \(r\) fehlenden Rängen gilt
$$A(r)=4(13-r)+2=54-4r,$$
also
$$B(r)=54-(54-4r)=4r.$$
Damit wird der Erwartungswert zu
$$\mathbb E[T]=\sum_{r=1}^{13}(-1)^{r+1}\binom{13}{r}\frac{55}{4r+1}.$$
Ausgewertet ergibt das
$$\mathbb E[T]\approx 29.05361725,$$
genau den numerischen Kontrollwert aus der Implementierung.
Die C++-, Python- und Java-Implementierungen werten die geschlossene Formel direkt aus. Zuerst wird die Gesamtgröße des Schuhs \(M\) berechnet, danach werden alle möglichen Zahlen fehlender Farben, fehlender Ränge und fehlender Decks durchlaufen. Für jedes Tripel \((s,r,d)\) werden die binomiale Multiplizität, das Vorzeichen aus der Parität von \(s+r+d\), die Zahl erlaubter Karten \(A(s,r,d)\) und die Zahl verbotener Karten \(B(s,r,d)\) bestimmt; anschließend wird der signierte Beitrag
$$\binom{S}{s}\binom{R}{r}\binom{D}{d}\frac{M+1}{B(s,r,d)+1}$$
aufsummiert. Dasselbe Gerüst behandelt auch reduzierte Modi, indem eine deaktivierte Kategorie auf den einzigen Wert \(0\) fixiert wird. Die C++-Implementierung ergänzt vor der Ausgabe zwei Prüfungen: den obigen Rang-Checkpoint und einen winzigen Schuh mit \(D=S=R=2\) und \(J=0\), bei dem die geschlossene Formel mit einer exakten vollständigen Erwartungsrechnung verglichen wird.
Seien \(S_0\), \(R_0\) und \(D_0\) die aktiven Kategoriengrößen, also jeweils entweder die volle Größe oder \(0\), je nachdem, ob der Typ gefordert ist. Dann benötigt die Auswertung der geschlossenen Formel
$$O\bigl((S_0+1)(R_0+1)(D_0+1)\bigr)$$
signierte Summanden und \(O(1)\) Speicher. Die Implementierungen berechnen die Binomialkoeffizienten mit kurzen multiplikativen Produkten; dadurch entsteht nur ein sehr kleiner Zusatzfaktor linear in der Kategoriengröße. Für die echten Project-Euler-Parameter werden insgesamt nur
$$ (4+1)(13+1)(10+1)=770 $$
Terme ausgewertet.
\(D\) destelik bir ayakkabı düşünelim. Her destede \(S \cdot R\) normal kart ve \(J\) joker vardır. Normal bir kart üç etiket taşır: hangi desteye ait olduğu, rengi ve değeri. Bir joker ise yalnızca ait olduğu desteye katkı yapar; renk ve değer bilgisi taşımaz. Deste rastgele karıştırıldıktan sonra kartlar üstten açılır ve istenen her deste, her renk ve her değer en az bir kez görülene kadar devam edilir.
Project Euler girdisinde
$$D=10,\qquad S=4,\qquad R=13,\qquad J=2,$$
olduğu için toplam kart sayısı
$$M=D(SR+J)=10(4\cdot 13+2)=540$$
olur. İstenen şey, bu durma zamanının beklenen değerini sekiz ondalık basamak doğrulukla hesaplamaktır.
Uygulamalar kapalı bir dahil et-çıkar formülünü doğrudan hesaplar. Temel fikir, hangi kategori ailesinin hâlâ hiç görünmemiş olduğunu sabitleyip bu durumda kaç kartın “izinli” kaldığını saymaktır.
\(T\), istenen bütün kategorilerin ilk kez görülmüş olduğu çekiş numarası olsun. En fazla \(M\) kart açılabileceği için kuyruk-toplam özdeşliği
$$\mathbb E[T]=\sum_{n=0}^{M-1}\Pr(T>n)$$
şeklindedir. Dolayısıyla önce, ilk \(n\) çekişten sonra en az bir gerekli deste, renk ya da değerin hâlâ eksik kalma olasılığını bulmamız gerekir.
\(s\) renk, \(r\) değer ve \(d\) deste eksik kalsın. Bu seçimlerin sayısı
$$\binom{S}{s}\binom{R}{r}\binom{D}{d}$$
kadardır.
Bu kategorilerin ilk \(n\) çekiş boyunca hiç görünmemesi için açılan her kartın bu eksik kümelerden kaçınması gerekir. Yalnızca kalan \(D-d\) destelerden kart gelebilir. Böyle bir destede normal bir kart ancak rengi \(S-s\) izinli renklerden birinde ve değeri \(R-r\) izinli değerlerden birinde ise kabul edilir. O destelerdeki jokerlerin hepsi de izinlidir; çünkü renk ve değer taşımazlar. Bu yüzden izinli kart sayısı
$$A(s,r,d)=(D-d)\bigl((S-s)(R-r)+J\bigr)$$
olur. Yasak kart sayısı ise tamamlayıcı olarak
$$B(s,r,d)=M-A(s,r,d)$$
şeklindedir.
Rastgele bir permütasyonda ilk \(n\) kart, tüm ayakkabıdan eş olasılıklı bir \(n\)-li alt küme oluşturur. Dolayısıyla sabit eksik kümeler için, ilk \(n\) kartın tamamının \(A(s,r,d)\) izinli kart içinden gelme olasılığı
$$\frac{\binom{A(s,r,d)}{n}}{\binom{M}{n}}$$
olur; \(n>A(s,r,d)\) ise bu değer zaten \(0\) kabul edilir.
Şimdi boş olmayan tüm eksik renk, eksik değer ve eksik deste seçimleri üzerinde dahil et-çıkar yaparsak
$$\Pr(T>n)=\sum_{\substack{0\le s\le S\\0\le r\le R\\0\le d\le D\\s+r+d>0}}(-1)^{s+r+d+1}\binom{S}{s}\binom{R}{r}\binom{D}{d}\frac{\binom{A(s,r,d)}{n}}{\binom{M}{n}}$$
elde edilir. İşaret, eksik ilan edilen kategori ailesi sayısı tek ise artı, çift ise eksi olur.
Bu ifadeyi \(\mathbb E[T]\) formülüne koyup toplam sırasını değiştirirsek
$$\mathbb E[T]=\sum_{\substack{0\le s\le S\\0\le r\le R\\0\le d\le D\\s+r+d>0}}(-1)^{s+r+d+1}\binom{S}{s}\binom{R}{r}\binom{D}{d}\sum_{n=0}^{A(s,r,d)}\frac{\binom{A(s,r,d)}{n}}{\binom{M}{n}}$$
olur.
İç toplam klasik bir değerdir. \(B=M-A\) tane yasak kartı “işaretli” sayarsak, rastgele permütasyonda ilk işaretli kartın beklenen konumu
$$\frac{M+1}{B+1}$$
olur. Aynı nicelik
$$\sum_{n=0}^{A}\frac{\binom{A}{n}}{\binom{M}{n}}=\frac{M+1}{M-A+1}=\frac{M+1}{B+1}$$
eşitliğiyle de yazılır. Böylece her dahil et-çıkar terimi tek bir rasyonel çarpana indirgenir.
\(B(s,r,d)=M-(D-d)\bigl((S-s)(R-r)+J\bigr)\) yerine yazınca
$$\boxed{\mathbb E[T]=\sum_{\substack{0\le s\le S\\0\le r\le R\\0\le d\le D\\s+r+d>0}}(-1)^{s+r+d+1}\binom{S}{s}\binom{R}{r}\binom{D}{d}\frac{M+1}{B(s,r,d)+1}.}$$
çıkar. Uygulamaların hesapladığı ifade tam olarak budur. Aynı formül azaltılmış sürümleri de kapsar; eğer renk, değer veya deste türlerinden biri gerekmiyorsa, o eksendeki toplam yalnızca \(0\) değerine düşer.
Uygulamalardan biri \(D=1\), \(S=4\), \(R=13\), \(J=2\) olan ve yalnızca \(13\) değerin önemli olduğu daha küçük bir durumu doğrulama için kullanır. Bu durumda
$$M=1(4\cdot 13+2)=54$$
olur.
Renkler ve desteler üzerinden toplam yoktur; yalnızca \(r\) kalır. \(r\) adet eksik değer seçildiğinde izinli kart sayısı
$$A(r)=4(13-r)+2=54-4r,$$
yasak kart sayısı ise
$$B(r)=54-(54-4r)=4r$$
olur. Dolayısıyla beklenen değer
$$\mathbb E[T]=\sum_{r=1}^{13}(-1)^{r+1}\binom{13}{r}\frac{55}{4r+1}$$
şeklindedir ve toplamın sayısal değeri
$$\mathbb E[T]\approx 29.05361725$$
çıkar. Bu, uygulamadaki sayısal kontrol değeriyle aynıdır.
C++, Python ve Java uygulamalarının üçü de kapalı formülü doğrudan hesaplar. Önce toplam kart sayısı \(M\) bulunur; sonra olası eksik renk, eksik değer ve eksik deste sayıları üzerinde dolaşılır. Her \((s,r,d)\) üçlüsü için binom katsayısı çarpanı, \(s+r+d\) paritesinden gelen işaret, izinli kart sayısı \(A(s,r,d)\) ve yasak kart sayısı \(B(s,r,d)\) hesaplanır; ardından
$$\binom{S}{s}\binom{R}{r}\binom{D}{d}\frac{M+1}{B(s,r,d)+1}$$
terimi işaretine göre toplama eklenir. Aynı yapı, devre dışı bırakılmış bir kategori türü için o sayacı yalnızca \(0\)'a sabitleyerek daha basit modları da çözer. C++ uygulaması son cevabı yazmadan önce iki ek doğrulama yapar: yukarıdaki yalnızca-değerler kontrolü ve \(D=S=R=2\), \(J=0\) olan minik bir ayakkabıda kapalı formülün tam kapsamlı beklenen değer hesabıyla karşılaştırılması.
\(S_0\), \(R_0\) ve \(D_0\) aktif kategori boyutları olsun; yani her biri ya tam boyuttur ya da kategori istenmiyorsa \(0\)'dır. Kapalı formülün değerlendirilmesi
$$O\bigl((S_0+1)(R_0+1)(D_0+1)\bigr)$$
adet işaretli terim ve \(O(1)\) bellek gerektirir. Uygulamalardaki binom hesabı kısa çarpımsal döngüler kullandığından buna yalnızca çok küçük, kategori boyutuna lineer bir ek çarpan gelir. Gerçek Project Euler girdisinde toplam
$$ (4+1)(13+1)(10+1)=770 $$
terim hesaplanır.
Estudiamos un zapato formado por \(D\) barajas. Cada baraja contiene \(S \cdot R\) cartas ordinarias y \(J\) comodines. Una carta ordinaria lleva tres etiquetas: su baraja, su palo y su valor. Un comodín solo contribuye a la etiqueta de baraja; no tiene palo ni valor. Tras una mezcla uniforme, las cartas se revelan desde arriba hasta que haya aparecido al menos una vez cada baraja requerida, cada palo requerido y cada valor requerido.
En la instancia de Project Euler,
$$D=10,\qquad S=4,\qquad R=13,\qquad J=2,$$
así que el zapato tiene
$$M=D(SR+J)=10(4\cdot 13+2)=540$$
cartas en total. El objetivo es calcular el valor esperado del tiempo de parada con precisión suficiente para imprimir ocho decimales.
Las implementaciones evalúan directamente una fórmula cerrada de inclusión-exclusión. La idea central es fijar qué familias de categorías siguen completamente ausentes y contar cuántas cartas todavía son compatibles con esa ausencia.
Sea \(T\) el índice de extracción en el que por primera vez ya se han visto todas las categorías requeridas. Como no se pueden extraer más de \(M\) cartas, la identidad de suma por colas da
$$\mathbb E[T]=\sum_{n=0}^{M-1}\Pr(T>n).$$
Por tanto, basta con encontrar una expresión para la probabilidad de que después de \(n\) extracciones aún falte al menos una baraja, un palo o un valor requerido.
Fijemos conjuntos de categorías ausentes: \(s\) palos, \(r\) valores y \(d\) barajas. Hay
$$\binom{S}{s}\binom{R}{r}\binom{D}{d}$$
maneras de elegirlos.
Si todas esas categorías siguen sin aparecer tras \(n\) extracciones, entonces cada carta revelada debe evitarlas. Solo pueden salir cartas de las \(D-d\) barajas restantes. Dentro de una de esas barajas, una carta ordinaria solo es válida si su palo pertenece a los \(S-s\) palos permitidos y su valor a los \(R-r\) valores permitidos. Todos los comodines de las barajas supervivientes siguen siendo válidos, porque no tienen ni palo ni valor. En consecuencia, el número de cartas permitidas es
$$A(s,r,d)=(D-d)\bigl((S-s)(R-r)+J\bigr).$$
El número complementario de cartas prohibidas es
$$B(s,r,d)=M-A(s,r,d).$$
Tras una permutación aleatoria, las primeras \(n\) cartas forman un subconjunto uniforme de tamaño \(n\) dentro de todo el zapato. Por ello, para conjuntos ausentes fijos, la probabilidad de que las primeras \(n\) cartas estén todas entre las \(A(s,r,d)\) cartas permitidas es
$$\frac{\binom{A(s,r,d)}{n}}{\binom{M}{n}},$$
entendiendo que el valor es \(0\) cuando \(n>A(s,r,d)\).
Aplicando inclusión-exclusión sobre todas las elecciones no vacías de palos, valores y barajas ausentes, obtenemos
$$\Pr(T>n)=\sum_{\substack{0\le s\le S\\0\le r\le R\\0\le d\le D\\s+r+d>0}}(-1)^{s+r+d+1}\binom{S}{s}\binom{R}{r}\binom{D}{d}\frac{\binom{A(s,r,d)}{n}}{\binom{M}{n}}.$$
El signo es positivo cuando el número de familias declaradas ausentes es impar y negativo cuando es par.
Sustituyendo la fórmula anterior en la expresión de \(\mathbb E[T]\) e intercambiando el orden de las sumas, aparece
$$\mathbb E[T]=\sum_{\substack{0\le s\le S\\0\le r\le R\\0\le d\le D\\s+r+d>0}}(-1)^{s+r+d+1}\binom{S}{s}\binom{R}{r}\binom{D}{d}\sum_{n=0}^{A(s,r,d)}\frac{\binom{A(s,r,d)}{n}}{\binom{M}{n}}.$$
La suma interior es clásica. Si se marcan las \(B=M-A\) cartas prohibidas, la posición esperada de la primera carta marcada en una permutación aleatoria es
$$\frac{M+1}{B+1}.$$
Esa misma cantidad satisface
$$\sum_{n=0}^{A}\frac{\binom{A}{n}}{\binom{M}{n}}=\frac{M+1}{M-A+1}=\frac{M+1}{B+1}.$$
Así, cada término de inclusión-exclusión se reduce a un único factor racional.
Sustituyendo \(B(s,r,d)=M-(D-d)\bigl((S-s)(R-r)+J\bigr)\), resulta
$$\boxed{\mathbb E[T]=\sum_{\substack{0\le s\le S\\0\le r\le R\\0\le d\le D\\s+r+d>0}}(-1)^{s+r+d+1}\binom{S}{s}\binom{R}{r}\binom{D}{d}\frac{M+1}{B(s,r,d)+1}.}$$
Esa es exactamente la expresión que evalúan las implementaciones. La misma fórmula sirve también para variantes reducidas: si palos, valores o barajas no se exigen, el rango correspondiente se contrae al único valor \(0\).
Una de las implementaciones comprueba el caso más simple \(D=1\), \(S=4\), \(R=13\), \(J=2\), donde solo importan los \(13\) valores. Entonces
$$M=1(4\cdot 13+2)=54.$$
No hay suma sobre palos ni sobre barajas; solo queda \(r\). Si elegimos \(r\) valores ausentes, el número de cartas permitidas es
$$A(r)=4(13-r)+2=54-4r,$$
y por tanto el número de cartas prohibidas es
$$B(r)=54-(54-4r)=4r.$$
La esperanza se reduce a
$$\mathbb E[T]=\sum_{r=1}^{13}(-1)^{r+1}\binom{13}{r}\frac{55}{4r+1}.$$
Al evaluar la suma se obtiene
$$\mathbb E[T]\approx 29.05361725,$$
que coincide con la comprobación numérica usada por la implementación.
Las implementaciones en C++, Python y Java evalúan directamente la fórmula cerrada. Primero calculan el tamaño total del zapato \(M\), luego recorren todos los posibles números de palos ausentes, valores ausentes y barajas ausentes. Para cada triple \((s,r,d)\) calculan la multiplicidad binomial, el signo según la paridad de \(s+r+d\), el número de cartas permitidas \(A(s,r,d)\) y el número de cartas prohibidas \(B(s,r,d)\), y añaden el término firmado
$$\binom{S}{s}\binom{R}{r}\binom{D}{d}\frac{M+1}{B(s,r,d)+1}.$$
El mismo esquema resuelve modos reducidos fijando en \(0\) el contador de una categoría desactivada. La implementación en C++ añade además dos comprobaciones: el caso de solo-valores descrito arriba y un zapato diminuto con \(D=S=R=2\) y \(J=0\), donde la fórmula cerrada se compara con una esperanza exacta obtenida por exploración exhaustiva.
Sean \(S_0\), \(R_0\) y \(D_0\) los tamaños activos de categoría; cada uno es el tamaño completo o \(0\), según si esa familia se exige o no. La evaluación de la fórmula cerrada usa
$$O\bigl((S_0+1)(R_0+1)(D_0+1)\bigr)$$
términos firmados y \(O(1)\) memoria. Las implementaciones calculan los coeficientes binomiales con productos multiplicativos cortos, así que solo aparece un factor extra muy pequeño lineal en el tamaño de la categoría. En los parámetros reales de Project Euler se evalúan apenas
$$ (4+1)(13+1)(10+1)=770 $$
términos.
我们考虑一个由 \(D\) 副牌组成的牌靴。每一副牌包含 \(S \cdot R\) 张普通牌和 \(J\) 张鬼牌。普通牌同时带有三个标签：它属于哪一副牌、它的花色、它的点数。鬼牌只对“牌副”这一类目有贡献，不携带花色或点数。把整副牌靴均匀洗乱后，从上往下依次翻牌，直到每一个要求出现的牌副、花色和点数都至少出现过一次为止。
在 Project Euler 的实际参数中，
$$D=10,\qquad S=4,\qquad R=13,\qquad J=2,$$
因此总牌数是
$$M=D(SR+J)=10(4\cdot 13+2)=540.$$
题目要计算这个停止时刻的期望值，并最终输出到小数点后八位。
这些实现都直接计算一个闭式的容斥公式。核心思路是：先固定“哪些类别到当前为止仍然完全没有出现”，再去数在这种约束下前面的牌只能从哪些牌中选出。
设 \(T\) 为第一次满足“所有要求类别都已经见过”的抽牌位置。由于最多只能抽到 \(M\) 张牌，尾和公式给出
$$\mathbb E[T]=\sum_{n=0}^{M-1}\Pr(T>n).$$
所以问题变成：对每个 \(n\)，求在前 \(n\) 张牌之后，仍然至少缺少一个要求的牌副、花色或点数的概率。
假设仍然缺失 \(s\) 个花色、\(r\) 个点数和 \(d\) 副牌。这样的选择一共有
$$\binom{S}{s}\binom{R}{r}\binom{D}{d}$$
种。
如果这些类别在前 \(n\) 次抽牌之后仍然没有出现，那么已经翻出的每一张牌都必须避开这些缺失类别。也就是说，只能从剩下的 \(D-d\) 副牌里抽到牌；在这些牌副中，一张普通牌只有在它的花色属于剩余的 \(S-s\) 个允许花色、并且它的点数属于剩余的 \(R-r\) 个允许点数时才是“安全”的。剩余牌副中的所有鬼牌也都是允许的，因为鬼牌没有花色和点数标签。于是允许出现的牌数为
$$A(s,r,d)=(D-d)\bigl((S-s)(R-r)+J\bigr).$$
相应地，禁止出现的牌数为
$$B(s,r,d)=M-A(s,r,d).$$
随机洗牌之后，前 \(n\) 张牌等价于从整副牌靴中等概率抽出的一个大小为 \(n\) 的子集。因此，在缺失集合固定的前提下，前 \(n\) 张牌全部落在这 \(A(s,r,d)\) 张允许牌中的概率是
$$\frac{\binom{A(s,r,d)}{n}}{\binom{M}{n}},$$
当 \(n>A(s,r,d)\) 时，该值自然视为 \(0\)。
然后对所有非空的缺失花色、缺失点数、缺失牌副集合使用容斥原理，就得到
$$\Pr(T>n)=\sum_{\substack{0\le s\le S\\0\le r\le R\\0\le d\le D\\s+r+d>0}}(-1)^{s+r+d+1}\binom{S}{s}\binom{R}{r}\binom{D}{d}\frac{\binom{A(s,r,d)}{n}}{\binom{M}{n}}.$$
其中，当宣布缺失的类别族数目为奇数时符号为正，为偶数时符号为负。
把上式代回 \(\mathbb E[T]\)，并交换求和顺序，可得
$$\mathbb E[T]=\sum_{\substack{0\le s\le S\\0\le r\le R\\0\le d\le D\\s+r+d>0}}(-1)^{s+r+d+1}\binom{S}{s}\binom{R}{r}\binom{D}{d}\sum_{n=0}^{A(s,r,d)}\frac{\binom{A(s,r,d)}{n}}{\binom{M}{n}}.$$
内部这个求和是一个经典恒等式。若把 \(B=M-A\) 张禁止牌看成“标记牌”，那么在随机排列中第一张标记牌出现的位置期望是
$$\frac{M+1}{B+1}.$$
而这恰好等于
$$\sum_{n=0}^{A}\frac{\binom{A}{n}}{\binom{M}{n}}=\frac{M+1}{M-A+1}=\frac{M+1}{B+1}.$$
因此，每一个容斥项都能压缩成一个单独的有理数因子。
代入 \(B(s,r,d)=M-(D-d)\bigl((S-s)(R-r)+J\bigr)\)，最终得到
$$\boxed{\mathbb E[T]=\sum_{\substack{0\le s\le S\\0\le r\le R\\0\le d\le D\\s+r+d>0}}(-1)^{s+r+d+1}\binom{S}{s}\binom{R}{r}\binom{D}{d}\frac{M+1}{B(s,r,d)+1}.}$$
这正是实现中直接计算的公式。它也自动适用于简化模式：如果某一类目并不要求覆盖，那么对应的求和范围就退化为唯一的 \(0\)。
有一个实现先验证一个更简单的情形：\(D=1\)、\(S=4\)、\(R=13\)、\(J=2\)，并且只要求 \(13\) 个点数都至少出现一次。此时
$$M=1(4\cdot 13+2)=54.$$
因为花色和牌副都不参与覆盖，所以只剩下 \(r\) 这一重求和。若选定 \(r\) 个仍然缺失的点数，则允许牌数是
$$A(r)=4(13-r)+2=54-4r,$$
从而禁止牌数为
$$B(r)=54-(54-4r)=4r.$$
于是期望值化为
$$\mathbb E[T]=\sum_{r=1}^{13}(-1)^{r+1}\binom{13}{r}\frac{55}{4r+1}.$$
把这个和式算出来，得到
$$\mathbb E[T]\approx 29.05361725,$$
与实现中的数值校验完全一致。
C++、Python 和 Java 三个实现都直接计算上面的闭式。它们先算出总牌数 \(M\)，然后枚举缺失花色数、缺失点数数和缺失牌副数。对于每个三元组 \((s,r,d)\)，程序计算二项式组合数乘子、由 \(s+r+d\) 奇偶性决定的符号、允许牌数 \(A(s,r,d)\) 以及禁止牌数 \(B(s,r,d)\)，再把
$$\binom{S}{s}\binom{R}{r}\binom{D}{d}\frac{M+1}{B(s,r,d)+1}$$
按正负号累加起来。若某一类目不需要覆盖，对应计数器就固定为 \(0\)，因此同一套框架可以同时处理简化版和完整题目。C++ 实现还额外做了两个自检：一个是上面的“只看点数”校验，另一个是 \(D=S=R=2\)、\(J=0\) 的微型牌靴，在那里闭式结果会与精确的穷举期望值进行比较。
设 \(S_0\)、\(R_0\)、\(D_0\) 是实际启用的类别规模；每个量要么取完整规模，要么在该类别不要求时取 \(0\)。闭式求值需要
$$O\bigl((S_0+1)(R_0+1)(D_0+1)\bigr)$$
个带符号的求和项，空间复杂度为 \(O(1)\)。实现中二项式系数采用很短的乘法循环计算，因此只带来一个很小的、与类别规模线性相关的额外因子。对于 Project Euler 的真实参数，总共只需要处理
$$ (4+1)(13+1)(10+1)=770 $$
项，计算量非常小。
Рассматривается башмак из \(D\) колод. В каждой колоде есть \(S \cdot R\) обычных карт и \(J\) джокеров. Обычная карта несет три метки: колода, масть и достоинство. Джокер влияет только на метку колоды и не имеет ни масти, ни достоинства. После равномерного перемешивания карты открываются сверху вниз, пока каждая требуемая колода, каждая требуемая масть и каждое требуемое достоинство не встретятся хотя бы один раз.
Для экземпляра из Project Euler
$$D=10,\qquad S=4,\qquad R=13,\qquad J=2,$$
поэтому всего карт
$$M=D(SR+J)=10(4\cdot 13+2)=540.$$
Нужно вычислить математическое ожидание этого момента остановки с точностью, достаточной для вывода восьми знаков после запятой.
Все реализации напрямую вычисляют замкнутую формулу включения-исключения. Главная идея состоит в том, чтобы зафиксировать, какие семейства категорий все еще полностью отсутствуют, и посчитать, сколько карт совместимо с таким условием.
Пусть \(T\) — номер вытягивания, на котором впервые оказались покрыты все требуемые категории. Так как больше \(M\) карт вытянуть нельзя, по формуле хвостовой суммы имеем
$$\mathbb E[T]=\sum_{n=0}^{M-1}\Pr(T>n).$$
Значит, достаточно найти вероятность того, что после \(n\) вытягиваний все еще отсутствует хотя бы одна требуемая колода, масть или достоинство.
Пусть по-прежнему отсутствуют \(s\) мастей, \(r\) достоинств и \(d\) колод. Выбрать их можно
$$\binom{S}{s}\binom{R}{r}\binom{D}{d}$$
способами.
Чтобы эти категории не появились среди первых \(n\) карт, каждая открытая карта должна их обходить. Разрешены только карты из оставшихся \(D-d\) колод. Внутри такой колоды обычная карта допустима тогда и только тогда, когда ее масть лежит среди \(S-s\) разрешенных мастей, а достоинство — среди \(R-r\) разрешенных достоинств. Все джокеры из выживших колод тоже допустимы, потому что не имеют ни масти, ни достоинства. Поэтому число допустимых карт равно
$$A(s,r,d)=(D-d)\bigl((S-s)(R-r)+J\bigr).$$
Число запрещенных карт равно дополнению
$$B(s,r,d)=M-A(s,r,d).$$
После случайной перестановки первые \(n\) карт образуют равномерно выбранное \(n\)-элементное подмножество всего башмака. Поэтому для фиксированных отсутствующих множеств вероятность того, что все первые \(n\) карт входят в число \(A(s,r,d)\) допустимых, равна
$$\frac{\binom{A(s,r,d)}{n}}{\binom{M}{n}},$$
причем при \(n>A(s,r,d)\) это выражение понимается как \(0\).
Теперь применяем включение-исключение по всем непустым выборам отсутствующих мастей, достоинств и колод:
$$\Pr(T>n)=\sum_{\substack{0\le s\le S\\0\le r\le R\\0\le d\le D\\s+r+d>0}}(-1)^{s+r+d+1}\binom{S}{s}\binom{R}{r}\binom{D}{d}\frac{\binom{A(s,r,d)}{n}}{\binom{M}{n}}.$$
Знак положителен, если число объявленных отсутствующими семейств категорий нечетно, и отрицателен, если оно четно.
Подставим предыдущую формулу в выражение для \(\mathbb E[T]\) и поменяем порядок суммирования:
$$\mathbb E[T]=\sum_{\substack{0\le s\le S\\0\le r\le R\\0\le d\le D\\s+r+d>0}}(-1)^{s+r+d+1}\binom{S}{s}\binom{R}{r}\binom{D}{d}\sum_{n=0}^{A(s,r,d)}\frac{\binom{A(s,r,d)}{n}}{\binom{M}{n}}.$$
Внутренняя сумма классическая. Если отметить \(B=M-A\) запрещенных карт, то ожидаемая позиция первой отмеченной карты в случайной перестановке равна
$$\frac{M+1}{B+1}.$$
Эта же величина совпадает с
$$\sum_{n=0}^{A}\frac{\binom{A}{n}}{\binom{M}{n}}=\frac{M+1}{M-A+1}=\frac{M+1}{B+1}.$$
Тем самым каждый член включения-исключения сводится к одному рациональному множителю.
Подставляя \(B(s,r,d)=M-(D-d)\bigl((S-s)(R-r)+J\bigr)\), получаем
$$\boxed{\mathbb E[T]=\sum_{\substack{0\le s\le S\\0\le r\le R\\0\le d\le D\\s+r+d>0}}(-1)^{s+r+d+1}\binom{S}{s}\binom{R}{r}\binom{D}{d}\frac{M+1}{B(s,r,d)+1}.}$$
Именно это выражение и вычисляют реализации. Та же формула покрывает и упрощенные режимы: если масти, достоинства или колоды не нужно отслеживать, соответствующий диапазон суммирования просто сжимается до единственного значения \(0\).
Одна из реализаций проверяет более простой случай \(D=1\), \(S=4\), \(R=13\), \(J=2\), где важны только \(13\) достоинств. Тогда
$$M=1(4\cdot 13+2)=54.$$
Суммирования по мастям и колодам нет, остается только \(r\). Для выбранного множества из \(r\) отсутствующих достоинств число допустимых карт равно
$$A(r)=4(13-r)+2=54-4r,$$
а число запрещенных карт равно
$$B(r)=54-(54-4r)=4r.$$
Следовательно,
$$\mathbb E[T]=\sum_{r=1}^{13}(-1)^{r+1}\binom{13}{r}\frac{55}{4r+1}.$$
Численное значение суммы
$$\mathbb E[T]\approx 29.05361725,$$
и оно совпадает с контрольным значением, используемым в реализации.
Реализации на C++, Python и Java напрямую вычисляют приведенную выше замкнутую формулу. Сначала находится общий размер башмака \(M\), затем перебираются все возможные количества отсутствующих мастей, отсутствующих достоинств и отсутствующих колод. Для каждого тройного индекса \((s,r,d)\) программа вычисляет биномиальный множитель, знак по четности \(s+r+d\), число допустимых карт \(A(s,r,d)\) и число запрещенных карт \(B(s,r,d)\), после чего прибавляет подписанный вклад
$$\binom{S}{s}\binom{R}{r}\binom{D}{d}\frac{M+1}{B(s,r,d)+1}.$$
Тот же каркас работает и для упрощенных режимов: отключенная категория просто фиксируется на значении \(0\). В реализации на C++ есть еще две проверки: приведенный выше контроль только по достоинствам и крошечный башмак с \(D=S=R=2\) и \(J=0\), где замкнутая формула сравнивается с точным ожиданием, полученным полным перебором состояний.
Пусть \(S_0\), \(R_0\) и \(D_0\) — активные размеры категорий; каждый из них равен либо полному размеру, либо \(0\), если данный тип не требуется. Тогда вычисление замкнутой формулы использует
$$O\bigl((S_0+1)(R_0+1)(D_0+1)\bigr)$$
подписанных слагаемых и \(O(1)\) памяти. Биномиальные коэффициенты в реализациях считаются короткими мультипликативными циклами, поэтому появляется лишь очень маленький дополнительный множитель, линейный по размеру категории. Для реальных параметров Project Euler вычисляется всего
$$ (4+1)(13+1)(10+1)=770 $$
слагаемых.
ننظر إلى حذاء أوراق مكوَّن من \(D\) رزم. كل رزمة تحتوي على \(S \cdot R\) بطاقة عادية و\(J\) بطاقات جوكر. البطاقة العادية تحمل ثلاث سمات: الرزمة التي جاءت منها، ونوعها، ورتبتها. أما الجوكر فيسهم فقط في فئة الرزمة، ولا يحمل نوعًا ولا رتبة. بعد خلط الحذاء خلطًا عشوائيًا منتظمًا، نكشف البطاقات من الأعلى حتى تكون كل رزمة مطلوبة، وكل نوع مطلوب، وكل رتبة مطلوبة قد ظهرت مرة واحدة على الأقل.
في مدخل Project Euler الفعلي لدينا
$$D=10,\qquad S=4,\qquad R=13,\qquad J=2,$$
ولذلك يكون العدد الكلي للبطاقات
$$M=D(SR+J)=10(4\cdot 13+2)=540.$$
المطلوب هو حساب القيمة المتوقعة لزمن التوقف هذا بدقة تكفي لعرض ثمانية أرقام عشرية.
جميع التطبيقات تحسب مباشرة صيغة مغلقة مبنية على مبدأ الاشتمال والاستبعاد. الفكرة الأساسية هي تثبيت العائلات التي ما زالت غائبة بالكامل، ثم عدّ عدد البطاقات التي يمكن أن تظهر من دون كسر هذا الغياب.
لنرمز بـ \(T\) إلى رقم السحبة التي تتحقق عندها لأول مرة تغطية جميع الفئات المطلوبة. وبما أن عدد السحبات لا يمكن أن يتجاوز \(M\)، فإن هوية مجموع الذيل تعطينا
$$\mathbb E[T]=\sum_{n=0}^{M-1}\Pr(T>n).$$
إذًا يكفي أن نحسب احتمال أنه بعد أول \(n\) بطاقات ما زالت هناك رزمة مطلوبة أو نوع مطلوب أو رتبة مطلوبة لم تظهر بعد.
ثبّت \(s\) أنواع مفقودة و\(r\) رتبًا مفقودة و\(d\) رزمًا مفقودة. عدد طرق اختيارها هو
$$\binom{S}{s}\binom{R}{r}\binom{D}{d}.$$
ولكي تبقى هذه الفئات كلها غير مرئية بعد \(n\) سحبات، يجب أن تتجنبها كل بطاقة مكشوفة. أي لا يجوز أن تظهر إلا بطاقات من الرزم المتبقية وعددها \(D-d\). وداخل كل رزمة باقية تكون البطاقة العادية مسموحة فقط إذا كان نوعها من بين \(S-s\) الأنواع المسموحة وكانت رتبتها من بين \(R-r\) الرتب المسموحة. أما جميع بطاقات الجوكر في الرزم الباقية فهي مسموحة دائمًا لأنها لا تحمل نوعًا ولا رتبة. لذلك يكون عدد البطاقات المسموحة
$$A(s,r,d)=(D-d)\bigl((S-s)(R-r)+J\bigr).$$
أما عدد البطاقات الممنوعة فهو المتمم
$$B(s,r,d)=M-A(s,r,d).$$
بعد ترتيب عشوائي، تمثل أول \(n\) بطاقات مجموعة فرعية موحدة الاحتمال من الحجم \(n\) من كامل الحذاء. لذلك، عند تثبيت المجموعات المفقودة، فإن احتمال أن تقع أول \(n\) بطاقات كلها ضمن \(A(s,r,d)\) بطاقة مسموحة هو
$$\frac{\binom{A(s,r,d)}{n}}{\binom{M}{n}},$$
ويُفهم هذا المقدار على أنه \(0\) عندما \(n>A(s,r,d)\).
وبتطبيق مبدأ الاشتمال والاستبعاد على جميع الاختيارات غير الفارغة للأنواع المفقودة والرتب المفقودة والرزم المفقودة نحصل على
$$\Pr(T>n)=\sum_{\substack{0\le s\le S\\0\le r\le R\\0\le d\le D\\s+r+d>0}}(-1)^{s+r+d+1}\binom{S}{s}\binom{R}{r}\binom{D}{d}\frac{\binom{A(s,r,d)}{n}}{\binom{M}{n}}.$$
وتكون الإشارة موجبة عندما يكون عدد عائلات الفئات المعلنة مفقودة عددًا فرديًا، وسالبة عندما يكون زوجيًا.
إذا عوّضنا بهذه الصيغة داخل \(\mathbb E[T]\) وبدّلنا ترتيب المجاميع، حصلنا على
$$\mathbb E[T]=\sum_{\substack{0\le s\le S\\0\le r\le R\\0\le d\le D\\s+r+d>0}}(-1)^{s+r+d+1}\binom{S}{s}\binom{R}{r}\binom{D}{d}\sum_{n=0}^{A(s,r,d)}\frac{\binom{A(s,r,d)}{n}}{\binom{M}{n}}.$$
المجموع الداخلي مقدار كلاسيكي. فإذا اعتبرنا البطاقات الممنوعة وعددها \(B=M-A\) بطاقاتٍ معلَّمة، فإن الموضع المتوقع لأول بطاقة معلَّمة في ترتيب عشوائي يساوي
$$\frac{M+1}{B+1}.$$
وهذا هو نفسه
$$\sum_{n=0}^{A}\frac{\binom{A}{n}}{\binom{M}{n}}=\frac{M+1}{M-A+1}=\frac{M+1}{B+1}.$$
وبذلك ينهار كل حد من حدود الاشتمال والاستبعاد إلى عامل نسبي واحد فقط.
بعد التعويض عن
$$B(s,r,d)=M-(D-d)\bigl((S-s)(R-r)+J\bigr)$$
نصل إلى الصيغة
$$\boxed{\mathbb E[T]=\sum_{\substack{0\le s\le S\\0\le r\le R\\0\le d\le D\\s+r+d>0}}(-1)^{s+r+d+1}\binom{S}{s}\binom{R}{r}\binom{D}{d}\frac{M+1}{B(s,r,d)+1}.}$$
وهذه هي الكمية التي تحسبها التطبيقات مباشرة. كما أن الصيغة نفسها تغطي الأنماط الأبسط: إذا كانت فئة معينة غير مطلوبة أصلًا، فإن مجال الجمع الموافق لها يختزل إلى القيمة الوحيدة \(0\).
إحدى التطبيقات تختبر أولًا حالة أبسط هي \(D=1\)، \(S=4\)، \(R=13\)، \(J=2\)، حيث لا نهتم إلا بظهور الرتب الثلاث عشرة. عندها
$$M=1(4\cdot 13+2)=54.$$
لا يوجد جمع على الأنواع ولا على الرزم، ويبقى المتغير \(r\) فقط. فإذا اخترنا \(r\) رتبًا ما زالت مفقودة، فإن عدد البطاقات المسموحة هو
$$A(r)=4(13-r)+2=54-4r,$$
ومن ثم يكون عدد البطاقات الممنوعة
$$B(r)=54-(54-4r)=4r.$$
فتصبح القيمة المتوقعة
$$\mathbb E[T]=\sum_{r=1}^{13}(-1)^{r+1}\binom{13}{r}\frac{55}{4r+1}.$$
وبعد التقييم نحصل على
$$\mathbb E[T]\approx 29.05361725,$$
وهو بالضبط مقدار التحقق العددي المستخدم داخل التنفيذ.
تقوم تطبيقات C++ وPython وJava بحساب الصيغة المغلقة مباشرة. فهي تبدأ بحساب الحجم الكلي للحذاء \(M\)، ثم تدور على جميع الأعداد الممكنة للأنواع المفقودة والرتب المفقودة والرزم المفقودة. ولكل ثلاثي \((s,r,d)\) تحسب المعامل الثنائي، والإشارة الناتجة من فردية أو زوجية \(s+r+d\)، وعدد البطاقات المسموحة \(A(s,r,d)\)، وعدد البطاقات الممنوعة \(B(s,r,d)\)، ثم تضيف الحد الموقَّع
$$\binom{S}{s}\binom{R}{r}\binom{D}{d}\frac{M+1}{B(s,r,d)+1}.$$
والهيكل نفسه يتعامل أيضًا مع الأوضاع المختزلة، وذلك بتثبيت عدّاد الفئة المعطلة عند \(0\). ويضيف تنفيذ C++ فحصين إضافيين قبل طباعة الجواب النهائي: فحص حالة الرتب فقط المذكورة أعلاه، وحالة صغيرة جدًا فيها \(D=S=R=2\) و\(J=0\) حيث تُقارَن الصيغة المغلقة مع قيمة متوقعة دقيقة محسوبة باستكشاف شامل للحالات.
لتكن \(S_0\) و\(R_0\) و\(D_0\) هي أحجام الفئات النشطة؛ أي إن كلًّا منها يساوي الحجم الكامل أو يساوي \(0\) إذا كانت تلك الفئة غير مطلوبة. عندئذٍ يحتاج تقييم الصيغة المغلقة إلى
$$O\bigl((S_0+1)(R_0+1)(D_0+1)\bigr)$$
حدًا ذا إشارة، ويستخدم ذاكرة \(O(1)\). أما معاملات ثنائية الحد فتُحسب في التطبيقات بواسطة جداءات قصيرة، ولذلك لا يظهر إلا عامل إضافي صغير جدًا خطي في حجم الفئة. وفي معطيات Project Euler الحقيقية لا يلزم إلا حساب
$$ (4+1)(13+1)(10+1)=770 $$
حدًا فقط.