## 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.
Advertisements
This entry was posted in combinatorics, derangements. Bookmark the permalink.

### 2 Responses to The Exponential Generating Function for the Derangement Numbers

1. amal says:

Here is a more elegant one, using The Exponential Formula: the egf for
$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))$.

• mzspivey says:

Thanks for this argument. It is elegant.