1. Let pn(k) be the number of permutations of the set {1, 2, 3, ... , n} which have exactly k fixed points. Prove ∑0n (k pn(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 Ni be the number which fix i, Nij the number which fix i and j, and so on. Then N0, the number with no fixed points, is n! - all Ni + all Nij - ... + (-1)nN1...n. But Ni = (n-1)!, Nij = (n-2)! and so on. So N0 = 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