Probability of rolling every face of a die at least once in a sequence of N throws.

Question

Say you have a die with $k$ faces (each face has a probability $1/k$).

You throw this die $n$ times.

What is the probability of having every single face showing at least once in that sequence?

Answer 1

Imagine throwing sequentially. There are then $k^n$ equally likely outcomes.

Now we count the favourables, in which each face appears at least once. This is a messy business, for which there is no closed form unless we use Stirling Numbers of the Second Kind (please see Wikipedia). Let $n\ge k$.

Let us count the bad outcomes, in which at least one face is missing. There are $(k-1)^n$ outcomes in which Face $1$ is missing, and the same number where Face $2$ is missing, for a total of $k(k-1)^n$.

However, this double-counts the cases where two faces are missing. Which two faces are missing can be chosen in $\binom{k}{2}$ ways, and then the rest of the faces can be filled in in $(k-2)^n$ ways.

So our new estimate for the number of bad choices is $k(k-1)^n-\binom{k}{2}(k-2)^n$.

However, we have subtracted too much, for we have subtracted one too many times the outcomes where $3$ faces are missing. There are $(k-3)^n$ outcomes where three specific faces (at least) are missing. Add up over all the $\binom{k}{3}$ ways to choose three specific spaces. That gives a new estimate of $k(k-1)^n-\binom{k}{2}(k-2)^n+\binom{k}{3}(k-3)^n$.

Continue.

Answer 2

The proof that the PIE argument yields the Stirling numbers times $k!$ i.e. that $$\sum_{q=0}^k {k\choose q} (-1)^q (k-q)^N = {N\brace k} \times k!$$ uses the integral $$(k-q)^N = \frac{N!}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z^{N+1}} \exp((k-q)z) \; dz$$ which gives for the sum $$\frac{N!}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z^{N+1}} \sum_{q=0}^k {k\choose q} (-1)^q \exp((k-q)z) \; dz \\ = \frac{N!}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z^{N+1}} (\exp(z)-1)^k \; dz.$$

This however is precisely $${N\brace k}\times k!$$ because the Stirling numbers of the second kind are the species $$\mathfrak{P}(\mathcal{U}(\mathfrak{P}_{\ge 1}(\mathcal{Z}))$$ which yields the generating function $$G(z,u) = \exp(u(\exp(z)-1)).$$