proof of recurrences for derangement numbers

The derangement numbers $D_n$ satisfy two recurrence relations:

$$D_n=(n-1)[D_{n-1}+D_{n-2}]$$ (1)

$$D_n=n{D}_{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):

$n{D}_{n-1}$ $=n(n-1)!{\displaystyle \sum _{k=0}^{n-1}}{\displaystyle \frac{{(-1)}^k}{k!}}=n!{\displaystyle \sum _{k=0}^{n-1}}{\displaystyle \frac{{(-1)}^k}{k!}}=n!\left(-{\displaystyle \frac{{(-1)}^n}{n!}}+{\displaystyle \sum _{k=0}^n}{\displaystyle \frac{{(-1)}^k}{k!}}\right)$

$=-{(-1)}^n+D_n$

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

$D_n$ $=n{D}_{n-1}+{(-1)}^n=(n-1)D_{n-1}+D_{n-1}+{(-1)}^n$

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

$=(n-1)(D_{n-1}+D_{n-2})$

Combinatorially, we can see (1) as follows. Write $[n]$ for $\{1,2,\mathrm{\dots },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 $(1x)$ 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
Canonical name	ProofOfRecurrencesForDerangementNumbers
Date of creation	2013-03-22 19:05:56
Last modified on	2013-03-22 19:05:56
Owner	rm50 (10146)
Last modified by	rm50 (10146)
Numerical id	4
Author	rm50 (10146)
Entry type	Result
Classification	msc 05A05
Classification	msc 05A15
Classification	msc 60C05