Expected value of letters of permutations with a given number of $k$-cycles

Abstract

In this paper, we study permutations $\pi \in S_n$ with exactly $m$ transpositions. In particular, we are interested in the expected value of $\pi (1)$ when such permutations are chosen uniformly at random. When $n$ is even, this expected value is approximated closely by $(n+1)/2$, with an error term that is related to the number isometries of the $(n/2-m)$-dimensional hypercube that move every face. Furthermore, when $k\mid n$, this construction generalizes to allow us to compute the expected value of $\pi (1)$ for permutations with exactly $m$ $k$-cycles. In this case, the expected value has an error term which is related instead to the number derangements of the generalized symmetric group $S(k,n/k-m)$. When $k$ does not divide $n$, the expected value of $\pi (1)$ is precisely $(n+1)/2$. Indirectly, this suggests the existence of a reversible algorithm to insert a letter into a permutation which preserves the number of $k$-cycles, which we construct.

21 pages