## 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!}.$

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

### 5 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$.