2
$\begingroup$

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}$?

| cite | improve this question | | | | |
$\endgroup$
  • 5
    $\begingroup$ 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.) $\endgroup$ – lambda Jul 18 '17 at 14:51
2
$\begingroup$

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

| cite | improve this answer | | | | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.