Difference between revisions of "1987 IMO Problems/Problem 1"

 
m (Resources)
Line 29: Line 29:
 
== Resources ==
 
== Resources ==
  
* [[1985 IMO Problems]]
+
* [[1987 IMO Problems]]
 
* [http://www.artofproblemsolving.com/Forum/viewtopic.php?p=366512#p366512 Discussion on AoPS/MathLinks]
 
* [http://www.artofproblemsolving.com/Forum/viewtopic.php?p=366512#p366512 Discussion on AoPS/MathLinks]
  
  
 
[[Category:Olympiad Combinatorics Problems]]
 
[[Category:Olympiad Combinatorics Problems]]

Revision as of 21:51, 24 November 2006

Problem

Let $\displaystyle p_n (k)$ be the number of permutations of the set $\displaystyle \{ 1, \ldots , n \} , \; n \ge 1$, which have exactly $\displaystyle k$ fixed points. Prove that

$\sum_{k=0}^{n} k \cdot p_n (k) = n!$.

(Remark: A permutation $\displaystyle f$ of a set $\displaystyle S$ is a one-to-one mapping of $\displaystyle S$ onto itself. An element $\displaystyle i$ in $\displaystyle S$ is called a fixed point of the permutation $\displaystyle f$ if $\displaystyle f(i) = i$.)

Solution

The sum in questions simply counts the total number of fixed points in all permutations of the set. But for any element $\displaystyle i$ of the set, there are $\displaystyle (n-1)!$ permutations which have $\displaystyle i$ as a fixed point. Therefore

$\sum_{k=0}^{n} k \cdot p_n (k) = n!$,

as desired.


Alternate solutions are always welcome. If you have a different, elegant solution to this problem, please add it to this page.


Resources

Invalid username
Login to AoPS