Probability that n people collectively occupy all 365 birthdays
The problem is quite simple to formulate. If you have a large group of people (n > 365), and their birthdays are uniformly distributed over the year (365 days), what's the probability that every day of the year is someone's birthday?
I am thinking that the problem should be equivalent to finding the number of ways to place n unlabeled balls into k labeled boxes, such that all boxes are non-empty, but C((n-k)+k-1, (n-k))/C(n+k-1, n) (C(n,k) being the binomial coefficient) does not yield the correct answer.
Birthday Coverage is basically a Coupon Collector's problem.
You have $n$ people who drew birthdays with repetition, and wish to find the probability that all $365$ different days were drawn among all $n$ people. ($n\geq 365$)
$$\mathsf P(T\leq n)= 365!\; \left\lbrace\begin{matrix}n\\365\end{matrix}\right\rbrace\; 365^{-n} $$
Where, the braces indicate a Stirling number of the second kind. Also represented as $\mathrm S(n, 365)$.
Just for sake of illustration I give some numerical results:
- for $1000$ people we get a propability of $1.7*10^{-10}$% to exhaust all birthdays
- for $1500$ people we get $0.2$%
- for $2000$ people we get $22$%
- for $2286$ people we get $50$%
- for $2500$ people we have $68$%
- for $3000$ people we have $91$%
- for $4000$ people we have $99$%
Use the inclusion-exclusion principle. For a given set of $m$ days, the probability that nobody has a birthday on those days is $(1 - m/365)^n$.
EDIT: There are $365 \choose m$ such sets. So the probability that there is at least one day with no birthdays is $$\sum_{m=1}^{364} (-1)^{m-1}{365 \choose m} (1 - m/365)^n $$