Consider the probability that no two people out of a group of will have matching birthdays out of
equally possible birthdays. Start with an arbitrary person's birthday, then note that the probability that the second person's
birthday is different is , that the third person's birthday is different from the first two is
,
and so on, up through the th person. Explicitly,
(1) 
(2) 
(3) 
(4) 
The probability can be estimated as
(5)  
(6) 
(7) 
In general, let denote the probability that a birthday is shared by exactly (and no more) people out of a group of
people. Then the probability that a birthday is shared by or more people is given by
(8) 
(9) 
where is a Binomial Coefficient, is a Gamma Function, and
is an
Ultraspherical Polynomial. This gives the explicit formula for as
(10) 

(11) 

(12) 
In general, can be computed using the Recurrence Relation
(13) 
A good approximation to the number of people such that is some given value can be given by solving the equation
(14) 
(15) 
The ``almost'' birthday problem, which asks the number of people needed such that two have a birthday within a day of each other,
was considered by Abramson and Moser (1970), who showed that 14 people suffice. An approximation for the minimum number of
people needed to get a 5050 chance that two have a match within days out of possible is given by
(16) 
See also Birthday Attack, Coincidence, Small World Problem
References
Abramson, M. and Moser, W. O. J. ``More Birthday Surprises.'' Amer. Math. Monthly 77, 856858, 1970.
Ball, W. W. R. and Coxeter, H. S. M. Mathematical Recreations and Essays, 13th ed. New York: Dover, pp. 4546, 1987.
Bloom, D. M. ``A Birthday Problem.'' Amer. Math. Monthly 80, 11411142, 1973.
Bogomolny, A. ``Coincidence.'' http://www.cuttheknot.com/do_you_know/coincidence.html.
Clevenson, M. L. and Watkins, W. ``Majorization and the Birthday Inequality.'' Math. Mag. 64, 183188, 1991.
Diaconis, P. and Mosteller, F. ``Methods of Studying Coincidences.'' J. Amer. Statist. Assoc. 84, 853861, 1989.
Feller, W. An Introduction to Probability Theory and Its Applications, Vol. 1, 3rd ed. New York: Wiley, pp. 3132, 1968.
Finch, S. ``Puzzle #28 [June 1997]: Coincident Birthdays.'' http://www.mathsoft.com/mathcad/library/puzzle/soln28/soln28.html.
Gehan, E. A. ``Note on the `Birthday Problem.''' Amer. Stat. 22, 28, Apr. 1968.
Heuer, G. A. ``Estimation in a Certain Probability Problem.'' Amer. Math. Monthly 66, 704706, 1959.
Hocking, R. L. and Schwertman, N. C. ``An Extension of the Birthday Problem to Exactly Matches.'' College Math. J. 17, 315321, 1986.
Hunter, J. A. H. and Madachy, J. S. Mathematical Diversions. New York: Dover, pp. 102103, 1975.
Klamkin, M. S. and Newman, D. J. ``Extensions of the Birthday Surprise.'' J. Combin. Th. 3, 279282, 1967.
Levin, B. ``A Representation for Multinomial Cumulative Distribution Functions.'' Ann. Statistics 9, 11231126, 1981.
McKinney, E. H. ``Generalized Birthday Problem.'' Amer. Math. Monthly 73, 385387, 1966.
Mises, R. von. ``Über Aufteilungsund BesetzungsWahrscheinlichkeiten.'' Revue de la Faculté des Sciences de l'Université d'Istanbul, N. S. 4, 145163, 1939. Reprinted in Selected Papers of Richard von Mises, Vol. 2 (Ed. P. Frank, S. Goldstein, M. Kac, W. Prager, G. Szegö, and G. Birkhoff). Providence, RI: Amer. Math. Soc., pp. 313334, 1964.
Riesel, H. Prime Numbers and Computer Methods for Factorization, 2nd ed. Boston, MA: Birkhäuser, pp. 179180, 1994.
Sayrafiezadeh, M. ``The Birthday Problem Revisited.'' Math. Mag. 67, 220223, 1994.
Sevast'yanov, B. A. ``Poisson Limit Law for a Scheme of Sums of Dependent Random Variables.'' Th. Prob. Appl. 17, 695699, 1972.
Sloane, N. J. A. A014088 and A033810 in ``An OnLine Version of the Encyclopedia of Integer Sequences.'' http://www.research.att.com/~njas/sequences/eisonline.html.
Stewart, I. ``What a Coincidence!'' Sci. Amer. 278, 9596, June 1998.
Tesler, L. ``Not a Coincidence!'' http://www.nomodes.com/coincidence.html.
© 19969 Eric W. Weisstein