If I randomly pick 80 cards, uniformly, from a standard 52-card deck, with replacement, what is the probability that every card is drawn at least once?
I understand that to tackle this question, I will most probably need to use Inclusion/Exclusion, however, I'm not entirely sure how to solve this.
Any help would be greatly appreciated.
Best Answer
Someone else asked a similar question a little while after this one. I'm modifying and reposting my answer from there to here. I've also added an example since it's early in the morning and the baby is still sleeping.
The short answer is $$\frac{{80\brace52}52!}{52^{80}}.$$
Explanation: Suppose we have a deck of $k$ cards, say $C=\{c_1,c_2,\ldots, c_k\}$, and we draw, with replacement, $n\geq k$ of them. Let $(d_1,\ldots, d_n)$ be the sequence of draws (so each $d_j\in C$). I'll call this a drawing.
Obviously there are $k^n$ possible drawings.
In how many drawings is each card chosen at least once? I'll call these good drawings. Well, let $(d_1,\ldots, d_n)$ be a drawing and suppose we have $k$ buckets labelled $\{c_1,c_2,\ldots, c_k\}$. Place $d_j$ into bucket $c_i$ when $d_j=c_i$. Then we know that the drawing is good if and only if each bucket is non-empty.
Now, suppose we have $k$ identical buckets and place symbols $\{D_1,\ldots, D_n\}$ into the buckets, making sure that each bucket gets at least one symbol. We make the convention that two such placements are the same if the buckets can be rearranged to get one from the other. By the definition of the Stirling number of the second kind, there are ${n\brace k}$ ways of doing this. Next, label the buckets with labels $\{c_1,\ldots,c_k\}$. There are $k!$ ways of doing this.
For each of the above placements and labellings, we can then define a good drawing $(d_1,\ldots, d_n)$ by setting $d_j=c_i$ if and only if $D_j$ was placed in bucket labelled $c_i$.
Thus there are exactly ${n\brace k}k!$ good drawings and so the probability that a drawing is good is $$\frac{{n\brace k} k!}{k^{n}}.$$
Example with a deck of $k=2$ cards, say $\{0,1\}$, and $n=3$ draws. In this case a drawing is simply a binary sequence of length 3, and clearly only $(1,1,1)$ and $(0,0,0)$ are not good drawings, so the probability should be $3/4$.
Now let $B_1$, and $B_2$ be the buckets. We want to put symbols $D_1,D_2,D_3$ into these and so there are ${3\brace 2}=3$ possibilities:
$D_1\in B_1, \{D_2,D_3\}\in B_2$ (which we consider the same as placing $D_1\in B_2$ and $\{D_2,D_3\}\in B_1$).
$D_2\in B_1, \{D_1,D_3\}\in B_2$,
$D_3\in B_1, \{D_1,D_2\}\in B_2$.
If $B_1$ is labelled $1$ and $B_2$ is labelled $0$ we get the drawings $(1,0,0)$, $(0,1,0)$ and $(0,0,1)$. The other labeling gives the drawings $(0,1,1)$, $(1,0,1)$ and $(1,1,0)$. As noted above, this is indeed all good drawings in this case and the probability of getting a good drawing is $$\frac{{3\brace 2}2!}{2^3} = \frac{3}{4}.$$