Maths WorkshopMaths problems with full solutions
Exercise 608Combinatorics › Counting principlesM1Added 4 Nov 2026

The expected number of fixed points of a random permutation

#linearity of expectation#indicator variables#permutations

Statement

A permutation σ\sigma of {1,…,n}\{1,\dots,n\} is chosen uniformly at random. Let XX be its number of fixed points (σ(i)=i\sigma(i)=i).

  1. Show that E[X]=1\mathbb{E}[X]=1 for every n≥1n\ge1.
  2. Show that E[X(X−1)]=1\mathbb{E}[X(X-1)]=1 for every n≥2n\ge2, and deduce the variance of XX.
Hint

Write X=∑iIiX=\sum_i I_i where IiI_i is the indicator of the event "σ(i)=i\sigma(i)=i". Expectation is additive even when the IiI_i are dependent. For part 2, X(X−1)X(X-1) counts ordered pairs of distinct fixed points.

Show solutionHide solution

Solution

1. For each ii, σ(i)\sigma(i) is uniformly distributed on {1,…,n}\{1,\dots,n\}, so E[Ii]=Pr⁡[σ(i)=i]=1n\mathbb{E}[I_i]=\Pr[\sigma(i)=i]=\frac1n. By linearity,
E[X]=∑i=1n1n=1.\mathbb{E}[X]=\sum_{i=1}^n\frac1n=1.

2. X(X−1)=∑i≠jIiIjX(X-1)=\sum_{i\ne j}I_iI_j, the number of ordered pairs (i,j)(i,j), i≠ji\ne j, of fixed points. For i≠ji\ne j,
Pr⁡[σ(i)=i, σ(j)=j]=(n−2)!n!=1n(n−1).\Pr[\sigma(i)=i,\ \sigma(j)=j]=\frac{(n-2)!}{n!}=\frac1{n(n-1)}.
There are n(n−1)n(n-1) ordered pairs, so E[X(X−1)]=n(n−1)⋅1n(n−1)=1\mathbb{E}[X(X-1)]=n(n-1)\cdot\frac1{n(n-1)}=1.

Variance. E[X2]=E[X(X−1)]+E[X]=2\mathbb{E}[X^2]=\mathbb{E}[X(X-1)]+\mathbb{E}[X]=2, so Var⁡X=2−12=1\operatorname{Var}X=2-1^2=1.

Check. For n=5n=5 a computer enumeration of the 120120 permutations gives exactly E[X(X−1)]=1\mathbb{E}[X(X-1)]=1.

Remark. The fixed points are far from independent (if n−1n-1 points are fixed, so is the last one), yet linearity of expectation does not care. For n=2n=2: XX is 22 or 00 with probability 12\frac12 each.

Lesson. Write the quantity as a sum of indicators and use linearity of expectation: no independence needed.