Project Euler Problem 796

Solution

Answer: 43.20649061

Let $T$ be the number of cards drawn until we have seen:

all $4$ suits,
all $13$ ranks,
all $10$ deck designs.

We use the standard identity for expectation of a stopping time:

$$\mathbb E[T] = \sum_{n\ge 0} \Pr(T>n).$$

Define an inclusion–exclusion event where some subset of suits, ranks, and deck designs are still missing after $n$ draws.

If:

$a$ suits are missing,
$b$ ranks are missing,
$c$ deck designs are missing,

then the remaining allowable cards are:

$$m(a,b,c) = (10-c)\Big((4-a)(13-b)+2\Big).$$

Explanation:

each non-missing deck contributes $(4-a)(13-b)$ ordinary cards,
plus $2$ jokers (which have no suit/rank),
missing decks contribute nothing.

The probability that none of those forbidden labels have appeared after $n$ draws is:

$$\frac{\binom{m(a,b,c)}{n}}{\binom{540}{n}}.$$

Applying inclusion–exclusion and summing over $n$, we use the identity

$$\sum_{n\ge0}\frac{\binom{m}{n}}{\binom{N}{n}} = \frac{N+1}{N+1-m}.$$

Thus

$$\mathbb E[T] = \sum_{a=0}^{4} \sum_{b=0}^{13} \sum_{c=0}^{10} {}' (-1)^{a+b+c+1} \binom{4}{a} \binom{13}{b} \binom{10}{c} \cdot \frac{541}{541-m(a,b,c)},$$

where the prime excludes $(a,b,c)=(0,0,0)$.

As a check, applying the same method to the single-deck “all ranks” example reproduces the problem’s value:

$$29.053617250830\ldots$$

which matches $29.05361725$.

Evaluating the full sum gives:

$$43.20649061473821\ldots$$

Rounded to eight decimal places:

Answer: 43.20649061