Permutations, Moments, Measures

Blitvić, Natasha; Steingrímsson, Einar

doi:10.1090/tran/8330

Permutations, Moments, Measures
HTML articles powered by AMS MathViewer

by Natasha Blitvić and Einar Steingrímsson PDF

Trans. Amer. Math. Soc. 374 (2021), 5473-5508 Request permission

Abstract:

Which combinatorial sequences correspond to moments of probability measures on the real line? We present a generating function, in the form of a continued fraction, for a fourteen-parameter family of such sequences and interpret these in terms of combinatorial statistics on the symmetric groups. Special cases include several classical and noncommutative probability laws, along with a substantial subset of the orthogonalizing measures in the $q$-Askey scheme, now given a new combinatorial interpretation in terms of elementary permutation statistics. This framework further captures a variety of interesting combinatorial sequences including, notably, the moment sequences associated to distributions of the numbers of occurrences of (classical and vincular) permutation patterns of length three. This connection between pattern avoidance and broader ideas in classical and noncommutative probability is among several intriguing new corollaries, which generalize and unify results previously appearing in the literature, while opening up new lines of inquiry.

The fourteen combinatorial statistics further generalize to signed and colored permutations, and, as an infinite family of statistics, to the $k$-arrangements: permutations with $k$-colored fixed points, introduced here along with several related results and conjectures.

References

