Editing Pigeonhole principle (section)

== Generalizations of the pigeonhole principle ==
{{Citations needed|section|date=February 2025}}
A probabilistic generalization of the pigeonhole principle states that if {{math|''n''}} pigeons are randomly put into {{math|''m''}} pigeonholes with uniform probability {{math|1/''m''}}, then at least one pigeonhole will hold more than one pigeon with probability

:<math>1 - \frac{(m)_n}{m^n}, </math>

where {{math|(''m'')<sub>''n''</sub>}} is the [[falling factorial]] {{math|''m''(''m'' &minus; 1)(''m'' &minus; 2)...(''m'' &minus; ''n'' + 1)}}. For {{math|1=''n'' = 0}} and for {{math|1=''n'' = 1}} (and {{math|''m'' > 0}}), that probability is zero; in other words, if there is just one pigeon, there cannot be a conflict. For {{math|''n'' > ''m''}} (more pigeons than pigeonholes) it is one, in which case it coincides with the ordinary pigeonhole principle. But even if the number of pigeons does not exceed the number of pigeonholes ({{math|''n'' ≤ ''m''}}), due to the random nature of the assignment of pigeons to pigeonholes there is often a substantial chance that clashes will occur. For example, if 2 pigeons are randomly assigned to 4 pigeonholes, there is a 25% chance that at least one pigeonhole will hold more than one pigeon; for 5 pigeons and 10 holes, that probability is 69.76%; and for 10 pigeons and 20 holes it is about 93.45%. If the number of holes stays fixed, there is always a greater probability of a pair when you add more pigeons. This problem is treated at much greater length in the [[birthday paradox]].

A further probabilistic generalization is that when a real-valued [[random variable]] {{math|''X''}} has a finite [[mean]] {{math|''E''(''X'')}}, then the probability is nonzero that {{math|''X''}} is greater than or equal to {{math|''E''(''X'')}}, and similarly the probability is nonzero that {{math|''X''}} is less than or equal to {{math|''E''(''X'')}}. To see that this implies the standard pigeonhole principle, take any fixed arrangement of {{math|''n''}} pigeons into {{math|''m''}} holes and let {{math|''X''}} be the number of pigeons in a hole chosen uniformly at random. The mean of {{math|''X''}} is {{math|''n''/''m''}}, so if there are more pigeons than holes the mean is greater than one. Therefore, {{math|''X''}} is sometimes at least 2.