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: