Derangement of a permutation ($D_n$)

A permutation with no fixed points. Applying the inclusion-exclusion principle to the events that each element is fixed gives $D_n=n!{\sum }_{k=0}^n(-1{)}^k/k!$. Therefore $D_n/n!\to e^{-1}$, and the alternating-series remainder is at most $1/(n+1)!$.

// Destination: foundations-of-mathematics.bigb

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$.