proof of recurrences for derangement numbers

The derangement numbers Dn satisfy two recurrence relations:

Dn=(n-1)[Dn-1+Dn-2] (1)
Dn=nDn-1+(-1)n (2)

These formulasMathworldPlanetmathPlanetmath 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


To derive the formulas algebraically, start with (2):

nDn-1 =n(n-1)!k=0n-1(-1)kk!=n!k=0n-1(-1)kk!=n!(-(-1)nn!+k=0n(-1)kk!)

and (2) follows. To derive (1), use (2) twice:

Dn =nDn-1+(-1)n=(n-1)Dn-1+Dn-1+(-1)n

Combinatorially, we can see (1) as follows. Write [n] for {1,2,,n}. Let π be any derangementMathworldPlanetmath of [n-1], i.e. a permutationMathworldPlanetmath containing no 1-cycles. Adding n before any of the n-1 elements of π produces a derangement of [n]. For fixed π, these are clearly all distinct, since 1 has a different successorMathworldPlanetmathPlanetmathPlanetmath in each case; for distinct π, these are equally obviously distinct. Thus each derangement of [n-1] corresponds to exactly n-1 derangements of [n]. Note also that since π had no 1-cycles that 1 is not a member of a transpositionMathworldPlanetmath (a 2-cycle).

Now let π be a derangement of any n-2 elements chosen from [n-1]. There are clearly (n-1)Dn-2 such derangements. If the omitted element in π is x, then adding the transposition (1x) to π 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