# 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.

• I'm guessing 1-P(at least one day is no one's birthday) might be easier to calculate. – user_of_math Dec 16 '14 at 23:09

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

• I've tested empirically, and I made a solution using inclusion-exclusion, and you are correct, it is supposed to be 365! – maxb Dec 17 '14 at 1:20

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

• I've manually done the calculations for 5 people and 3 birthdays, and gotten 150/243 as my probability. If I use inclusion exclusion, and name my boxes A, B and C, with |A| being the number of ways to fill the boxes making sure that A isn't empty, then |A|=|B|=|C|=3^4, |A∩B|=3^3, and |A∩B∩C| = 3^2, yielding 3*3^4-3*3^3+3^2 = 171, making the probability 171/243 – maxb Dec 16 '14 at 23:45
• Since you have to subtract your expression from $1$, I would have $\displaystyle \sum_{m=0}^{365} (-1)^{m}{365 \choose m} \left(1 - \dfrac{m}{365}\right)^n$ as the answer to the original question. – Henry Dec 17 '14 at 1:08