## 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
```