Detailed mathematical approach

Problem Summary

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.

Mathematical Approach

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.

Step 1: Define the stopping time

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.

Step 2: Choose which categories are 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).$

Step 3: Probability that the first \(n\) draws avoid those categories

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.

Step 4: Collapse the tail sum

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.

Step 5: Final closed form

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\).

Worked Example: only ranks are required in one deck

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.

How the Code Works

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.

Complexity Analysis

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.

Footnotes and References

1. Problem page: https://projecteuler.net/problem=796
2. Inclusion-exclusion principle: Wikipedia - Inclusion-exclusion principle
3. Negative hypergeometric distribution: Wikipedia - Negative hypergeometric distribution
4. Binomial coefficient: Wikipedia - Binomial coefficient