6 The pigeon hole principle

The pigeon hole principle is not really related to permutations or combinations. The pigeon hole principle states the following:

Assume there are $n$ pigeons and $r$ pigeon holes, and $n > r$ . If every pigeon is in a pigeon hole, then at least one pigeon hole has more than one pigeons.

The pigeon hole principle itself can be proven by contradiction. Let us make the assumption that $n > r$ (more pigeons than pigeon holes). The negation of the proposition states that every pigeon hole has at most one pigeon. Since there are only $r$ pigeon holes, then the number of pigeons, $n$ , must be less than or equal to $r$ , or $n \le r$ . This contradicts our assumption that $n > r$ because $(n > r) \wedge (n \le r)$ is a false proposition for all $n$ and all $r$ .