Calculate people needed to have all birthdays

Question

for n people where n > 365, how can you calculate how many people you would need to expect that each of every distinct possible birthday would be had by at least one person at a given probability p?

In other words, you can calculate the odds that there are a distinct set of 365 birthdays among 366 (n) people (likely very small due to birthday collisions). How can you specify odds, say if p=.95, hold number of possible days constant (365), and solve for the number of people (n)?

And generalized for bin spaces other than 365?

Answer 1

Let's assume every year contains $k$ days indexed $1,2,\ldots,k$. Given a set $S$ of $n$ people, we can form a family $\{A_i\}_{i=1}^k$ of subsets of $S$ with person $p \in S$ belonging to $A_i$ if and only if $p$ was born on day $i$.

Correspondingly, we define a family of sets $\{A_i\}_{i=1}^k$ as "valid" if (a) each $A_i \subseteq S$, (b) $\cup_{i=1}^k A_i=S$ and (c) the $A_i$'s are pairwise disjoint. (Like an ordered set partition, but we allow the empty part.) Further, we define a valid family as "good" if no $A_i$ is empty.

The probability we seek is thus $$\frac{\text{nr good valid families}}{\text{nr valid families}}.$$

The number of valid families is $k^n$ (each person $p$ belongs to exactly one of $k$ sets).

The number of good valid families is the number of ordered partitions of $\{1,2,\ldots,n\}$ into $k$ parts. This number is given by $k!\,S(n,k)$, where $S(n,k)$ is the Stirling number of the second kind (the number of unordered partitions of $\{1,2,\ldots,n\}$ into $k$ parts).

The probability we seek is thus $$\frac{k!\, S(n,k)}{k^n}.$$

Answer 2

Using the principle of inclusion-exclusion, I find that the probability of hitting every possible birthdate with $n$ people is $$ p(n) = 1 - \sum_{j=1} ^{364} (-1)^{(j+1)} {\binom{365}{j}} \left( \frac{365-j}{365} \right)^n $$ This is kind of a pain to work with, since things are very large or small, but I'm pretty confident in the following values.

\begin{align*} n & p(n) \\ 365 \ & 1.45 \times 10^{-157} \\ 1000 \ & 1.71232 \times 10^{-12} \\ 2000 \ & 0.216119 \\ 2287 \ & 0.500370 \\ 3000 \ & 0.907229 \\ 3234 \ & 0.950081 \\ 3828 \ & 0.990018 \\ \end{align*}

I calculated this using PARI/GP with 1000 digits of precision.