Chapter 8
COMBINATORICS
8.1 THE PIGEONHOLE PRINCIPLE
We know that for finite sets, | A | ≤ | B | iff there is an injection from A into B. The contrapositive of this fact is Corollary (The Pigeonhole Principle) If there are more pigeons than pigeonholes, then there must be at least two pigeons in one hole.
Formally, let A and B be finite sets. If | A | > | B | and f : A 
B, then there exist distinct elements a and a′ in A such that (a) = f (a′).
As a trivial application of the Pigeonhole Principle, suppose that there are three people in a room. The pigeonhole principle implies that two have the same gender. In this case, the “pigeons” are the three ...
Get Discrete Mathematics now with the O’Reilly learning platform.
O’Reilly members experience books, live events, courses curated by job role, and more from O’Reilly and nearly 200 top publishers.
