- #1
tjaeger
- 8
- 0
So, I've been trying to solve a variation of the famous birthday problem. The problem is a more generalized version and goes like this: given n people, what is the probability at least k people share a birthday? You could also describe the problem as such: given m items randomly distributed into n bins (a probability 1/m of an item being put into a bin) what is the probability that at least one bin has at least k items. I've been searching the internet for ways to try to solve this problem, but I haven't had much luck. Is there a name for this type of problem or does anyone have any insights on this problem?
My first intuition on how to solve this problem would be to use a computer program to calculate all the ways the items can be distributed for n items and finding out how many of the ways have bins have bins with k or more items.
For instance, if n = 5 the items can be distributed as follows:
1+1+1+1+1, 2+1+1+1, 3+1+1, 2+2+1, 3+2, 4+1, 5
Then, for each of these partitions find out how many ways they can be spread out over m bins. However, this becomes infeasible quickly because for n=100 there are 190569292 possible partitions and for n=1000 there are 24061467864032622473692149727991 partitions.
My first intuition on how to solve this problem would be to use a computer program to calculate all the ways the items can be distributed for n items and finding out how many of the ways have bins have bins with k or more items.
For instance, if n = 5 the items can be distributed as follows:
1+1+1+1+1, 2+1+1+1, 3+1+1, 2+2+1, 3+2, 4+1, 5
Then, for each of these partitions find out how many ways they can be spread out over m bins. However, this becomes infeasible quickly because for n=100 there are 190569292 possible partitions and for n=1000 there are 24061467864032622473692149727991 partitions.