Number of derangements

Definition

The derangement numbers $D_n$, for natural numbers $n$, are defined by the recursion $$D_0 = 1, \qquad D_1 = 0, \qquad D_{n+2} = (n + 1)\,(D_n + D_{n+1}).$$

Remarks

The first values, for $n = 0, 1, \dots, 6$, are $1, 0, 1, 2, 9, 44, 265$. The value $D_n$ is the number of derangements of an $n$-element set. The node the derangement numbers count derangements states this. Another notation is $!n$, the subfactorial of $n$.

Explanations

L1 human

The derangement numbers start $1, 0, 1, 2, 9, 44$. Each new number comes from the two before it: $D_4 = 3 \cdot (D_2 + D_3) = 3 \cdot 3 = 9$.