Kvant Math Problem 1077

Let $X(\sigma)$ denote the number of fixed points of a permutation $\sigma$ of an $n$ element set.

kvantmathematicsolympiad

Verified: no
Verdicts: SKIP + SKIP
Solve time: 1m44s
Source on kvant.digital

Problem

Let $p_n(k)$ be the number of permutations of a set of $n$ ($n\ge1$) elements that have exactly $k$ fixed points. Prove that:

  1. $$\textstyle\sum\limits_{k=0}^nk\cdot p_n(k)=0\cdot p_n(0)+1\cdot p_n(1)+\ldots+n\cdot p_n(n)=n!.$$
  2. $$\textstyle\sum\limits_{k=0}^n{}(k-1)^2p_n(k)=n!.$$

Note. A permutation of a finite set $S$ is a one-to-one mapping $f$ of the set $S$ onto itself; the number of all permutations of a set of $n$ elements is $n!=1\cdot2\cdot\ldots\cdot n$. An element $a$ of the set $S$ is called a fixed point of the permutation $f$ if $f(a)=a$.

International Mathematical Olympiad for School Students (1987)

Exploration

Let $X(\sigma)$ denote the number of fixed points of a permutation $\sigma$ of an $n$ element set. Then $p_n(k)$ counts permutations with $X(\sigma)=k$.

The first sum is

$$\sum_{k=0}^n k,p_n(k),$$

which is the total number of ordered pairs $(\sigma,a)$ such that $\sigma$ is a permutation and $a$ is a fixed point of $\sigma$. Counting such pairs directly may be easier.

Take a particular element $a$. The number of permutations fixing $a$ equals $(n-1)!$, since the remaining $n-1$ elements may be permuted arbitrarily. Since there are $n$ choices for $a$, the number of pairs $(\sigma,a)$ is

$$n\cdot (n-1)! = n!.$$

This suggests the first identity.

For the second identity, expand

$$(k-1)^2=k(k-1)-k+1.$$

Then

$$\sum_{k=0}^n (k-1)^2 p_n(k) = \sum_{k=0}^n k(k-1)p_n(k) - \sum_{k=0}^n k,p_n(k) + \sum_{k=0}^n p_n(k).$$

The last sum is $n!$, and the middle sum is $n!$ by part 1. Thus everything reduces to proving

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

This quantity counts triples $(\sigma,a,b)$ where $a$ and $b$ are distinct fixed points of $\sigma$. For a fixed ordered pair $(a,b)$ of distinct elements, the number of permutations fixing both is $(n-2)!$. There are $n(n-1)$ ordered pairs $(a,b)$, hence

$$n(n-1)(n-2)! = n!.$$

The only potentially delicate point is the interpretation of $k(k-1)$ as the number of ordered pairs of distinct fixed points of a permutation with exactly $k$ fixed points.

Problem Understanding

We are given the numbers $p_n(k)$ of permutations of an $n$ element set having exactly $k$ fixed points. We must prove two identities involving these numbers:

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

and

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

This is a Type B problem. The goal is to prove the stated identities.

The core difficulty is to recognize the sums as counts of suitable combinatorial objects and then count those objects in a second way.

Proof Architecture

Lemma 1. The quantity $\sum_{k=0}^n k,p_n(k)$ equals the number of pairs $(\sigma,a)$ where $\sigma$ is a permutation and $a$ is a fixed point of $\sigma$; for a permutation with $k$ fixed points there are exactly $k$ such pairs.

Lemma 2. The number of pairs $(\sigma,a)$ where $a$ is a fixed point of $\sigma$ equals $n!$; for each element $a$ there are $(n-1)!$ permutations fixing it.

Lemma 3. The quantity $\sum_{k=0}^n k(k-1)p_n(k)$ equals the number of triples $(\sigma,a,b)$ where $a$ and $b$ are distinct fixed points of $\sigma$; a permutation with $k$ fixed points contributes $k(k-1)$ ordered pairs $(a,b)$.

Lemma 4. The number of such triples equals $n!$; for each ordered pair of distinct elements $(a,b)$ there are $(n-2)!$ permutations fixing both.

The hardest point is Lemma 3, where one must count ordered pairs of distinct fixed points correctly.

Solution

Let $S$ be a set with $|S|=n$.

