---
tag: 03RSJXF728
kind: statement
role: theorem
name: Formula for the number of derangements
msc: [05A05]
uses: [0WFCGVMRRC, 0TH61JR04G, 03WY4HHMT1]
sources:
  - url: https://en.wikipedia.org/wiki/Derangement
    locator: Derivation by inclusion–exclusion principle
---

## Statement

Let $n$ be a natural number, and let $D_n$ be the number of [[derangements|0TH61JR04G]] 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|0FF7726C7P]] 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.