Pigeonhole and Inclusion-Exclusion - Key Proof

The derangement formula is one of the most elegant applications of the inclusion-exclusion principle, counting permutations where no element remains in its original position.

DefinitionDerangement

A derangement of a set $\{1, 2, \ldots, n\}$ is a permutation $\sigma$ such that $\sigma(i) \neq i$ for all $i \in \{1, 2, \ldots, n\}$ . The number of derangements of $n$ objects is denoted $D_n$ or $!n$ .

Theorem: The number of derangements of $n$ objects is: $D_n = n! \sum_{k=0}^{n} \frac{(-1)^k}{k!}$

Proof using Inclusion-Exclusion:

Let $S$ be the set of all permutations of $\{1, 2, \ldots, n\}$ , so $|S| = n!$ .

For each $i \in \{1, 2, \ldots, n\}$ , let $A_i$ be the set of permutations where element $i$ is in position $i$ (i.e., $\sigma(i) = i$ ).

We want to count permutations where no element is fixed, which is: $D_n = \left|\overline{A_1 \cup A_2 \cup \cdots \cup A_n}\right| = n! - |A_1 \cup A_2 \cup \cdots \cup A_n|$

We apply the inclusion-exclusion principle to compute $|A_1 \cup \cdots \cup A_n|$ : $|A_1 \cup \cdots \cup A_n| = \sum_{k=1}^{n} (-1)^{k+1} \sum_{|S|=k} \left|\bigcap_{i \in S} A_i\right|$

For any subset $S \subseteq \{1, 2, \ldots, n\}$ with $|S| = k$ , the intersection $\bigcap_{i \in S} A_i$ consists of permutations where all elements in $S$ are fixed in their original positions. The remaining $n-k$ elements can be arranged arbitrarily, giving $(n-k)!$ permutations.

The number of subsets $S$ with $|S| = k$ is $\binom{n}{k}$ .

Therefore: $\left|\bigcap_{i \in S} A_i\right| = (n-k)!$

and: $\sum_{|S|=k} \left|\bigcap_{i \in S} A_i\right| = \binom{n}{k} (n-k)!$

Substituting into the inclusion-exclusion formula: $|A_1 \cup \cdots \cup A_n| = \sum_{k=1}^{n} (-1)^{k+1} \binom{n}{k} (n-k)!$

$= \sum_{k=1}^{n} (-1)^{k+1} \frac{n!}{k!(n-k)!} (n-k)! = \sum_{k=1}^{n} (-1)^{k+1} \frac{n!}{k!}$

Therefore: $D_n = n! - \sum_{k=1}^{n} (-1)^{k+1} \frac{n!}{k!} = n! - \sum_{k=1}^{n} \frac{(-1)^{k+1} n!}{k!}$

$= n! - n! \sum_{k=1}^{n} \frac{(-1)^{k+1}}{k!} = n! \left(1 - \sum_{k=1}^{n} \frac{(-1)^{k+1}}{k!}\right)$

$= n! \left(1 + \sum_{k=1}^{n} \frac{(-1)^{k}}{k!}\right) = n! \sum_{k=0}^{n} \frac{(-1)^k}{k!}$

This completes the proof. $\square$

ExampleComputing Small Derangements

For small values of $n$ :

$D_0 = 1$ (by convention, the empty permutation)
$D_1 = 0$ (element 1 must be in position 1)
$D_2 = 1$ (only the swap: $(2,1)$ )
$D_3 = 2$ (permutations $(2,3,1)$ and $(3,1,2)$ )
$D_4 = 9$

We can verify $D_3$ using the formula: $D_3 = 3! \left(1 - 1 + \frac{1}{2} - \frac{1}{6}\right) = 6 \cdot \frac{1}{3} = 2$ ✓

Remark

As $n \to \infty$ , the sum $\sum_{k=0}^{n} \frac{(-1)^k}{k!}$ converges to $e^{-1} = 1/e$ . Therefore, $D_n \approx n!/e$ , and the probability that a random permutation is a derangement approaches $1/e \approx 0.368$ . This is the answer to the classic "hat check problem": if $n$ people check their hats and the hats are returned randomly, the probability that no one gets their own hat back approaches $1/e$ , independent of $n$ for large $n$ . There's also a useful recurrence relation: $D_n = (n-1)(D_{n-1} + D_{n-2})$ for $n \geq 2$ .