2
$\begingroup$

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.

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

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

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

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

$\endgroup$
  • $\begingroup$ 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 $\endgroup$ – maxb Dec 16 '14 at 23:45
  • $\begingroup$ 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. $\endgroup$ – Henry Dec 17 '14 at 1:08
1
$\begingroup$

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$%
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.