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

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 and initial conditions . (The recurrence relation can be proved combinatorially; see robjohn’s post or mine on the same question.) Then, subtract from both sides of the recurrence relation to get

Let , and the recurrence relation becomes . With , this recurrence is easy to solve, and we get .

Now, divide both sides of by to obtain

Let . Thus we have With this recurrence is also easy to solve, and we get

Multiplying both sides by yields the derangement formula:

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.

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.

Many thanks for the speedy reply!

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

Since , and , we get , , , and so forth. At this point we can see that, in general, .

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.