Research on enumeration problem of pattern-avoiding permutations

Abstract

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 n-element symmetric group {\mathcal{S}}_n, alternating permutations, Dumont permutations, Ballot permutations, and inversion sequences. It also introduces relevant research results on avoiding vincular patterns and barred patterns in {\mathcal{S}}_n.

Keywords

Pattern avoidance / combinatorial enumeration / combinatorial bijection

References

[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

RIGHTS & PERMISSIONS

Higher Education Press 2024