## The Exponential Generating Function for the Derangement Numbers

Recently I ran across a derivation of the exponential generating function for the derangement numbers that I like better than the ones I had seen before.  (Perhaps it’s standard, but it was new to me.)  It’s Problem 10 in Chapter 5 of the text [1] I’m currently using for combinatorics.

A derangement is a permutation with no fixed points.  One of the standard recurrences for the number of derangements $D_n$ on n elements is $D_n = n D_{n-1} + (-1)^n$, valid for $n \geq 1$.  The base case is $D_0 = 1$.  Now, multiply this recurrence by $x^n/n!$ and sum over n to get

$\displaystyle \sum_{n \geq 1} D_n \frac{x^n}{n!} = \sum_{n \geq 1} nD_{n-1} \frac{x^n}{n!} + \sum_{n \geq 1} (-1)^n \frac{x^n}{n!}$

$\displaystyle \implies \sum_{n \geq 0} D_n \frac{x^n}{n!} - 1 = x \sum_{n \geq 1} D_{n-1} \frac{x^{n-1}}{(n-1)!} + \sum_{n \geq 0} (-1)^n \frac{x^n}{n!} - 1$

$\displaystyle \implies G(x) = x G(x) + e^{-x}$

$\displaystyle \implies G(x) = \frac{e^{-x}}{1-x}$.

(I’ve also given this answer on math.SE.)

1. W. D. Wallis and J. C. George, Introduction to Combinatorics, CRC Press, 2011.
$c_n$ = the number of ways of creating a $n$-cycle, $n>1$,
is obviously $C(x) = \sum_{n>1} (n-1)! x^n/n! = -\ln(1-x)-x$. A dearangement can be considered as a set of such cycles, hence, by the EF, the egf counting dearangements is $\exp(C(x))$.