In a group of k people, how likely is it that at least m of them share a birthday? Assume a year of d days, every person's birthday equally likely to be any day and independent of everybody else's, so all d ** k ways of giving birthdays to the (distinguishable) people are equally likely.
For m = 2 this is the classic birthday problem. For m = 3 and more, "all birthdays different" is no longer the complement, and there are far too many assignments to list.
Write crowded_day(k, d, m) that returns the probability, as a float, that some day is the birthday of at least m people.
Examples
Input: k = 4, d = 2, m = 3
Output: 0.625
Explanation: of the 16 equally likely assignments, the only ones with no day holding three or
more people split the group 2 and 2, and there are 6 of those (choose which 2 people share
the first day). So the probability is 1 - 6/16 = 0.625.
Input: k = 23, d = 365, m = 2
Output: 0.5072972343239854
Input: k = 88, d = 365, m = 3
Output: 0.5110651106247305
Constraints
1 <= k <= 200,1 <= d <= 500,2 <= m <= 6- floats are compared with a tolerance of
1e-6
Goals
- Generalise the birthday problem from "two share a day" to "m share a day"
- Count the complement by building the assignment of people to days one day at a time
- Keep huge counts exact with Python integers and divide only at the end