IMO 1987 SL 16

Origin: FRG

Problem

Let S be a set of n elements. We denote the number of all permutations of S that have exactly k fixed points by pn(k). Prove: (a) n k=0 kpn(k) = n!; (b) n k=0(k −1)2pn(k) = n!.

Solution

We assume that S = {1, 2, . . ., n}, and use the obvious fact n  k=0 pn(k) = n! (0) (a) To each permutation \pi of S we assign an n-vector (e1, e2, . . . , en), where ei is 1 if i is a fixed point of \pi, and 0 otherwise. Since exactly pn(k) of the assigned vectors contain exactly k “1”s, the considered sum n k=0 kpn(k) counts all the “1”s occurring in all the n! assigned vectors. But for each i, 1 \leqi \leqn, there are exactly (n −1)! per- mutations that fix i; i.e., exactly (n −1)! of the vectors have ei = 1. Therefore the total number of “1”s is n \cdot (n −1)! = n!, implying n  k=0 kpn(k) = n!. (1) (b) In this case, to each permutation \pi of S we assign a vector (d1, . . . , dn) instead, with di = k if i is a fixed point of \pi, and di = 0 otherwise, where k is the number of fixed points of \pi. Let us count the sum Z of all components di for all the n! permuta- tions. There are pn(k) such vectors with exactly k components equal to k, and sums of components equal to k2. Thus, Z = n k=0 k2pn(k). On the other hand, we may first calculate the sum of all components di for fixed i. In fact, the value di = k > 0 will occur exactly pn−1(k −1) times, so that the sum of the di’s is n k=1 kpn−1(k −1) = n−1 k=0(k + 1)pn−1(k) = 2(n −1)!. Summation over i yields Z = n k=0 k2pn(k) = 2n!. (2) From (0), (1), and (2), we conclude that n  k=0 (k −1)2pn(k) = n  k=0 k2pn(k) −2 n  k=0 kpn(k) + n  k=0 pn(k) = n!. Remark. Only the first part of this problem was given on the IMO.