Probability of selecting each item at least once when sampling with replacement Sampling with replacement $N$ items from $K$, where $N \geq K$, what is the probability that each item in $K$ is selected at least once?
For example, from $10,000$ individuals, what is the probability that every birthday is represented? (assume each birthday $p = 1/365$)
I've been using simulations to work this out, but would like to know the general solution. Thanks!
 A: For completeness's sake, here's an answer and some references.
Because each sample has equal probability, it suffices to count the number of samples with the desired property and divide by the total number of samples.


*

*Let's tackle the denominator first, because it's easier to count.  A "sample" can be uniquely described by the sequence of results.  Abstractly, that's a function $s$ from $\{1,2,\ldots,N\}$ to the set of items or, equivalently, an $N$-vector with coefficients in a set of $K$ things.  Because there are $K$ ways to specify each coefficient, the total number of samples equals $K^N$.

*The numerator is the number of samples in which each item appears at least once.  In mathematical terminology, $s$ is a surjection (or "onto" function).  Combinatorics texts explain how to count surjections and they provide formulas.  For instance, Wagner's Basic Combinatorics covers this on the first page of Chapter 9 and the first page of Chapter 10.  The upshot is that the numerator equals $K!$ times the Stirling number of the second kind, $S(N,K)$.
The desired probability therefore equals $K! S(N,K) /K^N$.
This technique of first reducing a probability to a counting problem and then expressing that counting problem in terms of a set of functions with specific properties gives a general method for characterizing problems of this type. (Gian-Carlo Rota's Twelvefold Way provides a unified approach to such problems.) With such a characterization in hand you can often then look up the answer.
As an example of this particular formula, consider the case $K=2$ and $N=4$. We can look up or compute that $S(N,K)=7$, whence the probability is $2! \times 7 / 2^4$ = $14/16$. We can check by enumerating all samples of size $4$ from a set of $2$ items, such as $\{A,B\}$:
$AAAA, AAAB, AABA, AABB, ABAA, ABAB, ABBA, ABBB, BAAA, BAAB, BABA, BABB, BBAA, BBAB, BBBA, BBBB.$
Of these, the first and last omit one of the items but the remaining $14$ out of the $16$ samples include both.
Finally, the question asks for the answer when $N=10^4$ and $K=365$. It differs from $1$ by $4.44104 \times 10^{-10}$.  It is interesting to see how this probability depends on $N$ (keeping $K$ fixed at $365$):

