关于n元对称群上的有禁排列计数研究
Research on Enumeration of Pattern-Avoiding Permutations on N-Element Symmetric Group
DOI: 10.12677/PM.2023.135156, PDF,    国家自然科学基金支持
作者: 赵彤远, 李晓清, 郭 童：中国石油大学理学院，北京；赵 沨：河北师范大学数学科学学院，河北省数学与交叉科学国际联合研究中心，河北省计算数学与应用重点实验室，河北省数学研究中心，河北 石家庄
关键词: 排列；模式避免；组合双射；Permutation； Pattern Avoidance； Combinatorial Bijection
摘要: 有禁排列计数问题是计数组合学中的热点问题，在物理、化学、计算机等学科中有着广泛应用。本文在Kitaev的综述书籍基础上，对n元对称群Sn上有禁排列计数的经典结果进行了总结，并介绍相关研究成果。
Abstract: The enumeration of pattern-avoiding permutations is a hot topic in enumeration combinatorics and has wide applications in physics, chemistry and computer science. Based on Kitaev’s review book, this paper summarizes the classical results of the enumeration of pattern-avoiding permutations n-element symmetric group Sn, and introduces the related research results.
文章引用：赵彤远, 赵沨, 李晓清, 郭童. 关于n元对称群上的有禁排列计数研究[J]. 理论数学, 2023, 13(5): 1548-1554. https://doi.org/10.12677/PM.2023.135156

参考文献

