I came across this result while doing some representation theory of the permutation group $S_n$
$$ \sum\limits_{\sigma \in S_n} (\mbox{number of fixed points of } \sigma)^2 = 2 n!$$
This can be proved very easily using the permutation representation of $S_n$. Does anyone know of a direct, more elementary way of proving this without using any representation theory?
Best Answer
You can use Burnside's lemma. $\text{Fix}(\pi)^2$ is the number of elements fixed by $\pi$ acting on $[n]^2$, where $[n] = \{ 1, 2, ... n \}$, so Burnside's lemma tells you that
$$\frac{1}{n!} \sum_{\pi \in S_n} \text{Fix}(\pi)^2$$
is the number of orbits of $S_n$ acting on $[n]^2$. But there are, by inspection, two such orbits: the ordered pairs $(a, b)$ where $a \neq b$, and the ordered pairs $(a, a)$.
(Exercise: generalize this argument to figure out $\displaystyle \frac{1}{n!} \sum_{\pi \in S_n} \text{Fix}(\pi)^k$.)