proof of recurrences for derangement numbers

The derangement numbers $D_{n}$ satisfy two recurrence relations:

 $\displaystyle D_{n}=(n-1)[D_{n-1}+D_{n-2}]$ (1) $\displaystyle D_{n}=nD_{n-1}+(-1)^{n}$ (2)

These formulas can be derived algebraically (working from the explicit formula for the derangement numbers); there is also an enlightening combinatorial proof of (1).

The exponential generating function for the derangement numbers is

 $D_{n}=n!\sum_{k=0}^{n}\frac{(-1)^{k}}{k!}$

To derive the formulas algebraically, start with (2):

 $\displaystyle nD_{n-1}$ $\displaystyle=n(n-1)!\sum_{k=0}^{n-1}\frac{(-1)^{k}}{k!}=n!\sum_{k=0}^{n-1}% \frac{(-1)^{k}}{k!}=n!\left(-\frac{(-1)^{n}}{n!}+\sum_{k=0}^{n}\frac{(-1)^{k}}% {k!}\right)$ $\displaystyle=-(-1)^{n}+D_{n}$

and (2) follows. To derive (1), use (2) twice:

 $\displaystyle D_{n}$ $\displaystyle=nD_{n-1}+(-1)^{n}=(n-1)D_{n-1}+D_{n-1}+(-1)^{n}$ $\displaystyle=(n-1)D_{n-1}+((n-1)D_{n-2}+(-1)^{n-1})+(-1)^{n}$ $\displaystyle=(n-1)(D_{n-1}+D_{n-2})$

Combinatorially, we can see (1) as follows. Write $[n]$ for $\{1,2,\ldots,n\}$. Let $\pi$ be any derangement of $[n-1]$, i.e. a permutation containing no $1$-cycles. Adding $n$ before any of the $n-1$ elements of $\pi$ produces a derangement of $[n]$. For fixed $\pi$, these are clearly all distinct, since $1$ has a different successor in each case; for distinct $\pi$, these are equally obviously distinct. Thus each derangement of $[n-1]$ corresponds to exactly $n-1$ derangements of $[n]$. Note also that since $\pi$ had no $1$-cycles that $1$ is not a member of a transposition (a $2$-cycle).

Now let $\pi$ be a derangement of any $n-2$ elements chosen from $[n-1]$. There are clearly $(n-1)D_{n-2}$ such derangements. If the omitted element in $\pi$ is $x$, then adding the transposition $(1~{}x)$ to $\pi$ produces a derangement of $[n]$, and all such derangements again are distinct from one another. Finally, since in this case $1$ is a member of a transposition, these derangements are distinct from those in the first group. This proves (1).

Title proof of recurrences for derangement numbers ProofOfRecurrencesForDerangementNumbers 2013-03-22 19:05:56 2013-03-22 19:05:56 rm50 (10146) rm50 (10146) 4 rm50 (10146) Result msc 05A05 msc 05A15 msc 60C05