Bijective proof involving fixed points and symmetric group on $n$ letters?

Question

There is the following question here: If $S=\{1,2,\dots,n\}$ and $P_n(k)$ be the number of permutations of $S$ having $k$ fixed points, then $\sum_{k=0}^nk.P_{n}(k)=n!$:

Let $S = \{1,2,\dots,n\}$. Then $i \in S$ is said to be a fixed point of a permutation $p$ or $S$ if $p(i) = i$. Let $P_n(k) $ be the number of permutations of $S$ which have $k$ fixed point.

Prove that $\sum_{k=0}^nk\cdot P_{n}(k) = n!$.

There were some beautiful probabilistic proofs given. However, I'm wondering if there is a proof by coming up with an explicit bijection from the left-hand side to the symmetric group on $n$ letters.

Answer 1

Let $[n]=\{1,\dots,n\}$.

$\sum_{k=0}^nk\cdot P_n(k)$ enumerates ordered pairs $(\pi,x)$, such that $\pi:[n]\to [n]$ is a bijection, $x\in [n]$, and $\pi(x)=x$.

For any fixed $x$, there is a bijection between permutations $\pi$ for which $\pi(x)=x$, and permutations $\pi$ for which $\pi(n)=n$. Simply consider the permutation $\pi$ becomes when you rename $n$ to $x$, and $x$ to $n$.

Therefore, $\sum_{k=0}^n kP_n(k)$ enumerates ordered pairs $(\pi,x)$ where $\pi:[n]\to [n]$ is a permutation, $\pi(n)=n$ and $x\in [n]$.

It is obvious now that the number of such ordered pairs is $(n-1)!\cdot n$; there are $(n-1)!$ choices for a permutation which fixes $n$, and $n$ choices for $x$. Furthermore, it is easy to use a permutation $\pi$ of $[n-1]$, together with an $n$-way choice of $x$, to make bijectively permutation of $[n]$; simply insert the number $n$ at position $x$ in $\pi$. This completes the bijection from ordered pairs $(\pi,x)$ for which $\pi(x)=x$ to all permutations of $[n]$.

---

Here is an illustration of the bijection. We can think of $\sum_{k=0}^n kP_k(n)$ as counting permutations $\pi$ where one of the fixed points of $\pi$ is circled. We want a bijection between these "annotated permutations" and regular permutations. The bijection is this; with the annotated permutation written in one-line notation,

• Delete the circled element, $x$.

• Decrease all remaining numbers greater than $x$ by one, so all numbers are between $1$ and $n-1$,

• Insert $n$ at spot $x$ in the permutation.

Here is an example, where $n=5$:

$$ [3,\;\boxed{2},\;5,\;4,\;1]\to [3,\;5,\;4,\;1]\to [2,\;4,\;3,\;1]\to [2,\;\color{red}5,\;4,\;3,\;,1] $$

Answer 2

I think that this bijection is easier (it is actually the most elementary way of proving that the average number of fixed points is 1 regardless of $n$):

For any pair $(i,p)$ of a fixed point $i$ in a permutation $p$, let $p'$ the resulting permutation when you move $i$ to the last place. Conversely, for any permutation $p$, modify it by moving the last term $i$ to the $i$-th place, and if $p'$ is the resulting permutation consider the pair $(i,p')$.

It is clear that they are inverse maps.