Permutation statistics of products of random permutations. (English) Zbl 1290.60012
Summary: Given a permutation statistic \(\mathfrak{s}:\mathfrak{S}_n\to\mathbb R\), define the mean statistic \(\overline{\mathfrak{s}}\) as the class function giving the mean of \(\mathfrak{s}\) over conjugacy classes. We describe a way to calculate the expected value of \(\mathfrak{s}\) on a product of \(t\) independently chosen elements from the uniform distribution on a union of conjugacy classes \(\varGamma\subseteq\mathfrak{S}_n\). In order to apply the formula, one needs to express the class function \(\overline{\mathfrak{s}}\) as a linear combination of irreducible \(\mathfrak{S}_n\)-characters. We provide such expressions for several commonly studied permutation statistics, including the exceedance number, inversion number, descent number, major index and \(k\)-cycle number. In particular, this leads to formulae for the expected values of said statistics.
References:
| [1] | Alon, G.; Kozma, G., The probability of long cycles in interchange processes, Duke Math. J., 162, 1567-1585 (2013) · Zbl 1269.82041 |
| [2] | Bousquet-Mélou, M., The expected number of inversions after n adjacent transpositions, Discrete Math. Theor. Comput. Sci., 12, 65-88 (2010) · Zbl 1278.05014 |
| [3] | Diaconis, P.; Shahshahani, M., Generating a random permutation with random transpositions, Z. Wahrsch. Verw. Gebiete, 57, 159-179 (1981) · Zbl 0485.60006 |
| [4] | Eriksen, N., Expected number of inversions after a sequence of random adjacent transpositions – an exact expression, Discrete Math., 298, 155-168 (2005) · Zbl 1070.05001 |
| [5] | Eriksen, N.; Hultman, A., Estimating the expected reversal distance after a fixed number of reversals, Adv. in Appl. Math., 32, 439-453 (2004) · Zbl 1051.92029 |
| [6] | Eriksson, H.; Eriksson, K.; Sjöstrand, J., Expected number of inversions after a sequence of random adjacent transpositions, (Formal Power Series and Algebraic Combinatorics. Formal Power Series and Algebraic Combinatorics, Moscow, 2000 (2000), Springer-Verlag: Springer-Verlag Berlin), 677-685 · Zbl 0959.05005 |
| [7] | Fulman, J., The distribution of descents in fixed conjugacy classes of the symmetric groups, J. Combin. Theory Ser. A, 84, 171-180 (1998) · Zbl 0917.05006 |
| [8] | Ito, N., The spectrum of a conjugacy class of a finite group, Math. J. Okayama Univ., 26, 1-10 (1984) · Zbl 0581.20005 |
| [9] | Jackson, D. M., Some combinatorial problems associated with products of conjugacy classes of the symmetric group, J. Combin. Theory Ser. A, 49, 363-369 (1988) · Zbl 0682.20002 |
| [10] | Jönsson, A., Evolutionary fixed point distance problems (2009), University of Gothenburg, M.Sc. thesis |
| [11] | Lando, S. K.; Zvonkin, A. K., Graphs on Surfaces and Their Applications, Encyclopaedia Math. Sci., vol. 141 (2004), Springer-Verlag: Springer-Verlag Berlin · Zbl 1040.05001 |
| [12] | Sagan, B. E., The Symmetric Group. Representations, Combinatorial Algorithms, and Symmetric Functions, Grad. Texts in Math., vol. 203 (2001), Springer-Verlag: Springer-Verlag New York · Zbl 0964.05070 |
| [13] | Saloff-Coste, L., Random walks on finite groups, (Probability on Discrete Structures. Probability on Discrete Structures, Encyclopaedia Math. Sci., vol. 110 (2004), Springer-Verlag: Springer-Verlag Berlin), 263-346 · Zbl 1049.60006 |
| [14] | Sjöstrand, J., Expected length of a product of random reflections, Proc. Amer. Math. Soc., 140, 4369-4380 (2012) · Zbl 1280.20071 |
| [15] | Stanley, R. P., Enumerative Combinatorics, vol. 2 (1999), Cambridge University Press: Cambridge University Press New York · Zbl 0928.05001 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
