Derangement recurrence ($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\ge 2$. 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$.