OK math students, time for a lesson in
combinatorics. This problem is usually stated "
How many ways can we place P identical pigeons into H distinct holes?" However, I never liked that statement, because it displays a
gross ignorance about pigeons. If you ever look at a flock of pigeons in the city, you can easily see that no two are identical. They have wildly varying
colorization and
behavior from bird to bird. Furthermore, how many pigeons can you really cram into one hole? Eventually, you're going to have to resort to a
toilet plunger or something around your eighth bird. Whoever stated the pideonhole problem this way probably grew up in the country and never saw a real pigeon in his life. What I shall do, in keeping in the vein of some of my earlier nodes, is restate and solve the
real pigeonhole problem:
How many ways can we drill H identical holes into P distinct pigeons? Anyone who has ever lived in the city will empathize with me on this one.
This problem is a cousin of a similar problem in combinatorics: How many ways can we arrange P unique pigeons in a line? The answer, of course, is P!.
From this, we can then answer the question: How many ways can we choose P unique pigeons out of a pool of N? We solve this by visualizing our N pigeons arranged in a line, with a partition intersecting the line at position P. All pigeons to the left of the partition are selected. Now, the number of ways we can arrange all N pigeons is N!. However, this is not the answer, because there is a certain number of ways in which we can select the same P pigeons to the left of our partition, although the order of the pigeons will be different. In other words, if P = 5, N! considers the arrangement P1 P2 P3 P4 P5 to be distinct from P1 P3 P5 P4 P3, when for our purposes, they are the same. What we need to do is divide N! by the number of permutations of P, or P!.
We're not done yet. If we accounted for the rearrangement of the pigeons to the left of the partition, we need to account for the permutations of pigeons on the right of the partition. This is just the factorial of the number of pigeons we are not choosing. So the final answer to the choosing problem is equal to N!/(P!*(N-P)!).
How does this help us? We want to distribute identical holes among our pigeons, not pick pigeons from a pack. The answer is to reduce the problem at hand to the one already solved.
Imagine that we are creating a schedule to plan out our pigeon-puncturing in a professional manner. We have a long board filled with a number of peg holes, and a number P of pegs, that correspond to our pigeons. What we will do is place our pigeon pegs into the holes on the board, and the number of holes to the left of each peg, but to the right of the previous peg, will be equal to the number of holes received by the corresponding pigeon. Since we don't want to double count, we will always put P1 into the leftmost position, P2 to the right of P1, P3 to the right of P2, etc. This implies that the last peg will always take up the last position on the board, as we aren't going to let any of our planned holes go un-drilled.
How many holes do we need on this board? We can't just say H holes, because it is possible that by providence, some lucky pigeons may go un-penetrated, while their pathetic peers are punctured with a plethora of holes. So we need to add as many holes as there are pegs, to take this into account. The size of the board now is H+P holes.
SO:
The number ways to distribute our H holes among our P pigeons is now a question of how many ways we can select our P peg positions from our board of H + P holes. But not quite! Since the last peg is always in the last hole, we are really trying to choose (P-1) holes from (H+P-1) positions. If you scroll up, you'll see that the formula for this is: (H+P-1)!/((P-1)!*(H+P-1 - (P-1))!), or
(H+P-1)!/((P-1)!*H!)
Or, for the more boring question of sticking the pigeons into the holes, it's (H+P-1)!/((H-1)!*P!).