Research on enumeration problem of pattern-avoiding permutations
Tongyuan ZHAO, Xiaoqing LI, Feng ZHAO
Research on enumeration problem of pattern-avoiding permutations
The problem of relevant enumeration with pattern-avoiding permutations is a significant topic in enumerative combinatorics and has wide applications in physics, chemistry, and computer science. This paper summarizes the relevant conclusions of the enumeration of pattern-avoiding permutations on the -element symmetric group , alternating permutations, Dumont permutations, Ballot permutations, and inversion sequences. It also introduces relevant research results on avoiding vincular patterns and barred patterns in
Pattern avoidance / combinatorial enumeration / combinatorial bijection
[1] |
Asinowski A, Barequet G, Bousquet-Mélou M, Mansour T, Pinter R Y. Orders induced by segments in floorplans and (2-14-3, 3-41-2)-avoiding permutations. Electron J Combin 2013; 20(2): 35
|
[2] |
Babson E, Steingrímsson E. Generalized permutation patterns and a classification of the Mahoniar statistics. Sém Lothar Combin 2000; 44: B44b
|
[3] |
Backelin J, West J, Xin G C. Wilf-equivalence for singleton classes. Adv in Appl Math 2007; 38(2): 133–148
|
[4] |
Barnabei M, Bonetti F, Castronuovo N, Silimbani M. Pattern avoiding alternating involutions. Enumer Comb Appl 2023; 3(1): S2R4
|
[5] |
Bernini A, Ferrari L, Pinzani R. Enumerating permutations avoiding three Babson-Steingrímssont patterns. Ann Comb 2005; 9(2): 137–162
|
[6] |
Bernini A, Pergola E. Enumerating permutations avoiding more than three Babson-Steingrímsson Patterns. J Integer Seq 2007; 10(6): 07.6.4
|
[7] |
Bóna M. Exact enumeration of 1342-avoiding permutations: a close link with labeled trees and planar maps. J Combin Theory Ser A 1997; 80(2): 257–272
|
[8] |
Bóna M. New records in Stanley-Wilf limts. European J Combin 2007; 28(1): 75–85
|
[9] |
Bóna M. On a family of conjectures of Joel Lewis on alternating permutations. Graphs Combin 2014; 30(3): 521–526
|
[10] |
Bousquet-Mélou M, Butler S. Forest-like permutations. Ann Combin 2007; 11(3/4): 335–354
|
[11] |
Bousquet-Mélou M, Claesson A, Dukes M, Kitaev S. (2+2)-free posets, ascent sequences and patterm avoiding permutations. J Combin Theory Ser A 2010; 117(7): 884–909
|
[12] |
Burstein A. Restricted Dumont permutations. Ann Comb 2005; 9(3): 269–280
|
[13] |
Burstein A, Elizalde S, Mansour T. Restricted Dumont permutations, Dyck paths, and noncrossing partitions. Discrete Math 2006; 306(22): 2851–2869
|
[14] |
Burstein A, Jones O. Enumeration of Dumont permutations avoiding certain four-letter patterns. Discrete Math Theor Comput Sci 2021/2022; 22(2): 7
|
[15] |
Burstein A, Josuat-Vergès M, Stromquist W. New Dumont permutations. Pure Math Appl (PU M A) 2010; 21(2): 177–206
|
[16] |
BursteinAOfodileC. Dumont permutations containing one occurrence of certain three- and four- letter patterns. In: 9th International Conference on Permutation Patterns, June 20‒24, 2011, Sam Luis Obispo, CA
|
[17] |
BursteinAStromquistW. Dumont permutations of the third kind. In: 19th International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 20077), July, 2007, Tianjin
|
[18] |
CallanD. A Wilf equivalence related to two stack sortable permutations. 2005, arXiv: math/0510211
|
[19] |
Callan D. A combinatorial interpretation of the eigensequence for composition. J Integer Seq 2006; 9(1): 06.1.4
|
[20] |
CallanD. A bijection to count (1-23-4)-avoiding permutations. 2010
|
[21] |
Chen J N, Chen Y C, W R D P. On pattern avoiding alternating permutations. European J Combin 2014; 40: 11–25
|
[22] |
Chen W Y C, Deng E Y P, Yang L L M. Riordan paths and derangements. Discrete Math 2008; 308(11): 2222–2227
|
[23] |
Chern S. On 0012-avoiding inversion sequences and a conjecture of Lin and Ma. Quaest Math 2023; 46(4): 681–694
|
[24] |
Chern S, Fu S, Lin Z. Burstein’s permutation conjecture, Hong and Li’s inversion sequence conjecture and restricted Eulerian distributions. Proc Edinb Math Soc (2) 2023; 66(4): 1179–1201
|
[25] |
Claesson A. Generalized pattern avoidance. European J Combin 2001; 22(7): 961–971
|
[26] |
Claesson A, Mansour T. Counting occurrences of a pattern of type (1, 2) or (2, 1) in permutations. Adv Appl Math 2002; 29(2): 293–310
|
[27] |
Claesson A, Mansour T. Enumerating permutations avoiding a pair of Babson-Steingrímsson patterns. Ars Combin 2005; 77: 17–31
|
[28] |
Conway A R, Guttmann A J. On 1324-avoiding permutations. Adv Appl Math 2015; 64: 50–69
|
[29] |
Conway A R, Guttmann A J, Zinn-Justin P. 1324-avoiding permutations revisited. Adv Appl Math 2018; 96: 312–333
|
[30] |
Corteel S, Martinez M A, Savage C D, Weselcouch M. Patterns in inversion sequences I. Discret Math Theor Comput Sci 2016; 18(2): 2
|
[31] |
Dumont D. Interprétations combinatoires des nombres de Genocchi. Duke Math J 1974; 41: 305–318
|
[32] |
Elizalde S. Asymptotic enumeration of permutations avoiding generalized patterns. Adv Appl Math 2006; 36(2): 138–155
|
[33] |
Elizalde S. Generating trees for permutations avoiding generalized patterns. Ann Comb 2007; 11(3/4): 435–458
|
[34] |
Elizalde S, Noy M. Consecutive patterns in permutations. Adv Appl Math 2003; 30(1/2): 110–125
|
[35] |
Gessel I M. Symmetric functions and P-recursiveness. J Combin Theory Ser A 1990; 53(2): 257–285
|
[36] |
Hong L T, Li R. Length-four pattern avoidance in inversion sequences. Electron J Combin 2022; 29(4): 4.37
|
[37] |
Kitaev S. Partially ordered generalized patterns. Discrete Math 2005; 298(1/2/3): 212–229
|
[38] |
Kitaev S, Remmel J. Classifying descents according to equivalence mod k. Electron J Combin 2006; 13(1): 64
|
[39] |
Kitaev S, Remmel J. Classifying descents according to parity. Ann Combin 2007; 11(2): 173–193
|
[40] |
KnuthD E. The Art of Computer Programming, Vol 3, Sorting and Searching, Reading. MA: Addison-Wesley, 1973
|
[41] |
Kotsireas I, Mansour T, Yıldırım G. An algorithmic approach based on generating trees for enumerating pattern-avoiding inversion sequences. J Symbolic Comput 2024; 120: 102231
|
[42] |
Kremer D, Shiu W C. Finite transition matrices for permutations avoiding pairs of length four patterns. Discrete Math 2003; 268(1/2/3): 171–183
|
[43] |
Lewis J B. Alternating, pattern-avoiding permutations. Electron J Combin 2009; 16(1): Note 7, 8
|
[44] |
Lewis J B. Pattern avoidance for alternating permutations and Young tableaux. J Combin Theory Ser A 2011; 118(4): 1436–1450
|
[45] |
Lewis J B. Generating trees and pattern avoidance in alternating permutations. Electron J Combin 2012; 19(1): 21, 21
|
[46] |
Lin Z C, Wang D G L, Zhao T Y. A decomposition of ballot permutations, pattern avoidance and Gessel walks. J Combin Theory Ser A 2022; 191: 105644
|
[47] |
MacMahonP A. Combinatory Analysis, Volumes I, II. Mineola, NY: Dover Publications, Inc, 2004
|
[48] |
Mansour T. Restricted 132-alternating permutations and Chebyshev polynomials. Ann Comb 2003; 7(2): 201–227
|
[49] |
Mansour T. Restricted 132-Dumont permutations. Australas J Combin 2004; 29: 103–117
|
[50] |
Mansour T. The enumeration of permutations whose posets have a maximum element. Adv Appl Math 2006; 37(4): 434–442
|
[51] |
Mansour T. Generating trees for 0021-avoiding inversion sequences and a conjecture of Hong and Li. Discrete Math Lett 2023; 12: 11–14
|
[52] |
MansourTNassauC. On Stanley-Wilf limit of the pattern 1324. Adv Appl Math, 2021: 130
|
[53] |
Mansour T, Shattuck M. Pattern avoidance in inversion sequences. Pure Math Appl (PU M A) 2015; 25(2): 157–176
|
[54] |
MansourTYıldırımG. Inversion sequences avoiding 021 and another pattern of length four. 2023
|
[55] |
Marcus A, Tardos G. Excluded permutation matrices and the Stanley-Wilf conjecture. J Combin Theory Ser A 2004; 107(1): 1531160
|
[56] |
Martinez M, Savage C. Patterns in inversion sequences II: inversion sequences avoiding triples of relations. J Integer Seq 2018; 21(2): 18.2.2
|
[57] |
Noonan J, Zeilberger D. The enumeration of permutations with a prescribed number of “forbidden” patterns. Adv Appl Math 1996; 17(4): 381–407
|
[58] |
OfodileC O. The enumeration of Dumont permutations with few occurrences of three and four letter patterns. Ph D Thesis. Washington, DC: Howard University, 2011
|
[59] |
PudwellL. Enumeration schemes for words avoiding permutations. In: Permutation Patterns, London Math Soc Lecture Note Ser, Vol 376. Cambridge: Cambridge University Press, 2010, 193–211
|
[60] |
Regev A. Asymptotic values for degrees associated with strips of Young diagrams. Adv Math 1981; 41(2): 115–136
|
[61] |
Reifegerste A. A generalization of Simion-Schmidt’s bijection for restricted permutations. Electron J Combin 2003; 9(2): 14
|
[62] |
Simion R, Schmidt F W. Restricted permutations. European J Combin 1985; 6(4): 383–406
|
[63] |
Simion R, Stanton D. Octabasic Laguerre polynomials and permutation statistics. J Comput Appl Math 1996; 68(1/2): 297–329
|
[64] |
SteingrímssonE. Generalized permutation patterns—a short survey. In: Permutation Patterns, London Math Soc Lecture Note Ser, Vol 376. Cambridge: Cambridge University Press, 2010, 137–152
|
[65] |
Sun N. A complete enumeration of ballot permutations avoiding sets of small patterns. Enumer Comb Appl 2023; 3(1): S2R6
|
[66] |
TestartB. Inversion sequences avoiding the pattern 010. 2022, arXiv:2212.07222
|
[67] |
WestJ. Permutations with forbidden subsequences and stack-sortable permutations. Ph D Thesis. Cambridge, MA: Massachusetts Institute of Technology, 1990
|
[68] |
West J. Generating trees and the Catalan and Schröder numbers. DiscreteMath 1995; 146(1/2/3): 247–262
|
[69] |
Xu Y X, Yan S H F. Alternating permutations with restrictions and standard Young tableaux. Electron J Combin 2012; 19(2): 49
|
[70] |
Yan C Y, Lin Z C. Inversion sequences avoiding pairs of patterns. Discrete Math Theor Comput Sci 2020/2021; 22(1): 23
|
[71] |
Yan S H F, Wang L T, Zhou R D P. On refinements of Wilf-equivalence for involutions. J Algebraic Combin 2023; 58(1): 69–94
|
/
〈 | 〉 |