IMO Shortlist 1987 problem 16
Dodao/la:
arhiva2. travnja 2012. Let
![p_n(k)](/media/m/2/6/7/26783f7dc38175c0f7653bda157c05f1.png)
be the number of permutations of the set
![\{1,2,3,\ldots,n\}](/media/m/a/2/e/a2e3516f0858f109273e21a4ae90b6ed.png)
which have exactly
![k](/media/m/f/1/3/f135be660b73381aa6bec048f0f79afc.png)
fixed points. Prove that
![\sum_{k=0}^nk p_n(k)=n!](/media/m/9/b/1/9b1227aa3ef8fa9deb506eee9b3c3b7f.png)
.(IMO Problem 1)
Original formulation
Let
![S](/media/m/c/6/3/c63593c3ec0773fa38c2659e08119a75.png)
be a set of
![n](/media/m/a/e/5/ae594d7d1e46f4b979494cf8a815232b.png)
elements. We denote the number of all permutations of
![S](/media/m/c/6/3/c63593c3ec0773fa38c2659e08119a75.png)
that have exactly
![k](/media/m/f/1/3/f135be660b73381aa6bec048f0f79afc.png)
fixed points by
![p_n(k).](/media/m/7/f/5/7f5149c38b8b2eb88d32c2479c5b0681.png)
Prove:
(a)
(b)
![\sum_{k=0}^{n} (k-1)^2 p_n(k) =n!](/media/m/1/a/c/1ac8f9a96e19fb136393b1e0348f7f25.png)
Proposed by Germany, FR
%V0
Let $p_n(k)$ be the number of permutations of the set $\{1,2,3,\ldots,n\}$ which have exactly $k$ fixed points. Prove that $\sum_{k=0}^nk p_n(k)=n!$.(IMO Problem 1)
Original formulation
Let $S$ be a set of $n$ elements. We denote the number of all permutations of $S$ that have exactly $k$ fixed points by $p_n(k).$ Prove:
(a) $\sum_{k=0}^{n} kp_n(k)=n! \ ;$
(b) $\sum_{k=0}^{n} (k-1)^2 p_n(k) =n!$
Proposed by Germany, FR
Izvor: Međunarodna matematička olimpijada, shortlist 1987