A couple of posts from a few years back give proofs of the formula for , 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:
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 ways. The remaining n-k elements cannot be mapped to themselves; i.e., they must be deranged. There are 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 .
Next, apply the binomial inversion formula. This comes in different forms. The one we will use says that for sequences and we have
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 ).
Applying the binomial inversion formula to Equation (1), with and , we get
where the second step reverses the summation.
1. Ronald L. Graham, Donald E. Knuth, and Oren Patashnik. Concrete Mathematics (2nd ed.), Addison-Wesley, 1994.