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

Improve this question
$\endgroup$
1
  • 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
    Commented Jul 18, 2017 at 14:51

1 Answer 1

Reset to default
0
$\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$.

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .