Exact Solutions of the Generalized Birthday Problem 

Bruce Levin

   Assume N people are in a room.  What is the smallest N such that there
is at least probability 0.5 that M people have the same birthday?  Assume
the birthday distribution is uniform over 365 days.

   Assume X~Mult(N;P) on k=365 categories, with P=(1/365,...,1/365) and 
calculate Prob(M;N) = P[max X[i] is at least M] using the exact method of 
Levin, "A representation for multinomial cumulative distribution functions", 
Annals of Statistics, 9:1123-1126 (1981).

                M             N             Prob(M;N)
              -----         -----           ---------
                1             1             1
                1             0             0

                2            23             0.507297234324
                2            22             0.475695307663

                3            88             0.511065110625
                3            87             0.499454850632

                4           187             0.502685373189
                4           186             0.495825706383

                5           313             0.501070475849
                5           312             0.496195571644

                6           460             0.50244941037
                6           459             0.498637523705

                7           623             0.502948948663
                7           622             0.499795687887

                8           798             0.500320275207
                8           797             0.497616714463

                9           985             0.500948416378
                9           984             0.498568067031

               10          1181             0.500931161057
               10          1180             0.498796176416

               11          1385             0.501001958747
               11          1384             0.499059528126

               12          1596             0.501166734721
               12          1595             0.499379622274

               13          1813             0.501104224633
               13          1812             0.499445407288

               14          2035             0.500348626509
               14          2034             0.498798065243

               15          2263             0.501295448239
               15          2262             0.499836197505