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* * on *n* elements is , valid for . The base case is . Now, multiply this recurrence by and sum over *n* to get

.

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

- W. D. Wallis and J. C. George,
*Introduction to Combinatorics*, CRC Press, 2011.

Advertisements

Here is a more elegant one, using The Exponential Formula: the egf for

= the number of ways of creating a -cycle, ,

is obviously . A dearangement can be considered as a set of such cycles, hence, by the EF, the egf counting dearangements is .

Thanks for this argument. It is elegant.