MathDB

16

Part of 1987 IMO Shortlist

Problems(1)

Number of permutations

Source: IMO ShortList 1987 - Problem 16

8/19/2010
Let pn(k)p_n(k) be the number of permutations of the set {1,2,3,…,n}\{1,2,3,\ldots,n\} which have exactly kk fixed points. Prove that ∑k=0nkpn(k)=n!\sum_{k=0}^nk p_n(k)=n!.(IMO Problem 1)
Original formulation
Let SS be a set of nn elements. We denote the number of all permutations of SS that have exactly kk fixed points by pn(k).p_n(k). Prove:
(a) ∑k=0nkpn(k)=n! ;\sum_{k=0}^{n} kp_n(k)=n! \ ;
(b) ∑k=0n(k−1)2pn(k)=n!\sum_{k=0}^{n} (k-1)^2 p_n(k) =n!
Proposed by Germany, FR
probabilitycountingderangementpermutationsIMOIMO 1987IMO Shortlist