= Derangement recurrence
{title2=$d_n=(n-1)(d_{n-1}+d_{n-2})$}
The number $d_n$ of <derangements> of an $n$-element <set> satisfies $d_0=1$, $d_1=0$, $d_2=1$ and the displayed <recurrence relation> for $n\ge2$. Choose the image $j$ of a distinguished element, in $n-1$ ways. If those two elements form a two-cycle, removing them leaves $d_{n-2}$ choices. Otherwise remove the distinguished element from its longer <permutation cycle>, leaving a <derangement> on $n-1$ elements. The inverse operation inserts it immediately before $j$. Thus the two disjoint cases contribute $d_{n-2}+d_{n-1}$ for each $j$.
Back to article page
