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