## Generalized Birthday Problem (N Items in M Bins)

Suppose N items are randomly distributed into R bins so that each
item has a (independent) probability of 1/R of being put to any
particular bin. What is the probability that exactly K bins contain
exactly J items? This is sometimes called the generalized birthday
problem, because it can be expressed as a question about coincidences
between the birthdays of N people for R=365 days.
For any given distribution of items, let a_t denote the number of
containers with exactly t items. The probability of that particular
distribution is
N! R!
Pr = ---------------------------- (1)
N N a_t
R PROD (a_t)! (t!)
t=0
This can also be written in the form
M(N,j) R!
Pr{R,N,j} = ------------------ (2)
(R-s(N,j))! R^N
where s(N,j) is the number of occupied containers in the jth partition
of N, and M(N,j) is the multinomial coefficient called M_3 in Abramovitz
and Stegun.
For example, suppose we place N=5 objects into R=50 containers. The
five objects may be clustered in any of the following seven ways
j partition s(5,j) M(5,j)
--- ----------- ----- ------
1 5 1 1
2 4+1 2 5
3 3+2 2 10
4 3+1+1 3 10
5 2+2+1 3 15
6 2+1+1+1 4 10
7 1+1+1+1+1 5 1
The total number of ways that 5 items can be distributed into 50
containers is just R^N = 50^5. The other factors of (2) represent
the number of these distributions that give the jth partition.
These are listed in the table below for the case R=50, N=5:
number of
j partition distributions Pr{50,5,j)
--- ---------- ------------- ----------
1 5 50 .00000016
2 4+1 12250 .00003920
3 3+2 24500 .00007840
4 3+1+1 1176000 .00376320
5 2+2+1 1764000 .00564480
6 2+1+1+1 55272000 .17687040
7 1+1+1+1+1 254251200 .81360384
--------- ----------
total 312500000 1.00000000

Return to MathPages Main Menu