# Calculate people needed to have all birthdays

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?

-
related to the coupon collector problem –  Peter Feb 1 '14 at 1:20
I might be missing something, but I think it is simply $\frac{\binom{n}{365}}{365^n}$, where $n$ is the number of people. For $n=366$ the probability is given by Wolfram to be $5.8*10^{-936}$. –  Peter Feb 1 '14 at 1:22
related but not the same as the birthday paradox. birthday paradox is the odds of there being at least one collision. This is number expected for all birthdays to be used (of which number of collisions would factor into) –  ʞɔıu Feb 1 '14 at 1:24
@Peter: now I want to solve for n given p –  ʞɔıu Feb 1 '14 at 1:30

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}.$$

-
Which, incidentally, nicely passes a simple sanity check, because $S(n,k)$ is asymptotically $k^n/k!$. –  John Moeller Feb 1 '14 at 4:09

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.

-