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

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

Combinatorial Proofs

Combinatorial Proofs.
Lucas' Theorem.
Ways To Count.
Geometric Proof of Wilson's Theorem.
Partitioning a Circle
A Minesweeper Theorem
Another Binomial Identity with Proofs
Counting Fat Sets
Counting Permutations with Fixed Points
Pythagorean Triples via Fibonacci Numbers

Permutations

Transpositions

Groups of Permutations

Sliders

Puzzles on graphs

Equation in Permutations

71935851