Browse issues
no. 6
A lifting of the Goulden–Jackson cluster method to the Malvenuto–Reutenauer algebra
Zhuang, Yan1
1 Davidson College 405 N. Main St. Davidson, NC 28035 (USA)
Algebraic Combinatorics, Volume 5 (2022) no. 6, pp. 1391-1425.

The Goulden–Jackson cluster method is a powerful tool for counting words by occurrences of prescribed subwords, and was adapted by Elizalde and Noy for counting permutations by occurrences of prescribed consecutive patterns. In this paper, we lift the cluster method for permutations to the Malvenuto–Reutenauer algebra. Upon applying standard homomorphisms, our result specializes to both the cluster method for permutations as well as a q-analogue which keeps track of the inversion number statistic. We construct additional homomorphisms using the theory of shuffle-compatibility, leading to further specializations which keep track of various “inverse statistics”, including the inverse descent number, inverse peak number, and inverse left peak number. This approach is then used to derive formulas for counting permutations by occurrences of two families of consecutive patterns—monotone patterns and transpositional patterns—refined by these statistics.

Received:
Revised:
Accepted:
Published online:
DOI: 10.5802/alco.255
Classification: 05A05, 05A15, 05E05
Keywords: permutation statistics, consecutive patterns, Goulden–Jackson cluster method, Malvenuto–Reutenauer algebra, shuffle-compatibility

Zhuang, Yan 1

