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

2021/12/10 by Kagey, Peter
#05A05 #Combinatorics (math.CO) #FOS: Mathematics #Probability (math.PR)

paper · doi:10.48550/arxiv.2112.05281

Abstract

In this paper, we study permutations π∈ S_n with exactly m transpositions. In particular, we are interested in the expected value of π(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 | n, this construction generalizes to allow us to compute the expected value of π(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 π(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.

Related

• On the expected number of commutations in reduced words
• The Number of k-Cycles In a Family of Restricted Permutations
• The variance of the Stirling cycle numbers
• The Cycle Structure of Permutations Without Long Cycles
• The number of cycles of specified normalized length in permutations