Counting Permutations with Fixed Points

Problem 1 at the 1987 IMO dealt with number $p_{n}(k)$ of permutations of an $n$-element set that leave exactly $k$ points fixed. According to the process of problem selection to be offered at an olympiad, a committee selects a short list of all submitted problems for further discussion. Six olympiad problems are then selected from those shortlisted. The shortlisted variant of Problem 1 contained two questions of which only one has been offered at the olympiad. I think that including both makes the problem more challenging and more curious. I am adding a relatively simple question that I feel make a combination of the three even more attractive. (It also reminds of a similar but much simpler result.)

$\begin{align}\displaystyle (1) && \sum_{k=0}^{n}p_{n}(k) &=n!\\ (2) && \sum_{k=0}^{n}kp_{n}(k) &=n!\\ (3) && \sum_{k=0}^{n}(k-1)^{2}p_{n}(k)&=n! \end{align}$

Problem (1) is my addition; problem (2) was offered at the Olympiad; problem (3) was shortlisted.

Proof

(1). A permutation of a set is just a 1-1 mapping of the set onto itself. Each of these has a certain number of fixed points. The meaning of this is that $\displaystyle\sum_{k=0}^{n}p_{n}(k)$ is just a way of counting all permutations of $n$-element set, say $\mathbb{N}_{n}$. From the first principles, the total number of permutations is known to be $n!.$

(2). To each permutation $\pi$ of $\mathbb{N}_{n}$ we assign a binary $n$-vector $(e_{1},e_{2},\ldots,e_{n}),$ where $e_{i}$ is either $1$ or $0$ depending on whether $\pi$ fixes $i,$ i.e., $e_{i}=1$ if and only if $\pi(i)=i.$ According to (1), there are $n!$ such vectors. Since exactly $p_{n}(k)$ of these vectors contain exactly $k$ $1\text{s},$ the sum in (2) counts the total number of $1\text{s}$ in all the assigned vectors.

On the other hand, for each $i,\space 1\le i\le n,$ there are exactly $(n-1)!$ permutations that leave $i$ fixed, i.e., exactly $(n-1)!$ of the vectors have $e_{1}=1.$ It follows that the total number of $1\text{s}$ is $n\cdot (n-1)!=n!,$ implying (2).

(3). Now, we again assign vectors to permutations but in a different way.

$(d_{1},d_{2},\ldots,d_{n})=k\cdot (e_{1},e_{2},\ldots,e_{n})$ is assigned to permutation $\pi,$ where, as in (2), $e_{i}=1$ if and only if $\pi(i)=i,$ and $k$ is the number of fixed points in $\pi.$

Let us count the sum $Z$ of all components $d_i$ for all $n!$ permutations.

There are $p_{n}(k)$ vectors with exactly $k$ components equal to $k,$ implying $\displaystyle Z=\sum_{k=0}^{n}k^{2}p_{n}(k).$

On the other hand, we may first compute the sum of all components $d_i,$ for a fixed $i.$ In fact, the value $d_{i}=k$ will occur exactly $p_{n-1}(k-1)$ times, so that the sum of the $d_{i}\text{'s}$ is

$\begin{align}\displaystyle \sum_{k=1}^{n}kp_{n-1}(k-1)&=\sum_{k=0}^{n-1}(k+1)p_{n-1}(k)\\ &=\sum_{k=0}^{n-1}kp_{n-1}(k)+\sum_{k=0}^{n-1}p_{n-1}(k)\\ &=2(n-1)!, \end{align}$

by (1) and (2). Summing over all $i\text{'s}$ gives $\displaystyle Z=\sum_{k=0}^{n}k^{2}p_{n}(k)=2n!.$ Combining that with the results of (1) and (2) yields

$\displaystyle\sum_{k=0}^{n}(k-1)^{2}p_{n-1}(k)=\sum_{k=0}^{n}k^{2}p_{n}(k)-2\sum_{k=0}^{n}k p_{n}(k)+\sum_{k=0}^{n}p_{n}(k)=n!.$

References

  1. D. Djukic et al, The IMO Compendium, Springer, 2011 (Second edition)

[an error occurred while processing this directive]

[an error occurred while processing this directive]

|Contact| |Front page| |Contents| |Algebra|

Copyright © 1996-2018 Alexander Bogomolny

[an error occurred while processing this directive]
[an error occurred while processing this directive]