Tuesday, December 29, 2015

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


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. (n365)


P(Tn)=365!{n365}365n


Where, the braces indicate a Stirling number of the second kind.   Also represented as S(n,365).


No comments:

Post a Comment

analysis - Injection, making bijection

I have injection f:AB and I want to get bijection. Can I just resting codomain to f(A)? I know that every function i...