Michael Anshelevich, Partition-dependent stochastic measures and $q$-deformed cumulants, Doc. Math. 6 (2001), 343–384. MR 1871667
Paul Barry, On a transformation of Riordan moment sequences, J. Integer Seq. 21 (2018), no. 7, Art. 18.7.1, 19. MR 3858057
David Bevan, Robert Brignall, Andrew Elvey Price, and Jay Pantone, Staircases, dominoes, and the growth rate of 1324-avoiders, Electron. Notes Disc. Math., (61):123–129, 2017.
Marek Bożejko, Wiktor Ejsmont, and Takahiro Hasebe, Fock space associated to Coxeter groups of type B, J. Funct. Anal. 269 (2015), no. 6, 1769–1795. MR 3373433, DOI 10.1016/j.jfa.2015.06.026
Marek Bożejko, Wiktor Ejsmont, and Takahiro Hasebe, Noncommutative probability of type $D$, Internat. J. Math. 28 (2017), no. 2, 1750010, 30. MR 3615583, DOI 10.1142/S0129167X17500100
Alin Bostan, Andrew Elvey Price, Anthony John Guttmann, and Jean-Marie Maillard. Stieltjes moment sequences for pattern-avoiding permutations. Electron. J. Combin., 27(4):P4.20, 2020.
Eli Bagno, David Garber, and Toufik Mansour, On the group of alternating colored permutations, Electron. J. Combin. 21 (2014), no. 2, Paper 2.29, 28. MR 3210663, DOI 10.37236/3974
Philippe Biane, Permutations suivant le type d’excédance et le nombre d’inversions et interprétation combinatoire d’une fraction continue de Heine, European J. Combin. 14 (1993), no. 4, 277–284 (French). MR 1226575, DOI 10.1006/eujc.1993.1031
Philippe Biane, Some properties of crossings and partitions, Discrete Math. 175 (1997), no. 1-3, 41–53. MR 1475837, DOI 10.1016/S0012-365X(96)00139-2
Natasha Blitvić, The $(q,t)$-Gaussian process, J. Funct. Anal. 263 (2012), no. 10, 3270–3305. MR 2973341, DOI 10.1016/j.jfa.2012.08.006
Natasha Blitvić, Two-parameter non-commutative central limit theorem, Ann. Inst. Henri Poincaré Probab. Stat. 50 (2014), no. 4, 1456–1473. MR 3270001, DOI 10.1214/13-AIHP550
Anna Borowiec and Wojciech Młotkowski, New Eulerian numbers of type $D$, Electron. J. Combin. 23 (2016), no. 1, Paper 1.38, 13. MR 3484743
Marek Bożejko and Roland Speicher, An example of a generalized Brownian motion, Comm. Math. Phys. 137 (1991), no. 3, 519–531. MR 1105428
Marek Bożejko and Roland Speicher, Completely positive maps on Coxeter groups, deformed commutation relations, and operator spaces, Math. Ann. 300 (1994), no. 1, 97–120. MR 1289833, DOI 10.1007/BF01450478
Andrew R. Conway, Anthony J. Guttmann, and Paul Zinn-Justin, 1324-avoiding permutations revisited, Adv. in Appl. Math. 96 (2018), 312–333. MR 3767512, DOI 10.1016/j.aam.2018.01.002
Anders Claesson, Generalized pattern avoidance, European J. Combin. 22 (2001), no. 7, 961–971. MR 1857258, DOI 10.1006/eujc.2001.0515
Anders Claesson and Toufik Mansour, Counting occurrences of a pattern of type $(1,2)$ or $(2,1)$ in permutations, Adv. in Appl. Math. 29 (2002), no. 2, 293–310. MR 1928101, DOI 10.1016/S0196-8858(02)00012-X
Louis Comtet, Advanced combinatorics, Revised and enlarged edition, D. Reidel Publishing Co., Dordrecht, 1974. The art of finite and infinite expansions. MR 0460128
Sylvie Corteel, Crossings and alignments of permutations, Adv. in Appl. Math. 38 (2007), no. 2, 149–163. MR 2290808, DOI 10.1016/j.aam.2006.01.006
S. Corteel, R. Stanley, D. Stanton, and L. Williams, Formulae for Askey-Wilson moments and enumeration of staircase tableaux, Trans. Amer. Math. Soc. 364 (2012), no. 11, 6009–6037. MR 2946941, DOI 10.1090/S0002-9947-2012-05588-7
Robert J. Clarke, Einar Steingrímsson, and Jiang Zeng, New Euler-Mahonian statistics on permutations and words, Adv. in Appl. Math. 18 (1997), no. 3, 237–270. MR 1436481, DOI 10.1006/aama.1996.0506
Sylvie Corteel and Lauren K. Williams, Tableaux combinatorics for the asymmetric exclusion process and Askey-Wilson polynomials, Duke Math. J. 159 (2011), no. 3, 385–415. MR 2831874, DOI 10.1215/00127094-1433385
Anne de Médicis, Dennis Stanton, and Dennis White, The combinatorics of $q$-Charlier polynomials, J. Combin. Theory Ser. A 69 (1995), no. 1, 87–114. MR 1309153, DOI 10.1016/0097-3165(95)90108-6
Anne de Médicis and Xavier G. Viennot, Moments des $q$-polynômes de Laguerre et la bijection de Foata-Zeilberger, Adv. in Appl. Math. 15 (1994), no. 3, 262–304 (French). MR 1288802, DOI 10.1006/aama.1994.1010
Eric S. Egge, Defying God: the Stanley-Wilf conjecture, Stanley-Wilf limits, and a two-generation explosion of combinatorics, A century of advancing mathematics, Math. Assoc. America, Washington, DC, 2015, pp. 65–82. MR 3408142
Richard Ehrenborg, The Hankel determinant of exponential polynomials, Amer. Math. Monthly 107 (2000), no. 6, 557–560. MR 1767065, DOI 10.2307/2589352
Wiktor Ejsmont, Poisson type operators on the Fock space of type $B$ and in the Blitvić model, J. Operator Theory 84 (2020), no. 1, 67–97. MR 4157354, DOI 10.7900/jot
Sergi Elizalde, Continued fractions for permutation statistics, Discrete Math. Theor. Comput. Sci. 19 (2017), no. 2, Paper No. 11, 24. MR 3820131
Sergi Elizalde and Marc Noy, Consecutive patterns in permutations, Adv. in Appl. Math. 30 (2003), no. 1-2, 110–125. Formal power series and algebraic combinatorics (Scottsdale, AZ, 2001). MR 1979785, DOI 10.1016/S0196-8858(02)00527-4
Andrew Elvey-Price, Selected problems in enumerative combinatorics: permutation classes, random walks and planar maps, Thesis (Ph.D.)–University of Melbourne, 2018.
Shishuo Fu, Guo-Niu Han, and Zhicong Lin, $k$-arrangements, statistics, and patterns, SIAM J. Discrete Math. 34 (2020), no. 3, 1830–1853. MR 4138207, DOI 10.1137/20M1340538
P. Flajolet, Combinatorial aspects of continued fractions, Discrete Math. 32 (1980), no. 2, 125–161. MR 592851, DOI 10.1016/0012-365X(80)90050-3
Dominique Foata and Marcel-P. Schützenberger. Théorie géométrique des polynômes eulériens. Lecture Notes in Mathematics, Vol. 138. Springer-Verlag, Berlin-New York, 1970.
Jean Françon and Gérard Viennot, Permutations selon leurs pics, creux, doubles montées et double descentes, nombres d’Euler et nombres de Genocchi, Discrete Math. 28 (1979), no. 1, 21–35 (French, with English summary). MR 542933, DOI 10.1016/0012-365X(79)90182-1
Dominique Foata and Doron Zeilberger, Denert’s permutation statistic is indeed Euler-Mahonian, Stud. Appl. Math. 83 (1990), no. 1, 31–59. MR 1061147, DOI 10.1002/sapm199083131
Hans Hamburger, Über eine Erweiterung des Stieltjesschen Momentenproblems, Math. Ann. 82 (1920), no. 1-2, 120–164 (German). MR 1511978, DOI 10.1007/BF01457982
Mourad E. H. Ismail, Anisse Kasraoui, and Jiang Zeng, Separation of variables and combinatorics of linearization coefficients of orthogonal polynomials, J. Combin. Theory Ser. A 120 (2013), no. 3, 561–599. MR 3007137, DOI 10.1016/j.jcta.2012.10.007
Mourad E. H. Ismail, Dennis Stanton, and Gérard Viennot, The combinatorics of $q$-Hermite polynomials and the Askey-Wilson integral, European J. Combin. 8 (1987), no. 4, 379–392. MR 930175, DOI 10.1016/S0195-6698(87)80046-X
Alexandre Junod, Hankel determinants and orthogonal polynomials, Expo. Math. 21 (2003), no. 1, 63–74. MR 1955218, DOI 10.1016/S0723-0869(03)80010-5
Sergey Kitaev, Introduction to partially ordered patterns, Discrete Appl. Math. 155 (2007), no. 8, 929–944. MR 2319869, DOI 10.1016/j.dam.2006.09.011
Sergey Kitaev, Patterns in permutations and words, Monographs in Theoretical Computer Science. An EATCS Series, Springer, Heidelberg, 2011. With a foreword by Jeffrey B. Remmel. MR 3012380, DOI 10.1007/978-3-642-17333-2
Roelof Koekoek, Peter A. Lesky, and René F. Swarttouw, Hypergeometric orthogonal polynomials and their $q$-analogues, Springer Monographs in Mathematics, Springer-Verlag, Berlin, 2010. With a foreword by Tom H. Koornwinder. MR 2656096, DOI 10.1007/978-3-642-05014-5
Donald E. Knuth, The art of computer programming. Vol. 3, Addison-Wesley, Reading, MA, 1998. Sorting and searching; Second edition [of MR0445948]. MR 3077154
C. Krattenthaler, Advanced determinant calculus, Sém. Lothar. Combin. 42 (1999), Art. B42q, 67. The Andrews Festschrift (Maratea, 1998). MR 1701596
C. Krattenthaler, Advanced determinant calculus: a complement, Linear Algebra Appl. 411 (2005), 68–166. MR 2178686, DOI 10.1016/j.laa.2005.06.042
Anisse Kasraoui, Dennis Stanton, and Jiang Zeng, The combinatorics of Al-Salam–Chihara $q$-Laguerre polynomials, Adv. in Appl. Math. 47 (2011), no. 2, 216–239. MR 2803800, DOI 10.1016/j.aam.2010.04.008
Anisse Kasraoui and Jiang Zeng, Distribution of crossings, nestings and alignments of two edges in matchings and partitions, Electron. J. Combin. 13 (2006), no. 1, Research Paper 33, 12. MR 2212506
Percy A. MacMahon, Combinatory analysis, Chelsea Publishing Co., New York, 1960. Two volumes (bound as one). MR 0141605
Richard J. Martin and Michael J. Kearney, Integral representation of certain combinatorial recurrences, Combinatorica 35 (2015), no. 3, 309–315. MR 3367128, DOI 10.1007/s00493-014-3183-3
Wojciech Młotkowski, Fuss-Catalan numbers in noncommutative probability, Doc. Math. 15 (2010), 939–955. MR 2745687, DOI 10.1016/j.cnsns.2009.05.004
Wojciech Młotkowski, Probability measures corresponding to Aval numbers, Colloq. Math. 129 (2012), no. 2, 189–202. MR 3021804, DOI 10.4064/cm129-2-3
Wojciech Młotkowski and Karol A. Penson, The probability measure corresponding to 2-plane trees, Probab. Math. Statist. 33 (2013), no. 2, 255–264. MR 3158553
Wojciech Młotkowski and Karol A. Penson, Probability distributions with binomial moments, Infin. Dimens. Anal. Quantum Probab. Relat. Top. 17 (2014), no. 2, 1450014, 32. MR 3212684, DOI 10.1142/S0219025714500143
Wojciech Młotkowski and Karol A. Penson, A Fuss-type family of positive definite sequences, Colloq. Math. 151 (2018), no. 2, 289–304. MR 3769685, DOI 10.4064/cm6894-2-2017
Alexandru Nica and Roland Speicher, Lectures on the combinatorics of free probability, London Mathematical Society Lecture Note Series, vol. 335, Cambridge University Press, Cambridge, 2006. MR 2266879, DOI 10.1017/CBO9780511735127
OEIS Foundation Inc. (2018), The On-Line Encyclopedia of Integer Sequences.
Alex Postnikov, Total positivity, grassmannians, and networks, arXiv:math/0609764.
Christian Radoux, Calcul effectif de certains déterminants de Hankel, Bull. Soc. Math. Belg. Sér. B 31 (1979), no. 1, 49–55 (French). MR 592660
Christian Radoux, Déterminant de Hankel construit sur les polynômes de Hermite, Ann. Soc. Sci. Bruxelles Sér. I 104 (1990), no. 2, 59–61 (1991) (French). MR 1111101
Christian Radoux, Déterminant de Hankel construit sur des polynômes liés aux nombres de dérangements, European J. Combin. 12 (1991), no. 4, 327–329 (French). MR 1120419, DOI 10.1016/S0195-6698(13)80115-1
Christian Radoux, Déterminants de Hankel et théorème de Sylvester, Séminaire Lotharingien de Combinatoire (Saint-Nabor, 1992) Publ. Inst. Rech. Math. Av., vol. 498, Univ. Louis Pasteur, Strasbourg, 1992, pp. 115–122 (French). MR 1308736
Christian Radoux, Addition formulas for polynomials built on classical combinatorial sequences, Proceedings of the 8th International Congress on Computational and Applied Mathematics, ICCAM-98 (Leuven), 2000, pp. 471–477. MR 1747239, DOI 10.1016/S0377-0427(99)00120-X
Christian Radoux, The Hankel determinant of exponential polynomials: A very short proof and a new result concerning Euler numbers, Amer. Math. Monthly, 109(3):277–278, 2002.
Arthur Randrianarivony, Moments des polynômes orthogonaux unitaires de Sheffer généralisés et spécialisations, European J. Combin. 19 (1998), no. 4, 507–518 (French, with English summary). MR 1630576, DOI 10.1006/eujc.1998.0207
G. C. Shephard, Unitary groups generated by reflections, Canad. J. Math. 5 (1953), 364–383. MR 55349, DOI 10.4153/cjm-1953-042-7
Alan D. Sokal, The Euler and Springer numbers as moment sequences, Expo. Math. 38 (2020), no. 1, 1–26. MR 4082303, DOI 10.1016/j.exmath.2018.08.001
Roland Speicher, A noncommutative central limit theorem, Math. Z. 209 (1992), no. 1, 55–66. MR 1143213, DOI 10.1007/BF02570820
Rodica Simion and Frank W. Schmidt, Restricted permutations, European J. Combin. 6 (1985), no. 4, 383–406. MR 829358, DOI 10.1016/S0195-6698(85)80052-4
R. Simion and D. Stanton, Specializations of generalized Laguerre polynomials, SIAM J. Math. Anal. 25 (1994), no. 2, 712–719. MR 1266585, DOI 10.1137/S003614109322854X
R. Simion and D. Stanton, Octabasic Laguerre polynomials and permutation statistics, J. Comput. Appl. Math. 68 (1996), no. 1-2, 297–329. MR 1418763, DOI 10.1016/0377-0427(95)00250-2
J. A. Shohat and J. D. Tamarkin, The Problem of Moments, American Mathematical Society Mathematical Surveys, Vol. I, American Mathematical Society, New York, 1943. MR 0008438
Einar Steingrímsson, Permutation statistics of indexed permutations, European J. Combin. 15 (1994), no. 2, 187–205. MR 1261065, DOI 10.1006/eujc.1994.1021
Carla D. Savage and Herbert S. Wilf, Pattern avoidance in compositions and multiset permutations, Adv. in Appl. Math. 36 (2006), no. 2, 194–201. MR 2199988, DOI 10.1016/j.aam.2005.06.003
John Shareshian and Michelle L. Wachs, $q$-Eulerian polynomials: excedance number and major index, Electron. Res. Announc. Amer. Math. Soc. 13 (2007), 33–45. MR 2300004, DOI 10.1090/S1079-6762-07-00172-2
Einar Steingrímsson and Lauren K. Williams, Permutation tableaux and permutation patterns, J. Combin. Theory Ser. A 114 (2007), no. 2, 211–234. MR 2293088, DOI 10.1016/j.jcta.2006.04.001
Alan D. Sokal and Jiang Zeng, Some multivariate master polynomials for permutations, set partitions, and perfect matchings, and their continued fractions, arXiv:2003.08192.
Eugene P. Wigner, Characteristic vectors of bordered matrices with infinite dimensions, Ann. of Math. (2) 62 (1955), 548–564. MR 77805, DOI 10.2307/1970079
Jet Wimp, Hankel determinants of some polynomials arising in combinatorial analysis, Numer. Algorithms 24 (2000), no. 1-2, 179–193. Computational methods from rational approximation theory (Wilrijk, 1999). MR 1784998, DOI 10.1023/A:1019197311168