**1.** Let p_{n}(k) be the number of permutations of the set {1, 2, 3, ... , n} which have exactly k fixed points. Prove ∑_{0}^{n} (k p_{n}(k) ) = n!.

**First Solution**

We show first that the number of permutations of n objects with no fixed points is n!(1/0! - 1/1! + 1/2! - ... + (-1)^{n}/n!). This follows immediately from the law of inclusion and exclusion: let N_{i} be the number which fix i, N_{ij} the number which fix i and j, and so on. Then N_{0}, the number with no fixed points, is n! - all N_{i} + all N_{ij} - ... + (-1)^{n}N_{1...n}. But N_{i} = (n-1)!, N_{ij} = (n-2)! and so on. So N_{0} = n! ( 1 - 1/1! + ... + (-1)^{r}(n-r)!/(r! (n-r)!) + ... + (-1)^{n}/n!) = n! (1/0! - 1/1! + ... + (-1)^{n}/n!).

Hence the number of permutations of n objects with exactly r fixed points = no. of ways of choosing the r fixed points x no. of perms of the remaining n - r points with no fixed points = n!/(r! (n-r)!) x (n-r)! (1/0! - 1/1! + ... + (-1)^{n-r}/(n-r)! ). Thus we wish to prove that the sum from r = 1 to n of 1/(r-1)! (1/0! - 1/1! + ... + (-1)^{n-r}/(n-r)! ) is 1. We use induction on n. It is true for n = 1. Suppose it is true for n. Then the sum for n+1 less the sum for n is: 1/0! (-1)^{n}/n! + 1/1! (-1)^{n-1}/(n-1)! + ... + 1/n! 1/0! = 1/n! (1 - 1)^{n} = 0. Hence it is true for n + 1, and hence for all n.

*Comment*

This is a plodding solution. If you happen to know the result for no fixed points (which many people do), then it is essentially a routine induction.

**Second solution**

Count all pairs (x, s) where s is a permutation with x a fixed point of x. Clearly, if we fix x, then there are (n-1)! possible permutations s. So the total count is n!. But if we count the number of permutations s with exactly k fixed points, then we get the sum in the question.

*Comment*

This much more elegant solution is due to Gerhard Wöginger (email 24 Aug 99).

Solutions are also available in István Reiman, International Mathematical Olympiad 1959-1999, ISBN 189-8855-48-X.

© John Scholes

jscholes@kalva.demon.co.uk

30 Nov 1998