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

Latest revision as of 17:52, 9 July 2025

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.

Slightly Clearer Solution

For any $k$ , if there are $p_n(k)$ permutations that have $k$ fixed points, then we know that each fixed point is counted once in the product $k \cdot p_n{k}$ . Therefore the given sum is simply the number of fixed points among all permutations of $\{ 1, \ldots , n \}$ . However, if we take any $x$ such that $1 \le x \le n$ and $x$ is a fixed point, there are $(n-1)!$ ways to arrange the other numbers in the set. Therefore our desired sum becomes $n \cdot (n-1)! = n!$ , so we are done.

Solution 2

The probability of any number $i$ where $1\le i\le n$ being a fixed point is $\frac{1}{n}$ . Thus, the expected value of the number of fixed points is $n\times \frac{1}{n}=1$ .

The expected value is also $\sum_{k=0}^{n} \frac{k \cdot p_n (k)}{n!}$ .

Thus, $\sum_{k=0}^{n} \frac{k \cdot p_n (k)}{n!}=1$ or $\sum_{k=0}^{n} k \cdot p_n (k) = n!.$

Solution 3

Call a permutation of $k$ objects a derangement if the permutation has $0$ fixed points. Consider $d_k$ the number of derangements of $k$ objects. Notice that $\sum_{k=0}^n {n \choose k}d_{n-k} = n!.$ Specifically, for $n$ objects being permuted, there are ${n \choose k}$ ways of holding $k$ points fixed and $d_{n-k}$ ways of deranging the other $n-k$ points. And summing these possibilities from $0$ points held fixed to $n$ points held fixed yields all $n!$ permutations of $n$ objects. On the other hand clearly $p_n(k) = {n \choose k} d_{n-k}$ . Since ${n \choose k} = \frac{n}{k}{n-1 \choose k-1}$ for $n \geq k \geq 1$ (taking ${0 \choose 0} = 1$ ) we find $\begin{align*} \sum_{k=0}^n k \cdot p_n(k) &= \sum_{k=1}^n k {n \choose k} d_{n-k} \\ &= n\sum_{k=1}^n {n-1 \choose k-1} d_{n-k} \\ &= n \sum_{k=0}^{n-1} {n-1 \choose k} d_{n-1-k} \\ &= n \cdot (n-1)! \end{align*}$ by our first equation as desired.

~not_detriti

Note

Maybe try and find a formula for $p_n(k)$ . It is quite elementary if you know basic properties of binomial coefficients and stuff. For instance, how many ways can we choose $k$ fixed points out of the $n$ total digits? Well, it can be done in $\binom{n}{k}$ ways. Now since we want exactly $k$ fixed points, what do we do with the remaining $(n-k)$ digits? Well we don't want any of those fixed. Clearly, of the $(n-k)$ spots left to put these $(n-k)$ points, we can put where it started off. So we have then $(n-k-1)$ spots to put one of the remaining $(n-k)$ points. Continuing on, we actually obtain a formula for $p_n(k)$ , namely, $\binom{n}{k}(n-k-1)(n-k-2)\dots1$ . Now we have to be careful, because now, what about for $k=n-1$ ? We see that no matter how we choose $n-1$ fixed points, we always have to put the remain point into the last possible spot, which was the spot it started on. Therefore, we must eliminate the case $k=n-1$ .

~th1nq3r

Note 2

