= Solution
The initial values are \b[$d_1=0$ and $d_2=1$]: one element cannot move, while two elements must be swapped.
For $n\ge3$, fix one distinguished element, called $n$, and choose its image $j\ne n$, in $n-1$ ways. If $n,j$ form a two-cycle, deleting them leaves an arbitrary <derangement> on the other $n-2$ elements, giving $d_{n-2}$ choices.
Otherwise the <permutation cycle> containing $n$ has length at least three. Remove $n$ from that cycle, joining its predecessor directly to $j$. No fixed point is created because the predecessor is not $j$. This gives a <derangement> on $n-1$ elements. Conversely, any such <derangement> uniquely recovers the original one by inserting $n$ immediately before $j$ in its cycle. This case contributes $d_{n-1}$ choices for each $j$.
The two cases are disjoint and exhaustive, so the <derangement recurrence> is
$$
\boxed{d_n=(n-1)(d_{n-1}+d_{n-2}).}
$$
Back to article page
