Formula for the number of derangements

Statement

Let $n$ be a natural number, and let $D_n$ be the number of derangements of an $n$-element set. Then $$D_n = n! \sum_{k=0}^{n} \frac{(-1)^k}{k!} = \sum_{k=0}^{n} (-1)^k \frac{n!}{k!}.$$

Remarks

For $n = 4$: $24 - 24 + 12 - 4 + 1 = 9$. The proof applies the inclusion–exclusion principle to the sets $A_i$ of permutations that fix $i$. The sum is a partial sum of the series of $e^{-1}$. Thus $D_n / n! \to 1/e$, and for $n \ge 1$, $D_n$ is the integer nearest to $n!/e$.

Explanations

L1 human

Start with all $n!$ permutations. Remove those that fix some point, add back those that fix two points, and so on. The result is the alternating sum in the formula.