$p_n(k)$ is actually $\binom{n}{k}d(n-k)$ , where $d$ is the derangement counter function (See https://oeis.org/A000166)

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

@@ Line 33: / Line 33: @@
 Thus, <cmath>\sum_{k=0}^{n} \frac{k \cdot p_n (k)}{n!}=1</cmath> or <cmath>\sum_{k=0}^{n} k \cdot p_n (k) = n!.</cmath>
+==Solution 3==
+Call a permutation of <math>k</math> objects a derangement if the permutation has <math>0</math> fixed points. Consider <math>d_k</math> the number of derangements of <math>k</math> objects. Notice that
+<cmath>
+\sum_{k=0}^n {n \choose k}d_{n-k} = n!.
+</cmath>
+Specifically, for <math>n</math> objects being permuted, there are <math>{n \choose k}</math> ways of holding <math>k</math> points fixed and <math>d_{n-k}</math> ways of deranging the other <math>n-k</math> points. And summing these possibilities from <math>0</math> points held fixed to <math>n</math> points held fixed yields all <math>n!</math> permutations of <math>n</math> objects. On the other hand clearly <math>p_n(k) = {n \choose k} d_{n-k}</math>. Since
+<cmath>
+{n \choose k} = \frac{n}{k}{n-1 \choose k-1}
+</cmath>
+for <math>n \geq k \geq 1</math> (taking <math>{0 \choose 0} = 1</math>) we find
+<cmath>
+\begin{align*}
+\sum_{k=0}^n k \cdot p_n(k) &= \sum_{k=1}^n k {n \choose k} d_{n-k} \\
+                      &= n\sum_{k=1}^n {n-1 \choose k-1} d_{n-k} \\
+                      &= n \sum_{k=0}^{n-1} {n-1 \choose k} d_{n-1-k} \\
+                      &= n \cdot (n-1)!
+\end{align*}
+</cmath>
+by our first equation as desired.
+~not_detriti
 == Note ==
-Maybe try and find a formula for <math>p_n(k)</math>. It is quite elementary if you know basic properties of binomial coefficients and stuff. For instance, how many ways can we choose <math>k</math> fixed points out of the <math>n</math> total digits? Well, it can be done in <math>\binom{n}{k}</math> ways. Now since we want exactly <math>\italic k</math> fixed points, what do we do with the remaining <math>(n-k)</math> digits? Well we don't want any of those fixed. Clearly, of the <math>(n-k)</math> spots left to put these <math>(n-k)</math> points, we can put where it started off. So we have then <math>(n-k-1)</math> spots to put one of the remaining <math>(n-k)</math> points. Continuing on, we actually obtain a formula for <math>p_n(k)</math>, namely, <math>\binom{n}{k}(n-k-1)(n-k-2)\dots1</math>. Now we have to be careful, because now, what about for <math>k=n-1</math>? We see that no matter how we choose <math>n-1</math> fixed points, we always have to put the remain point into the last possible spot, which was the spot it started on. Therefore, we must eliminate the case <math>k=n-1</math>.
+Maybe try and find a formula for <math>p_n(k)</math>. It is quite elementary if you know basic properties of binomial coefficients and stuff. For instance, how many ways can we choose <math>k</math> fixed points out of the <math>n</math> total digits? Well, it can be done in <math>\binom{n}{k}</math> ways. Now since we want exactly <math>k</math> fixed points, what do we do with the remaining <math>(n-k)</math> digits? Well we don't want any of those fixed. Clearly, of the <math>(n-k)</math> spots left to put these <math>(n-k)</math> points, we can put where it started off. So we have then <math>(n-k-1)</math> spots to put one of the remaining <math>(n-k)</math> points. Continuing on, we actually obtain a formula for <math>p_n(k)</math>, namely, <math>\binom{n}{k}(n-k-1)(n-k-2)\dots1</math>. Now we have to be careful, because now, what about for <math>k=n-1</math>? We see that no matter how we choose <math>n-1</math> fixed points, we always have to put the remain point into the last possible spot, which was the spot it started on. Therefore, we must eliminate the case <math>k=n-1</math>.
+~th1nq3r
+== Note 2 ==
+<math>p_n(k)</math> is actually <math>\binom{n}{k}d(n-k)</math>, where <math>d</math> is the derangement counter function (See https://oeis.org/A000166)
 {{IMO box|before=First question|num-a=2|year=1987}}
 [[Category:Olympiad Combinatorics Problems]]

Page

Toolbox

Search