1 Davidson College 405 N. Main St. Davidson, NC 28035 (USA)
License: CC-BY 4.0
Copyrights: The authors retain unrestricted copyrights and publishing rights 
@article{ALCO_2022__5_6_1391_0,
     author = {Zhuang, Yan},
     title = {A lifting of the {Goulden{\textendash}Jackson} cluster method to the {Malvenuto{\textendash}Reutenauer} algebra},
     journal = {Algebraic Combinatorics},
     pages = {1391--1425},
     publisher = {The Combinatorics Consortium},
     volume = {5},
     number = {6},
     year = {2022},
     doi = {10.5802/alco.255},
     language = {en},
     url = {https://alco.centre-mersenne.org/articles/10.5802/alco.255/}
}
TY  - JOUR
AU  - Zhuang, Yan
TI  - A lifting of the Goulden–Jackson cluster method to the Malvenuto–Reutenauer algebra
JO  - Algebraic Combinatorics
PY  - 2022
SP  - 1391
EP  - 1425
VL  - 5
IS  - 6
PB  - The Combinatorics Consortium
UR  - https://alco.centre-mersenne.org/articles/10.5802/alco.255/
DO  - 10.5802/alco.255
LA  - en
ID  - ALCO_2022__5_6_1391_0
ER  - 
%0 Journal Article
%A Zhuang, Yan
%T A lifting of the Goulden–Jackson cluster method to the Malvenuto–Reutenauer algebra
%J Algebraic Combinatorics
%D 2022
%P 1391-1425
%V 5
%N 6
%I The Combinatorics Consortium
%U https://alco.centre-mersenne.org/articles/10.5802/alco.255/
%R 10.5802/alco.255
%G en
%F ALCO_2022__5_6_1391_0
Zhuang, Yan. A lifting of the Goulden–Jackson cluster method to the Malvenuto–Reutenauer algebra. Algebraic Combinatorics, Volume 5 (2022) no. 6, pp. 1391-1425. doi : 10.5802/alco.255. https://alco.centre-mersenne.org/articles/10.5802/alco.255/

[1] André, Désiré Sur les permutations alternées, J. Math. Pures Appl., Volume 7 (1881), pp. 167-184 | Zbl

[2] Beaton, Nicholas R.; Conway, Andrew R.; Guttmann, Anthony J. On consecutive pattern avoiding permutations of length 4, 5 and beyond, Discrete Math. Theor. Comput. Sci., Volume 19 (2017) no. 2, p. Paper No. 8, 24 pp. | MR | Zbl

[3] Crane, Harry; DeSalvo, Stephen; Elizalde, Sergi The probability of avoiding consecutive patterns in the Mallows distribution, Random Structures Algorithms, Volume 53 (2018) no. 3, pp. 417-447 | DOI | MR | Zbl

[4] Dokos, Theodore; Dwyer, Tim; Johnson, Bryan P.; Sagan, Bruce E.; Selsor, Kimberly Permutation patterns and statistics, Discrete Math., Volume 312 (2012) no. 18, pp. 2760-2775 | DOI | MR | Zbl

[5] Duchamp, Gérard; Hivert, Florent; Thibon, Jean-Yves Noncommutative symmetric functions. VI. Free quasi-symmetric functions and related algebras, Internat. J. Algebra Comput., Volume 12 (2002) no. 5, pp. 671-717 | DOI | MR | Zbl

[6] Dwyer, Tim; Elizalde, Sergi Wilf equivalence relations for consecutive patterns, Adv. in Appl. Math., Volume 99 (2018), pp. 134-157 | DOI | MR | Zbl

[7] Elizalde, Sergi The most and the least avoided consecutive patterns, Proc. Lond. Math. Soc. (3), Volume 106 (2013) no. 5, pp. 957-979 | DOI | MR | Zbl

[8] Elizalde, Sergi A survey of consecutive patterns in permutations, Recent trends in combinatorics (IMA Vol. Math. Appl.), Volume 159, Springer, [Cham], 2016, pp. 601-618 | DOI | MR | Zbl

[9] Elizalde, Sergi; Noy, Marc Consecutive patterns in permutations, Adv. in Appl. Math., Volume 30 (2003) no. 1–2, pp. 110-125 | DOI | MR | Zbl

[10] Elizalde, Sergi; Noy, Marc Clusters, generating functions and asymptotics for consecutive patterns in permutations, Adv. in Appl. Math., Volume 49 (2012) no. 3–5, pp. 351-374 | DOI | MR | Zbl

[11] Garsia, A. M.; Gessel, I. Permutation statistics and partitions, Adv. in Math., Volume 31 (1979) no. 3, pp. 288-305 | DOI | MR | Zbl

[12] Gelfand, Israel M.; Krob, Daniel; Lascoux, Alain; Leclerc, Bernard; Retakh, Vladimir S.; Thibon, Jean-Yves Noncommutative symmetric functions, Adv. Math., Volume 112 (1995) no. 2, pp. 218-348 | DOI | MR | Zbl

[13] Gessel, Ira M. Multipartite P-partitions and inner products of skew Schur functions, Contemp. Math., Volume 34 (1984), pp. 289-317 | DOI | MR | Zbl

[14] Gessel, Ira M. Reciprocals of exponential polynomials and permutation enumeration, Australas. J. Combin., Volume 74 (2019), pp. 364-370 | MR | Zbl

[15] Gessel, Ira M. A note on Stirling permutations (2020 (originally written in 1978)) | arXiv

[16] Gessel, Ira M.; Zhuang, Yan Counting permutations by alternating descents, Electron. J. Combin., Volume 21 (2014) no. 4, p. Paper P4.23, 21 pp. | MR | Zbl

[17] Gessel, Ira M.; Zhuang, Yan Shuffle-compatible permutation statistics, Adv. Math., Volume 332 (2018), pp. 85-141 | DOI | MR | Zbl

[18] Gessel, Ira Martin Generating Functions and Enumeration of Sequences, Ph. D. Thesis, Massachusetts Institute of Technology (1977) | MR

[19] Goulden, I. P.; Jackson, D. M. An inversion theorem for cluster decompositions of sequences with distinguished subsequences, J. London Math. Soc. (2), Volume 20 (1979) no. 3, pp. 567-576 | DOI | MR | Zbl

[20] Grinberg, Darij; Reiner, Victor Hopf Algebras in Combinatorics (2020) | arXiv

[21] Josuat-Vergès, Matthieu; Novelli, Jean-Christophe; Thibon, Jean-Yves The algebraic combinatorics of snakes, J. Combin. Theory Ser. A, Volume 119 (2012) no. 8, pp. 1613-1638 | DOI | MR | Zbl

[22] Lee, Mitchell; Sah, Ashwin Constraining strong c-Wilf equivalence using cluster poset asymptotics, Adv. in Appl. Math., Volume 103 (2019), pp. 43-57 | MR | Zbl

[23] Luoto, Kurt; Mykytiuk, Stefan; van Willigenburg, Stephanie An Introduction to Quasisymmetric Schur Functions. Hopf Algebras, Quasisymmetric Functions, and Young Composition Tableaux., Springer, 2013 | DOI

[24] Malvenuto, Claudia; Reutenauer, Christophe Duality between quasi-symmetric functions and the Solomon descent algebra, J. Algebra, Volume 177 (1995) no. 3, pp. 967-982 | DOI | MR

[25] Petersen, T. Kyle Enriched P-partitions and peak algebras, Adv. Math., Volume 209 (2007) no. 2, pp. 561-610 | DOI | MR

[26] Petersen, T. Kyle Eulerian Numbers, Birkhäuser/Springer, New York, 2015 | DOI

[27] Rawlings, Don The q-exponential generating function for permutations by consecutive patterns and inversions, J. Combin. Theory Ser. A, Volume 114 (2007) no. 1, pp. 184-193 | DOI | MR | Zbl

[28] Savage, Carla D.; Viswanathan, Gopal The 1/k-Eulerian polynomials, Electron. J. Combin., Volume 19 (2012) no. 1, p. Paper 9, 21 pp. | Zbl

[29] Simion, Rodica; Schmidt, Frank W. Restricted permutations, European J. Combin., Volume 6 (1985) no. 4, pp. 383-406 | DOI | MR | Zbl

[30] Sloane, N. J. A. The On-Line Encyclopedia of Integer Sequences http://oeis.org | Zbl

[31] Stanley, Richard P. Enumerative Combinatorics, Vol. 1, Cambridge University Press, 2011 | DOI

[32] Stanley, Richard P. Enumerative Combinatorics, Vol. 2, Cambridge University Press, 2001

[33] Stembridge, John R. Enriched P-partitions, Trans. Amer. Math. Soc., Volume 349 (1997) no. 2, pp. 763-788 | DOI | MR | Zbl

[34] Troyka, Justin M.; Zhuang, Yan Fibonacci numbers, consecutive patterns, and inverse peaks, Adv. in Appl. Math., Volume 141 (2022), p. Paper No. 102406, 19 pages | DOI | MR | Zbl

[35] Zhuang, Yan Counting permutations by runs, J. Comb. Theory Ser. A, Volume 142 (2016), pp. 147-176 | DOI | MR | Zbl

[36] Zhuang, Yan Eulerian polynomials and descent statistics, Adv. in Appl. Math., Volume 90 (2017), pp. 86-144 | DOI | MR | Zbl

[37] Zhuang, Yan A generalized Goulden-Jackson cluster method and lattice path enumeration, Discrete Math., Volume 341 (2018) no. 2, pp. 358-379 | DOI | MR | Zbl

[38] Zhuang, Yan Refined consecutive pattern enumeration via a generalized cluster method (2022) (to appear in Sém. Lothar. Combin.)

Cited by Sources: