What is the expectation of the number of $k$-cycles in a randomly selected permutation of $[2k] = {1,2, . . . ,2k}$?
Asked
Active
Viewed 634 times
1 Answers
0
Use linearity of expectation. There are $\binom{2k}k$ different $k$-tuples that could form a $k$-cycle. For each of them, the probability that it forms a $k$-cycle is
$$ \frac{k-1}{2k}\cdot\frac{k-2}{2k-1}\cdots\frac1{k+2}\frac1{k+1}=\frac{k!(k-1)!}{(2k)!}\;, $$
where each factor is the probability that one of the elements is mapped appropriately in successively randomly choosing images for the elements.
Thus the expected number of cycles is $\displaystyle\binom{2k}k\frac{k!(k-1)!}{(2k)!}=\frac1k$.
Alternatively, you can reason like this: To count the number of permutations with a $k$ cycle, choose $k$ of the $2k$ elements, for a factor of $\binom{2k}k$, choose one of the cycles you can form from them, for a factor of $(k-1)!$, and choose one of the $k!$ permutations for the remaining elements. That makes $k!(k-1)!\binom{2k}k$ out of $(2k)!$ permutations, for an expected value of $1/k$. Now it might seem that we need a special treatment for the permutations that have two $k$-cycles, but a moment's reflection shows that these already get counted twice, as they should be.
For a solution using generating functions, see this answer.
