Proof of the formula for the number of derangements by inclusion–exclusion

Proof

We apply the inclusion–exclusion principle to the permutations that fix a given point.

1. Let $X$ be a set with $n$ elements. Choose a bijection $\beta : X \to [n]$, where $[n] = \set{1, \dots, n}$.
2. The map $\sigma \mapsto \beta \sigma \beta^{-1}$ is a bijection from the permutations of $X$ to those of $[n]$. Its inverse is $\tau \mapsto \beta^{-1} \tau \beta$.
3. We have $\beta \sigma \beta^{-1}(\beta(x)) = \beta(x)$ exactly when $\sigma(x) = x$. So this bijection sends derangements to derangements, in both directions.
4. By the bijection principle, it suffices to count the derangements of $[n]$.
5. If $n = 0$, the only permutation of $[0] = \varnothing$ is the empty map. It has no fixed point, so $D_0 = 1$. The formula gives $0! \cdot \frac{1}{0!} = 1$. From now on let $n \ge 1$.
6. Let $\Sigma$ be the set of permutations of $[n]$. By the number of permutations, $|\Sigma| = n!$.
7. For $i \in [n]$, let $A_i = \set{\sigma \in \Sigma : \sigma(i) = i}$. A permutation is a derangement exactly when it lies in no $A_i$.
8. So the derangements form the complement of $\bigcup_{i=1}^{n} A_i$ in $\Sigma$. By the complement principle, $D_n = n! - \left| \bigcup_{i=1}^{n} A_i \right|$.
9. Let $I \subseteq [n]$ have $k$ elements, and let $A_I = \bigcap_{i \in I} A_i$, the permutations that fix every point of $I$. We claim $|A_I| = (n - k)!$.
10. Let $\sigma \in A_I$ and $x \notin I$. If $\sigma(x) = i \in I$, then $\sigma(x) = \sigma(i)$ with $x \ne i$, against injectivity. So $\sigma$ maps $[n] \setminus I$ into itself.
11. This restriction is injective. It is also surjective: if $y \notin I$ and $y = \sigma(x)$, then $x \notin I$, since otherwise $y = \sigma(x) = x \in I$.
12. So restriction is a map from $A_I$ to the permutations of $[n] \setminus I$. Its inverse extends a permutation of $[n] \setminus I$ by the identity on $I$.
13. Hence $A_I$ is in bijection with the permutations of an $(n - k)$-element set. By the number of permutations, $|A_I| = (n - k)!$.
14. By the number of $k$-element subsets, there are $\binom{n}{k}$ sets $I$ with $k$ elements. By the factorial formula, $\binom{n}{k} (n - k)! = \frac{n!}{k!}$.
15. The inclusion–exclusion principle, with terms grouped by $k = |I|$, gives $$\left| \bigcup_{i=1}^{n} A_i \right| = \sum_{k=1}^{n} (-1)^{k+1} \binom{n}{k} (n - k)! = \sum_{k=1}^{n} (-1)^{k+1} \frac{n!}{k!}.$$
16. By step 8, and since $n! = (-1)^0 \frac{n!}{0!}$ by the definition of the factorial, $$D_n = n! - \sum_{k=1}^{n} (-1)^{k+1} \frac{n!}{k!} = \sum_{k=0}^{n} (-1)^k \frac{n!}{k!} = n! \sum_{k=0}^{n} \frac{(-1)^k}{k!}.$$