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

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s