---
tag: 67S4PPN54V
kind: proof
name: Proof of the formula for the number of derangements by inclusion–exclusion
msc: [05A05]
proves: 03RSJXF728
uses: [0TH61JR04G, 0BQMWCNS8S, 0FF7726C7P, 0CEBCS0E0E, 0BFMR2FQ8B, 033KTKKRV6, 03QC59M99B, 0WFCGVMRRC, 0GV2573FP4]
sources:
  - url: https://en.wikipedia.org/wiki/Derangement
    locator: Derivation by inclusion–exclusion principle
---

## Proof

We apply the [[inclusion–exclusion principle|0FF7726C7P]] 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|0BQMWCNS8S]] 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|0TH61JR04G]] to derangements, in both directions.
4. By the [[bijection principle|0GV2573FP4]], 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|0CEBCS0E0E]], $|\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|03QC59M99B]], $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|0BFMR2FQ8B]], there are $\binom{n}{k}$ sets $I$ with $k$ elements. By the [[factorial formula|033KTKKRV6]], $\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|0WFCGVMRRC]],
$$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!}.$$

## Idea

A derangement is a permutation that avoids every set $A_i$ of permutations fixing $i$. The permutations that fix $k$ given points are just the permutations of the other $n - k$ points, so inclusion–exclusion has easy terms. They simplify to $(-1)^k n!/k!$.