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