IMO 1987 Problem 1

Proposed by: -
Verified: yes
Verdicts: PASS + PASS
Solve time: 6m25s

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$.)

Exploration

For each permutation of ${1,\ldots,n}$, a fixed point is an index $i$ with $f(i)=i$. The quantity $p_n(k)$ counts permutations with exactly $k$ such indices. The expression $\sum_{k=0}^n k,p_n(k)$ is therefore the total number of fixed points across all permutations, because each permutation with $k$ fixed points contributes $k$ to the sum.

This suggests a double counting strategy: count the set of pairs $(\sigma,i)$ where $\sigma$ is a permutation and $i$ is a fixed point of $\sigma$. One approach is to fix $i$ first and count permutations fixing it, then sum over $i$. Another approach is to fix a permutation and count its fixed points.

The second perspective already suggests symmetry: every element $i\in{1,\ldots,n}$ should play an identical role, so each $i$ should be a fixed point in exactly $(n-1)!$ permutations. This would give a total of $n\cdot (n-1)! = n!$, matching the desired identity.

The key idea is to formalize this symmetry argument via counting ordered pairs $(\sigma,i)$ with $\sigma(i)=i$.

Problem Understanding

This is a Type B problem: a pure identity to prove about permutations and fixed points.

We consider all permutations of ${1,\ldots,n}$ and count how many fixed points they have in total, aggregated over all permutations. The goal is to show that this total equals $n!$.

Intuitively, each element $i$ has the same chance to be fixed across permutations. For a fixed $i$, exactly $(n-1)!$ permutations keep it fixed, since the remaining $n-1$ elements can be permuted arbitrarily. Summing over all $n$ elements gives $n(n-1)! = n!$, which explains why the identity should hold.

Proof Architecture

We introduce the set of all pairs $(\sigma,i)$ such that $\sigma$ is a permutation of ${1,\ldots,n}$ and $i$ is a fixed point of $\sigma$.

Lemma 1 states that the total number of such pairs equals $\sum_{k=0}^n k,p_n(k)$, since each permutation with $k$ fixed points contributes exactly $k$ pairs. This follows directly from partitioning permutations by number of fixed points.

Lemma 2 states that for each fixed $i$, the number of permutations fixing $i$ is $(n-1)!$, since the remaining elements can be permuted arbitrarily.

Lemma 3 states that summing over all $i$ yields $n(n-1)!$ total pairs.

The main argument equates the two counts of the same set of pairs. The symmetry argument in Lemma 2 is the most delicate conceptual step, although the proof itself is straightforward.

Solution

Lemma 1

The total number of pairs $(\sigma,i)$ such that $\sigma$ is a permutation of ${1,\ldots,n}$ and $i$ is a fixed point of $\sigma$ equals $\sum_{k=0}^n k,p_n(k)$.

Each permutation $\sigma$ has exactly $k$ fixed points if and only if it contributes exactly $k$ distinct pairs $(\sigma,i)$ satisfying $\sigma(i)=i$. The set of all permutations decomposes into disjoint classes indexed by $k$, and each class contributes exactly $k,p_n(k)$ pairs. Summing over all $k$ gives the total count.

This establishes a direct correspondence between fixed points counted individually and the weighted sum over permutations.

Lemma 2

Fix $i\in{1,\ldots,n}$. The number of permutations $\sigma$ such that $\sigma(i)=i$ equals $(n-1)!$.

If $\sigma(i)=i$, then $\sigma$ restricts to a permutation of the remaining set ${1,\ldots,n}\setminus{i}$, which has $n-1$ elements. Any permutation of these $n-1$ elements uniquely extends to a permutation of the full set fixing $i$, and every such permutation arises in this way. Since the number of permutations of a set of size $n-1$ equals $(n-1)!$, the claim follows.

This identifies the exact combinatorial freedom once a fixed point is prescribed.

Lemma 3

The total number of pairs $(\sigma,i)$ with $\sigma(i)=i$ equals $n(n-1)!$.

For each fixed $i$, there are $(n-1)!$ permutations fixing it by Lemma 2. Summing over all $n$ possible values of $i$ yields $n(n-1)!$.

This completes the second counting of the same set via fixing the fixed point first.

Main Argument

The set of pairs $(\sigma,i)$ with $\sigma(i)=i$ is counted in two ways. By Lemma 1 it equals $\sum_{k=0}^n k,p_n(k)$, and by Lemma 3 it equals $n(n-1)!$.

Equating these two expressions gives

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

Since $n(n-1)! = n!$, the identity follows:

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

This completes the proof. ∎

Verification of Key Steps

The crucial point is that counting fixed points via pairs $(\sigma,i)$ does not double count incorrectly, since each fixed point contributes exactly one distinct pair. Any mistake here would come from forgetting that multiplicity is encoded in the index $i$ rather than in permutations.

Another delicate point is Lemma 2, where the bijection between permutations fixing $i$ and permutations of the remaining $n-1$ elements must be exact. Any omission would occur if one assumed freedom without explicitly constructing the correspondence in both directions.

The final identification $n(n-1)! = n!$ depends on the factorial definition $n! = n\cdot (n-1)!$, and no additional assumptions are required.

Alternative Approaches

A probabilistic method assigns a uniform random permutation and computes the expected number of fixed points. Linearity of expectation gives that each position $i$ is fixed with probability $1/n$, so the expected number of fixed points is $1$. Multiplying by the total number of permutations $n!$ yields the same identity.

Another approach uses indicator variables $X_i$ for the event $\sigma(i)=i$, summing expectations over all $i$. This reframes the argument in probabilistic language but is equivalent in structure to the double counting proof.