For the first identity, consider all pairs $(\sigma,a)$ where $\sigma$ is a permutation of $S$ and $a$ is a fixed point of $\sigma$.

If a permutation $\sigma$ has exactly $k$ fixed points, then it contributes exactly $k$ such pairs. Since there are $p_n(k)$ permutations with exactly $k$ fixed points, the total number of pairs $(\sigma,a)$ is

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

Now count the same set of pairs in another way. Fix an element $a\in S$. A permutation fixing $a$ may permute the remaining $n-1$ elements arbitrarily, hence there are

$$(n-1)!$$

such permutations. Since there are $n$ choices for $a$, the total number of pairs $(\sigma,a)$ equals

$$n\cdot (n-1)! = n!.$$

Comparing the two counts gives

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

This proves the first identity.

For the second identity, first write

$$(k-1)^2=k(k-1)-k+1.$$

Therefore

$$\sum_{k=0}^n (k-1)^2p_n(k) = \sum_{k=0}^n k(k-1)p_n(k) - \sum_{k=0}^n k,p_n(k) + \sum_{k=0}^n p_n(k).$$

Since the numbers $p_n(k)$ partition all permutations according to the number of fixed points,

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

By the first part,

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

Thus it remains to prove that

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

Consider all triples $(\sigma,a,b)$ where $\sigma$ is a permutation of $S$ and $a,b$ are distinct fixed points of $\sigma$.

A permutation with exactly $k$ fixed points contributes

$$k(k-1)$$

triples, because the first fixed point $a$ can be chosen in $k$ ways and the second fixed point $b$, distinct from $a$, in $k-1$ ways. Hence the number of triples is

$$\sum_{k=0}^n k(k-1)p_n(k).$$

Count the same triples differently. Fix an ordered pair $(a,b)$ of distinct elements of $S$. A permutation fixing both $a$ and $b$ may permute the remaining $n-2$ elements arbitrarily, so there are

$$(n-2)!$$

such permutations. The number of ordered pairs $(a,b)$ with $a\neq b$ is

$$n(n-1).$$

Therefore the total number of triples equals

$$n(n-1)(n-2)! = n!.$$

Hence

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

Substituting into the previous expansion yields

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

Both required identities have been proved.

This completes the proof.

∎

Verification of Key Steps

The first double counting relies on the fact that a permutation with exactly $k$ fixed points contributes exactly $k$ pairs $(\sigma,a)$. No pair is counted twice because the second component uniquely specifies the fixed point. No pair is omitted because every fixed point produces one pair.

For the second double counting, a permutation with exactly $k$ fixed points contributes $k(k-1)$ triples $(\sigma,a,b)$. The factor is not $\binom{k}{2}$ because the pair $(a,b)$ is ordered. For example, if the fixed points are $x,y,z$, the six ordered pairs are

$$(x,y),(x,z),(y,x),(y,z),(z,x),(z,y),$$

which equals $3\cdot2$.

When counting triples by fixing $(a,b)$ first, the number of admissible permutations is exactly $(n-2)!$. Once $a$ and $b$ are required to be fixed, every permutation of the remaining $n-2$ elements determines a unique permutation of the whole set, and every such permutation fixes both $a$ and $b$.

Alternative Approaches

Introduce the random variable $X$ equal to the number of fixed points of a uniformly chosen permutation of $n$ elements. Then

$$\sum_{k=0}^n k,p_n(k)=n!,\mathbb E[X].$$

Writing $X=I_1+\cdots+I_n$, where $I_i$ indicates that the $i$-th element is fixed, gives

$$\mathbb E[X] = \sum_{i=1}^n \mathbb E[I_i] = n\cdot \frac1n = 1.$$

Hence the first identity follows.

For the second identity, observe that

$$\sum_{k=0}^n (k-1)^2p_n(k) = n!,\mathbb E[(X-1)^2].$$

Using

$$\mathbb E[X]=1, \qquad \mathbb E[X(X-1)] = \sum_{i\ne j}\Pr(I_i=I_j=1) = n(n-1)\frac1{n(n-1)} = 1,$$

one obtains

$$\mathbb E[(X-1)^2] = \mathbb E[X(X-1)]-\mathbb E[X]+1 = 1.$$

Multiplying by $n!$ yields the second identity. The direct double counting proof is preferable because it stays entirely within elementary combinatorics and gives a transparent interpretation of each sum.