# Asymptotic behaviour of fixed points in permutations

For any $n\in\mathbb{N}$ let $S_n$ denote the set of all permutations (bijective maps) $\pi:\{1,\ldots, n\} \to \{1,\ldots,n\}$. For $\pi \in S_n$ we set $$\text{fix}(\pi) = \{x\in \{1,\ldots, n\}: \pi(x) = x\}.$$

For any $n\in \mathbb{N}$ the expected value of the number of fixed points of a randomly chosen element of $S_n$ is $$E_n := \frac{1}{n!}\sum_{\pi\in\S_n} |\text{fix}(\pi)|.$$

Is the real sequence $(E_n)_{n\in\mathbb{N}}$ bounded? If not, what are the values of $\lim_{n\to\infty}\frac{E_n}{n}$ and $\lim_{n\to\infty}\frac{E_n}{\log n}$?

• Not only is it bounded, it is constant. The probability that a particular symbol is fixed by a random permutation is clearly $1/n$. By linearity of expectation, the expected number of symbols fixed is $n \cdot 1/n = 1$. (This also follows from Burnside's lemma.) – lambda Jul 18 '17 at 14:51

$E_n=1$, it is well known and easy to prove by double counting: for any specific point $x$, it is fixed for $(n-1)!$ permutations, now sum up by $x$.