Please wait a minute...
Frontiers of Mathematics in China

ISSN 1673-3452

ISSN 1673-3576(Online)

CN 11-5739/O1

Postal Subscription Code 80-964

2018 Impact Factor: 0.565

Front. Math. China    2024, Vol. 19 Issue (4) : 191-213    https://doi.org/10.3868/s140-DDD-024-0012-x
Research on enumeration problem of pattern-avoiding permutations
Tongyuan ZHAO1, Xiaoqing LI1, Feng ZHAO2()
1. College of Science, China University of Petroleum (Beijing), Beijing 102249, China
2. School of Mathematical Sciences, Hebei Normal University, Shijiazhuang 050024, China
 Download: PDF(683 KB)   HTML
 Export: BibTeX | EndNote | Reference Manager | ProCite | RefWorks
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 Sn, alternating permutations, Dumont permutations, Ballot permutations, and inversion sequences. It also introduces relevant research results on avoiding vincular patterns and barred patterns in Sn.

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


Abstract

Cited

  Shared   
  Discussed