[1] MacMahon, P.A. (2001) Combinatory Analysis, Volumes I and II. American Mathematical Society, Washington DC.
[2] Knuth, D.E. (1973) The Art of Computer Programming, Volume 3: Sorting and Searching. Pearson Education India, London.
[3] Rotem, D. (1975) On a Correspondence between Binary Trees and a Certain Type of Permutation. Information Processing Letters, 4, 58-61. [Google Scholar] [CrossRef] 
[4] Rogers, D.G. (1978) Ascending Sequences in Permutations. Discrete Mathematics, 22, 35-40. [Google Scholar] [CrossRef] 
[5] Simion, R. and Schmidt, F.W. (1985) Restricted Permutations. European Journal of Combinatorics, 6, 383-406. [Google Scholar] [CrossRef] 
[6] Kitaev, S. (2011) Patterns in Permutations and Words. Springer, Heidelberg. [Google Scholar] [CrossRef] 
[7] Callan, D. and Mansour, T. (2017) Enumeration of 2-Wilf Classes of Four 4-Letter Patterns. Turkish Journal of Analysis and Number Theory, 5, 210-225. [Google Scholar] [CrossRef] 
[8] Callan, D. and Mansour, T. (2018) Enumeration of 3- and 4-Wilf Classes of Four 4-Letter Patterns. Notes on Number Theory and Discrete Mathematics, 24, 115-130. [Google Scholar] [CrossRef] 
[9] Callan, D. and Mansour, T. (2018) Enumeration of Small Wilf Classes Avoiding 1342 and Two Other 4-Letter Patterns. Pure Mathematics and Applications, 27, 62-97. [Google Scholar] [CrossRef] 
[10] Hou, Q.H. and Mansour, T. (2006) Horse Paths, Restricted 132-Avoiding Permutations, Continued Fractions, and Chebyshev Polynomials. Discrete Applied Mathematics, 154, 1183-1197. [Google Scholar] [CrossRef] 
[11] Claesson, A., Kitaev, S. and Steingrímsson, E. (2009) Decompositions and Statistics for β(1,0)-Trees and Nonseparable Permutations. Advances in Applied Mathematics, 42, 313-328. [Google Scholar] [CrossRef] 
[12] Krattenthaler, C. (2001) Permutations with Restricted Patterns and Dyck Paths. Advances in Applied Mathematics, 27, 510-530. [Google Scholar] [CrossRef] 
[13] Mansour, T., Deng, E.Y.P. and Du, R.R.X. (2006) Dyck Paths and Restricted Permutations. Discrete Applied Mathematics, 154, 1593-1605. [Google Scholar] [CrossRef] 
[14] Richards, D. (1988) Ballot Sequences and Restricted Permutations. ARS Combinatoria, 25, 83-86.
[15] West, J. (1995) Generating Trees and the Catalan and Schröder Numbers. Discrete Mathematics, 146, 247-262. [Google Scholar] [CrossRef] 
[16] Reifegerste, A. (2003) A Generalization of Simion-Schmidt’s Bijection for Restricted Permutations. The Electronic Journal of Combinatorics, 9, R14. [Google Scholar] [CrossRef] 
[17] Claesson, A. and Kitaev, S. (2008) Classification of Bijections between 321- and 132-Avoiding Permutations. Séminaire Lotharingien de Combinatoire, 60, B60d. [Google Scholar] [CrossRef] 
[18] Bóna, M. (1997) Exact Enumeration of 1342-Avoiding Permutations: A Close Link with Labeled Trees and Planar Maps. Journal of Combinatorial Theory, Series A, 80, 257-272. [Google Scholar] [CrossRef] 
[19] Regev, A. (1981) Asymptotic Values for Degrees Associated with Strips of Young Diagrams. Advances in Mathematics, 41, 115-136. [Google Scholar] [CrossRef] 
[20] Backelin, J., West, J. and Xin, G. (2007) Wilf-Equivalence for Singleton Classes. Advances in Applied Mathematics, 38, 133-148. [Google Scholar] [CrossRef] 
[21] Stankova, Z.E. (1994) Forbidden Subsequences. Discrete Mathematics, 132, 291-316. [Google Scholar] [CrossRef] 
[22] Stankova, Z. (1996) Classification of Forbidden Subsequences of Length 4. European Journal of Combinatorics, 17, 501-517. [Google Scholar] [CrossRef] 
[23] Gessel, I.M. (1990) Symmetric Functions and P-Recursiveness. Journal of Combinatorial Theory, Series A, 53, 257-285. [Google Scholar] [CrossRef] 
[24] Erdös, P. and Szekeres, G. (1935) A Combinatorial Problem in Geometry. Compositio Mathematica, 2, 463-470.
[25] Billey, S.C., Jockusch, W. and Stanley, R.P. (1993) Some Combinatorial Properties of Schubert Polynomials. Journal of Algebraic Combinatorics, 2, 345-374. [Google Scholar] [CrossRef] 
[26] West, J. (1996) Generating Trees and Forbidden Subsequences. Discrete Mathematics, 157, 363-374. [Google Scholar] [CrossRef] 
[27] Tenner, B.E. (2007) Pattern Avoidance and the Bruhat Order. Journal of Combinatorial Theory, Series A, 114, 888-905. [Google Scholar] [CrossRef] 
[28] Le, I. (2005) Wilf Classes of Pairs of Permutations of Length 4. The Electronic Journal of Combinatorics, 12, R25. [Google Scholar] [CrossRef] 
[29] Kremer, D. (2000) Permutations with Forbidden Subsequences and a Generalized Schröder Number. Discrete Mathematics, 218, 121-130. [Google Scholar] [CrossRef] 
[30] Egge, E.S. and Mansour, T. (2003) Permutations Which Avoid 1243 and 2143, Continued Fractions, and Chebyshev Polynomials. The Electronic Journal of Combinatorics, 9, R7. [Google Scholar] [CrossRef] 
[31] Kremer, D. and Shiu, W.C. (2003) Finite Transition Matrices for Permutations Avoiding Pairs of Length Four Patterns. Discrete Mathematics, 268, 171-183. [Google Scholar] [CrossRef] 
[32] Atkinson, M.D. (1998) Permutations Which Are the Union of an Increasing and a Decreasing Subsequence. The Electronic Journal of Combinatorics, 5, R6. [Google Scholar] [CrossRef] 
[33] Miner, S. (2016) Enumeration of Several Two-by-Four Classes.
[34] Miner, S. and Pantone, J. (2018) Completing the Structural Analysis of the 2 × 4 Permutation Classes.
[35] Callan, D., Mansour, T. and Shattuck, M. (2017) Wilf Classification of Triples of 4-Letter Patterns I. Discrete Mathematics and Theoretical Computer Science, 19, Article No. 5. [Google Scholar] [CrossRef] 
[36] Shattuck, M., Mansour, T. and Callan, D. (2017) Wilf Classification of Triples of 4-Letter Patterns II. Discrete Mathematics and Theoretical Computer Science, 19, Article No. 6.
[37] Mansour, T. (2006) The Enumeration of Permutations Whose Posets Have a Maximum Element. Advances in Applied Mathematics, 37, 434-442. [Google Scholar] [CrossRef] 
[38] Mansour, T. (2020) Enumeration and Wilf-Classification of Permutations Avoiding Four Patterns of Length 4. Discrete Mathematics Letters, 3, 67-94.
[39] Greene, R.M. and Losonczy, J. (2002) Freely Braided Elements in Coxeter Groups. Annals of Combinatorics, 6, 337-348. [Google Scholar] [CrossRef] 
[40] Mansour, T. (2004) On an Open Problem of Green and Losonczy: Exact Enumeration of Freely Braided Permutations. Discrete Mathematics and Theoretical Computer Science, 6, 461-470. [Google Scholar] [CrossRef] 
[41] Albert, M.H., Linton, S. and Rus ̌kuc, N. (2005) The Insertion Encoding of Permutations. The Electronic Journal of Combinatorics, 12, R47. [Google Scholar] [CrossRef] 
[42] Babson, E. and West, J. (2000) The Permutations 123p_4⋯p_m and 321p_4⋯p_m Are Wilf-Equivalent. Graphs and Combinatorics, 16, 373-380. [Google Scholar] [CrossRef] 
[43] Stankova, Z. and West, J. (2002) A New Class of Wilf-Equivalent Permutations. Journal of Algebraic Combinatorics, 15, 271-290. [Google Scholar] [CrossRef] 
[44] Wilf, H.S. (1992) Ascending Subsequences of Permutations and the Shapes of Tableaux. Journal of Combinatorial Theory, Series A, 60, 155-157. [Google Scholar] [CrossRef] 
[45] Bóna, M. (2010) On Three Different Notions of Monotone Subsequences. Permutation Patterns, 376, 89-114. [Google Scholar] [CrossRef] 
[46] Bóna, M. (1997) Permutations Avoiding Certain Patterns: The Case of Length 4 and Some Generalizations. Discrete Mathematics, 175, 55-67. [Google Scholar] [CrossRef] 
[47] Marcus, A. and Tardos, G. (2004) Excluded Permutation Matrices and the Stanley-Wilf Conjecture. Journal of Combinatorial Theory, Series A, 107, 153-160. [Google Scholar] [CrossRef] 
[48] Bóna, M. (2005) The Limit of a Stanley-Wilf Sequence Is Not Always Rational, and Layered Patterns Beat Monotone Patterns. Journal of Combinatorial Theory, Series A, 110, 223-235. [Google Scholar] [CrossRef] 
[49] Albert, H., Elder, M., Rechnitzer, A., et al. (2006) On the Stanley-Wilf Limit of 4231-Avoiding Permutations and a Conjecture of Arratia. Advances in Applied Mathematics, 36, 96-105. [Google Scholar] [CrossRef] 
[50] Kaiser, T. and Klazar, M. (2002) On Growth Rates of Closed Permutation Classes. The Electronic Journal of Combinatorics, 9, R10. [Google Scholar] [CrossRef] 
[51] Bóna, M. (2007) New Records in Stanley-Wilf Limits. European Journal of Combinatorics, 28, 75-85. [Google Scholar] [CrossRef] 
[52] Mansour, T. and Rastegar, R. (2022) Pattern Occurrences in K-Ary Words Revisited: A Few New and Old Observations. Journal of Combinatorial Theory, Series A, 188, Article ID: 105596. [Google Scholar] [CrossRef] 

为你推荐