## A Nice Proof of the Derangements Formula

A derangement is a permutation in which none of the elements is mapped to itself.  The formula for the number of derangements $D_n$ on $n$ elements is

$\displaystyle D_n = n! \sum_{k=0}^n \frac{(-1)^k}{k!}.$

This formula is normally proved using inclusion-exclusion (and, in fact, it is one of the classic illustrations of inclusion-exclusion).

A few days ago on math.SE robjohn posted a nice proof of this formula that I had never seen before.  It starts with the recurrence relation $D_n = (n-1)(D_{n-1} + D_{n-2})$ and initial conditions $D_0 = 1, D_1 = 0$.  (The recurrence relation can be proved combinatorially; see robjohn’s post or mine on the same question.)  Then, subtract $nD_{n-1}$ from both sides of the recurrence relation to get

$\displaystyle D_n - nD_{n-1} = -(D_{n-1} - (n-1)D_{n-2}).$

Let $A_n = D_n - n D_{n-1}$, and the recurrence relation becomes $A_n = - A_{n-1}$.  With $A_0 = 1$, this recurrence is easy to solve, and we get $D_n - n D_{n-1} = A_n = (-1)^n$.

Now, divide both sides of $D_n - n D_{n-1} = (-1)^n$ by $n!$ to obtain

$\displaystyle \frac{D_n}{n!} - \frac{D_{n-1}}{(n-1)!} = \frac{(-1)^n}{n!}.$

Let $B_n = \frac{D_n}{n!}$.  Thus we have $B_n = B_{n-1} + \frac{(-1)^n}{n!}.$  With $B_0 = 1$ this recurrence is also easy to solve, and we get

$\displaystyle \frac{D_n}{n!} = B_n = \sum_{k=0}^n \frac{(-1)^k}{k!}.$

Multiplying both sides by $n!$ yields the derangement formula:

$\displaystyle D_n = n! \sum_{k=0}^n \frac{(-1)^k}{k!}.$

Advertisements
This entry was posted in combinatorics, derangements, permutations, recurrence relations. Bookmark the permalink.

### 6 Responses to A Nice Proof of the Derangements Formula

1. Dave Perkins says:

Thanks for providing extra detail that the original math.SE posts left out. Very lovely proof! If I wanted to use the proof in a paper, do you know how I’d cite it? I can’t find the original author of this proof and wonder if you happen to know it.

• mzspivey says:

I haven’t seen the proof in a book or paper before. I think it would be fine to cite the original math.SE post or even mine here using some standard format for citing web pages. You could also ask robjohn on math.SE if he got it from some other source.

• Dave Perkins says:

Many thanks for the speedy reply!

2. John says:

You wrote that the recurrence is easy to solve. Could you please elaborate on how you arrived at A_n = (-1)^n? Thanks.

• mzspivey says:

Since $A_n = -A_{n-1}$, and $A_0 = 1$, we get $A_1 = -A_0 = -1$, $A_2 = -A_1 = 1$, $A_3 = -A_2 = -1$, and so forth. At this point we can see that, in general, $A_n = (-1)^n$.

3. William P. G. SHAW says:

The derangement formula is the very thing I need to make strong passwords by mapping the upper and lower case alphabet, numerals zero to nine [excluding one which is indistiguishable from lower case L and other indistiguishables] and a few non-alphabetic characters such as £*%, about sixty-seven in all to a derangement of the integers from one to sixty-seven.
In using the recursive formula, the initial cases D[0] and D[1] need to be stated clearly.