## Yet Another Nice Proof of the Derangements Formula

A couple of posts from a few years back give proofs of the formula for $D_n$, the number of derangements on n elements.  (A derangement is a permutation with no fixed points.)  Both proofs avoid the use of the principle of inclusion-exclusion, which is the standard method of proving the derangements formula.

This post contains another proof of the derangements formula, and I think this one is my favorite of the three.  It starts with a proof of the following identity:

$\displaystyle n! = \sum_{k=0}^n \binom{n}{k} D_{n-k} = \sum_{k=0}^n \binom{n}{k} D_k.$

Proof.  Both sides of the identity count the number of permutations on n elements.  The left side is straightforward.  For the middle formula, condition on the number of fixed points in the permutation.  To count the number of permutations with k fixed points, first choose which k of the n elements are to be mapped to themselves.  This can be done in $\binom{n}{k}$ ways.  The remaining n-k elements cannot be mapped to themselves; i.e., they must be deranged.  There are $D_{n-k}$ ways to do this.  Multiply these together and sum over all possible values of k to get the middle formula.  The right side just reverses the summation on the middle formula (i.e., replacing k with n-k), while using the binomial coefficient symmetry property $\binom{n}{k} = \binom{n}{n-k}$.

Next, apply the binomial inversion formula.  This comes in different forms.  The one we will use says that for sequences $f(n)$ and $g(n)$ we have

$\displaystyle f(n) = \sum_{k=0}^n \binom{n}{k} g(k) \iff g(n) = \sum_{k=0}^n \binom{n}{k} f(k) (-1)^{n-k}.$

Binomial inversion can be proved multiple ways.  My favorite uses exponential generating functions, but there are more direct proofs, too (see, for example, p. 193 of Concrete Mathematics [1]).

Applying the binomial inversion formula to Equation (1), with $f(n) = n!$ and $g(k) = D_k$, we get

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

where the second step reverses the summation.

References

1.  Ronald L. Graham, Donald E. Knuth, and Oren Patashnik.  Concrete Mathematics (2nd ed.), Addison-Wesley, 1994.