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

Revision as of 18:08, 18 November 2011

Problem

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

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

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

Solution

The sum in question simply counts the total number of fixed points in all permutations of the set. But for any element $i$ of the set, there are $(n-1)!$ permutations which have $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.

1987 IMO (Problems) • Resources
Preceded by First question	1 • 2 • 3 • 4 • 5 • 6	Followed by Problem 2
All IMO Problems and Solutions

@@ Line 13: / Line 13: @@
 == Solution ==
-The sum in questions simply counts the total number of fixed points in all permutations of the set.  But for any element <math>i </math> of the set, there are <math>(n-1)! </math> permutations which have <math>i </math> as a fixed point.  Therefore
+The sum in question simply counts the total number of fixed points in all permutations of the set.  But for any element <math>i </math> of the set, there are <math>(n-1)! </math> permutations which have <math>i </math> as a fixed point.  Therefore
 <center>

Page

Toolbox

Search

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

Revision as of 18:08, 18 November 2011

Problem

Solution