Expected square of number of fixed points of permutation equals two

Statement

Suppose $n$ is a natural number. Consider the uniform distribution on the symmetric group of degree $n$ , i.e., the symmetric group on a set of size $n$ . For $n \geq 2$ , the expected value of the square of the number of fixed points for a permutation picked according to the uniform probability distribution equals $2$ .

Related facts

Similar facts

Expected number of fixed points of permutation equals one
In general, the expected value of the $k^{t h}$ power of the number of fixed points equals the Bell number $B (k)$ (the number of ways of partitioning a set of size $k$ into subsets) whenever $n \geq k$ .

Proof

For $1 \leq i \leq n$ , denote by $X_{i}$ the random variable that indicates whether $i$ is fixed by the permutation (so it's $1$ if $i$ is fixed and $0$ otherwise). We can show that:

$E [X_{i}^{2}] = E [X_{i}] = 1 / n$ , i.e., the probability that any particular element is fixed is $1 / n$ . Note that squaring makes no difference since the variables take values $0$ and $1$ .
For $i \neq j$ , $E [X_{i} X_{j}] = 1 / (n (n - 1))$ , i.e., the probability that two specific elements are fixed is $1 / (n (n - 1))$ .

The expected value of the square of the number of fixed points is $E [{(\sum_{i = 1}^{n} X_{i})}^{2}]$ . This simplifies to:

$\sum_{i = 1}^{n} E [X_{i}^{2}] + \sum_{1 \leq i, j \leq n} E [2 X_{i} X_{j}]$

The first of these becomes $n (1 / n) = 1$ . The second is a sum of $n (n - 1) / 2$ terms each of which is $2 / (n (n - 1))$ , which cancels out to give $1$ . The sum is $1 + 1 = 2$ as desired.

Note that this uses $n \geq 2$ ; when $n \leq 1$ , there are no cross terms and the expression $1 / (n (n - 1))$ is illegal as it involves division by zero.

Representation theory interpretation

The expected value of the square of the number of fixed points can be thought of as the norm of the linear representation of the symmetric group acting naturally on $n$ points. For $n \geq 2$ , this representation is the sum of two irreducible representations: the trivial representation and the standard representation, therefore the norm must equal $2$ .