# 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 |