This question is rather difficult to describe clearly, so I will begin with an example. Suppose I have a 365 people in a room. The odds are very low that all these people have different birthdays. In fact, ignoring leap years and assuming that every birthday is equally likely, I estimated (using a program) that the most likely scenario is 231 distinct birthdays (with a probability of ~6.69%).
More abstractly, out of P people, what are the odds that there are exactly N distinct birthdays amongst them (ignoring leap years and assuming that every birthday is equally likely)? In my above example I used P=365 and I estimated the answer for N=231. I am curious if there is a general solution to the problem which could give an exact answer for all N and P.
For those who are interested, the program I created tries random combinations of birthdays and counts the number of unused birthdays. With it, I created a table of estimated probabilities for all N for P=365. Here is the most interesting part of the table:
242 - 1.1837375%
241 - 1.5966975%
240 - 2.0933325%
239 - 2.6695062%
238 - 3.3059700%
237 - 3.9824950%
236 - 4.6610425%
235 - 5.2969675%
234 - 5.8606362%
233 - 6.2995763%
232 - 6.5841737%
231 - 6.6932175%
230 - 6.6143263%
229 - 6.3563137%
228 - 5.9308837%
227 - 5.3896263%
226 - 4.7588988%
225 - 4.0879863%
224 - 3.4110800%
223 - 2.7697687%
222 - 2.1889950%
221 - 1.6793675%
220 - 1.2546263%
Answer
There are $\binom{365}{N}$ ways to select the $N$ birthdays. Then there are $P \brace N$ ways to select select which of the birthdays each person will have so that every of the selected birthdays is indeed the birthday of at least one person.
All in all there are $\binom{365}{N}{P \brace N}N!$ outcomes that give exactly $N$ distinct birthdays.
Hence the probability is:
$$\dfrac{\binom{365}{N}{P \brace N}N!}{365^P}$$
Here $\binom{n}{k}$ is the binomial coefficient and $n\brace k$ is the stirling number of the second kind.
No comments:
Post a Comment