Counting inversions and descents of random elements in finite Coxeter groups
Authors:
Thomas Kahle and Christian Stump
Journal:
Math. Comp. 89 (2020), 437-464
MSC (2010):
Primary 20F55; Secondary 05A15, 05A16, 60F05
DOI:
https://doi.org/10.1090/mcom/3443
Published electronically:
May 9, 2019
MathSciNet review:
4011551
Full-text PDF
View in AMS MathViewer
Abstract | References | Similar Articles | Additional Information
Abstract: We investigate Mahonian and Eulerian probability distributions given by inversions and descents in general finite Coxeter groups. We provide uniform formulas for the means and variances in terms of Coxeter group data in both cases. We also provide uniform formulas for the double-Eulerian probability distribution of the sum of descents and inverse descents. We finally establish necessary and sufficient conditions for general sequences of Coxeter groups of increasing rank under which Mahonian and Eulerian probability distributions satisfy central and local limit theorems.
- Edward A. Bender, Central and local limit theorems applied to asymptotic enumeration, J. Combinatorial Theory Ser. A 15 (1973), 91–111. MR 375433, DOI https://doi.org/10.1016/0097-3165%2873%2990038-1
- Sara C. Billey, Matjaž Konvalinka, T. Kyle Petersen, William Slofstra, and Bridget E. Tenner, Parabolic double cosets in Coxeter groups, Electron. J. Combin. 25 (2018), no. 1, Paper No. 1.23, 66. MR 3785002, DOI https://doi.org/10.37236/6741
- Patrick Billingsley, Probability and measure, John Wiley & Sons, New York-Chichester-Brisbane, 1979. Wiley Series in Probability and Mathematical Statistics. MR 534323
- Anders Björner and Francesco Brenti, Combinatorics of Coxeter Groups, vol. 231, Springer Science & Business Media, 2006.
- Petter Brändén, Unimodality, log-concavity, real-rootedness and beyond, Handbook of enumerative combinatorics, Discrete Math. Appl. (Boca Raton), CRC Press, Boca Raton, FL, 2015, pp. 437–483. MR 3409348
- Francesco Brenti, Log-concave and unimodal sequences in algebra, combinatorics, and geometry: an update, Jerusalem combinatorics ’93, Contemp. Math., vol. 178, Amer. Math. Soc., Providence, RI, 1994, pp. 71–89. MR 1310575, DOI https://doi.org/10.1090/conm/178/01893
- Francesco Brenti, $q$-Eulerian polynomials arising from Coxeter groups, European J. Combin. 15 (1994), no. 5, 417–441. MR 1292954, DOI https://doi.org/10.1006/eujc.1994.1046
- E. Rodney Canfield, Svante Janson, and Doron Zeilberger, The Mahonian probability distribution on words is asymptotically normal, Adv. in Appl. Math. 46 (2011), no. 1-4, 109–124. Supplementary material available online. MR 2794017, DOI https://doi.org/10.1016/j.aam.2009.10.001
- Sourav Chatterjee and Persi Diaconis, A central limit theorem for a new statistic on permutations, Indian J. Pure Appl. Math. 48 (2017), no. 4, 561–573. MR 3741694, DOI https://doi.org/10.1007/s13226-017-0246-3
- Chak-On Chow and Toufik Mansour, Asymptotic probability distributions of some permutation statistics for the wreath product $C_r\wr \mathfrak S_n$, Online J. Anal. Comb. 7 (2012), 14. MR 3016122
- The Sage Developers, SageMath, the Sage Mathematics Software System (Version 8.1), 2017. http://www.sagemath.org.
- Valentin Féray, Pierre-Loïc Méliot, and Ashkan Nikeghbali, Mod-$\straightphi $ convergence, SpringerBriefs in Probability and Mathematical Statistics, Springer, Cham, 2016. Normality zones and precise deviations. MR 3585777
- Dominique Foata and Guo-Niu Han, The $q$-series in combinatorics; permutation statistics, preliminary version, 207 pages, available at http://irma.math.unistra.fr/~guoniu/papers/index.html.
- Achim Klenke, Probability theory, Translation from the German edition, Universitext, Springer, London, 2014. A comprehensive course. MR 3112259
- T. Kyle Petersen, Two-sided Eulerian numbers via balls in boxes, Math. Mag. 86 (2013), no. 3, 159–176. MR 3063137, DOI https://doi.org/10.4169/math.mag.86.3.159
- T. Kyle Petersen, Eulerian numbers, Birkhäuser Advanced Texts: Basler Lehrbücher. [Birkhäuser Advanced Texts: Basel Textbooks], Birkhäuser/Springer, New York, 2015. With a foreword by Richard Stanley. MR 3408615
- Jim Pitman, Probabilistic bounds on the coefficients of polynomials with only real zeros, J. Combin. Theory Ser. A 77 (1997), no. 2, 279–303. MR 1429082, DOI https://doi.org/10.1006/jcta.1997.2747
- Frank Röttger, Asymptotics of a locally dependent statistic on finite reflection groups, preprint, arXiv:1812.00372, 2018.
- Martin Rubey, Christian Stump, et al., FindStat - The combinatorial statistics database, http://www.FindStat.org, 2018. Accessed: \today.
- Carla D. Savage and Mirkó Visontai, The $\mathbf {s}$-Eulerian polynomials have only real roots, Trans. Amer. Math. Soc. 367 (2015), no. 2, 1441–1466. MR 3280050, DOI https://doi.org/10.1090/S0002-9947-2014-06256-9
- Richard P. Stanley, Log-concave and unimodal sequences in algebra, combinatorics, and geometry, Graph theory and its applications: East and West (Jinan, 1986) Ann. New York Acad. Sci., vol. 576, New York Acad. Sci., New York, 1989, pp. 500–535. MR 1110850, DOI https://doi.org/10.1111/j.1749-6632.1989.tb16434.x
Retrieve articles in Mathematics of Computation with MSC (2010): 20F55, 05A15, 05A16, 60F05
Retrieve articles in all journals with MSC (2010): 20F55, 05A15, 05A16, 60F05
Additional Information
Thomas Kahle
Affiliation:
Fakultät für Mathematik, Otto von Guericke Universität Magdeburg, Magdeburg, Germany
MR Author ID:
869155
ORCID:
0000-0003-3451-5021
Email:
thomas.kahle@ovgu.de
Christian Stump
Affiliation:
Fakultät für Mathematik, Ruhr-Universität Bochum, Bochum, Germany
MR Author ID:
904921
ORCID:
0000-0002-9271-8436
Email:
christian.stump@rub.de
Keywords:
Permutation statistic,
central limit theorem,
Mahonian numbers,
Eulerian numbers,
Coxeter group
Received by editor(s):
April 27, 2018
Received by editor(s) in revised form:
November 10, 2018, and February 25, 2019
Published electronically:
May 9, 2019
Additional Notes:
The first author acknowledges support from the DFG (314838170, GRK 2297 MathCoRe).
The second author was supported by the DFG grants STU 563/2 “Coxeter-Catalan combinatorics” and STU 563/4-1 “Noncrossing phenomena in Algebra and Geometry”.
Article copyright:
© Copyright 2019
American Mathematical Society