请输入您要查询的百科知识：

　

词条 Enumerations of specific permutation classes
释义

  1. Classes avoiding one pattern of length 3

  2. Classes avoiding one pattern of length 4

  3. Classes avoiding two patterns of length 3

  4. Classes avoiding one pattern of length 3 and one of length 4

  5. Classes avoiding two patterns of length 4

  6. External links

  7. See also

  8. References

In the study of permutation patterns, there has been considerable interest in enumerating specific permutation classes, especially those with relatively few basis elements. This area of study has turned up unexpected instances of Wilf equivalence, where two seemingly-unrelated permutation classes have the same numbers of permutations of each length.

Classes avoiding one pattern of length 3

There are two symmetry classes and a single Wilf class for single permutations of length three.

β sequence enumerating Avn(β) OEIS type of sequence exact enumeration reference

123

231		1, 2, 5, 14, 42, 132, 429, 1430, ...id=A000108}} algebraic (nonrational) g.f.
Catalan numbers 		MacMahon|1916}}
{{harvtxt|Knuth|1968}}

Classes avoiding one pattern of length 4

There are seven symmetry classes and three Wilf classes for single permutations of length four.

β sequence enumerating Avn(β) OEIS type of sequence exact enumeration reference

1342

2413

1, 2, 6, 23, 103, 512, 2740, 15485, ...id=A022558}} algebraic (nonrational) g.f. Bóna|1997}}

1234

1243

1432

2143		1, 2, 6, 23, 103, 513, 2761, 15767, ...id=A005802}} holonomic (nonalgebraic) g.f. Gessel|1990}}
1324 1, 2, 6, 23, 103, 513, 2762, 15793, ... id=A061552}}

No non-recursive formula counting 1324-avoiding permutations is known. A recursive formula was given by {{harvtxt|Marinov|Radoičić|2003}}.

A more efficient algorithm using functional equations was given by {{harvtxt|Johansson|Nakamura|2014}}, which was enhanced by {{harvtxt|Conway|Guttmann|2015}}, and then further enhanced by {{harvtxt|Conway|Guttmann|Zinn-Justin|2018}} who give the first 50 terms of the enumeration.

{{harvtxt|Bevan|Brignall|Elvey Price|Pantone|2017}} have provided lower and upper bounds for the growth of this class.

Classes avoiding two patterns of length 3

There are five symmetry classes and three Wilf classes, all of which were enumerated in {{harvtxt|Simion|Schmidt|1985}}.

B sequence enumerating Avn(B) OEIS type of sequence
123, 321 1, 2, 4, 4, 0, 0, 0, 0, ... n/a finite
213, 321 1, 2, 4, 7, 11, 16, 22, 29, ... id=A000124}} polynomial,

231, 321

132, 312
231, 312		1, 2, 4, 8, 16, 32, 64, 128, ...id=A000079}} rational g.f.,

Classes avoiding one pattern of length 3 and one of length 4

There are eighteen symmetry classes and nine Wilf classes, all of which have been enumerated. For these results, see {{harvtxt|Atkinson|1999}} or {{harvtxt|West|1996}}.

B sequence enumerating Avn(B) OEIS type of sequence
321, 1234 1, 2, 5, 13, 25, 25, 0, 0, ... n/a finite
321, 2134 1, 2, 5, 13, 30, 61, 112, 190, ... id=A116699}} polynomial
132, 4321 1, 2, 5, 13, 31, 66, 127, 225, ...id=A116701}} polynomial
321, 1324 1, 2, 5, 13, 32, 72, 148, 281, ... id=A179257}} polynomial
321, 1342 1, 2, 5, 13, 32, 74, 163, 347, ... id=A116702}} rational g.f.
321, 2143 1, 2, 5, 13, 33, 80, 185, 411, ... id=A088921}} rational g.f.

132, 4312

132, 4231

1, 2, 5, 13, 33, 81, 193, 449, ...id=A005183}} rational g.f.
132, 3214 1, 2, 5, 13, 33, 82, 202, 497, ... id=A116703}} rational g.f.

321, 2341

321, 3412

321, 3142

132, 1234

132, 4213

132, 4123

132, 3124

132, 2134

132, 3412

1, 2, 5, 13, 34, 89, 233, 610, ...id=A001519}} rational g.f.,
alternate Fibonacci numbers

Classes avoiding two patterns of length 4

There are 56 symmetry classes and 38 Wilf equivalence classes. Only 3 of these remain unenumerated, and their generating functions are conjectured not to satisfy any algebraic differential equation (ADE) by {{harvtxt|Albert|Homberger|Pantone|Shar|2018}}; in particular, their conjecture would imply that these generating functions are not D-finite.

B sequence enumerating Avn(B) OEIS type of sequence exact enumeration reference insertion encoding is regular
4321, 1234 1, 2, 6, 22, 86, 306, 882, 1764, ... id=A206736 }} finite Erdős–Szekeres theorem ✔
4312, 1234 1, 2, 6, 22, 86, 321, 1085, 3266, ... id=A116705}} polynomial Kremer|Shiu|2003}} ✔
4321, 3124 1, 2, 6, 22, 86, 330, 1198, 4087, ... id=A116708}} rational g.f. Kremer|Shiu|2003}} ✔
4312, 2134 1, 2, 6, 22, 86, 330, 1206, 4174, ... id=A116706}} rational g.f. Kremer|Shiu|2003}} ✔
4321, 1324 1, 2, 6, 22, 86, 332, 1217, 4140, ... id=A165524}} polynomial Vatter|2012}} ✔
4321, 2143 1, 2, 6, 22, 86, 333, 1235, 4339, ... id=A165525}} rational g.f. Albert|Atkinson|Brignall|2012}}
4312, 1324 1, 2, 6, 22, 86, 335, 1266, 4598, ... id=A165526}} rational g.f. Albert|Atkinson|Brignall|2012}}
4231, 2143 1, 2, 6, 22, 86, 335, 1271, 4680, ... id=A165527}} rational g.f. Albert|Atkinson|Brignall|2011}}
4231, 1324 1, 2, 6, 22, 86, 336, 1282, 4758, ... id=A165528}} rational g.f. Albert|Atkinson|Vatter|2009}}
4213, 2341 1, 2, 6, 22, 86, 336, 1290, 4870, ... id=A116709}} rational g.f. Kremer|Shiu|2003}} ✔
4312, 2143 1, 2, 6, 22, 86, 337, 1295, 4854, ... id=A165529}} rational g.f. Albert|Atkinson|Brignall|2012}}
4213, 1243 1, 2, 6, 22, 86, 337, 1299, 4910, ... id=A116710}} rational g.f. Kremer|Shiu|2003}} ✔
4321, 3142 1, 2, 6, 22, 86, 338, 1314, 5046, ... id=A165530}} rational g.f. Vatter|2012}} ✔
4213, 1342 1, 2, 6, 22, 86, 338, 1318, 5106, ... id=A116707}} rational g.f. Kremer|Shiu|2003}} ✔
4312, 2341 1, 2, 6, 22, 86, 338, 1318, 5110, ... id=A116704}} rational g.f. Kremer|Shiu|2003}} ✔
3412, 2143 1, 2, 6, 22, 86, 340, 1340, 5254, ... id=A029759}} algebraic (nonrational) g.f. Atkinson|1998}}

4321, 4123

4321, 3412

4123, 3214

4123, 2143

1, 2, 6, 22, 86, 342, 1366, 5462, ...id=A047849}} rational g.f. Kremer|Shiu|2003}}

True for the first three

4123, 2341 1, 2, 6, 22, 87, 348, 1374, 5335, ... id=A165531}} algebraic (nonrational) g.f. Atkinson|Sagan|Vatter|2012}}
4231, 3214 1, 2, 6, 22, 87, 352, 1428, 5768, ... id=A165532}} algebraic (nonrational) g.f. Miner|2016}}
4213, 1432 1, 2, 6, 22, 87, 352, 1434, 5861, ... id=A165533}} algebraic (nonrational) g.f. Miner|2016}}

4312, 3421

4213, 2431

1, 2, 6, 22, 87, 354, 1459, 6056, ...id=A164651}} algebraic (nonrational) g.f. Le|2005}} established the Wilf-equivalence;
{{harvtxt|Callan|2013a}} determined the enumeration.
4312, 3124 1, 2, 6, 22, 88, 363, 1507, 6241, ... id=A165534}} algebraic (nonrational) g.f. Pantone|2017}}
4231, 3124 1, 2, 6, 22, 88, 363, 1508, 6255, ... id=A165535}} algebraic (nonrational) g.f. Albert|Atkinson|Vatter|2014}}
4312, 3214 1, 2, 6, 22, 88, 365, 1540, 6568, ... id=A165536}} algebraic (nonrational) g.f. Miner|2016}}

4231, 3412

4231, 3142

4213, 3241

4213, 3124

4213, 2314

1, 2, 6, 22, 88, 366, 1552, 6652, ...id=A032351}} algebraic (nonrational) g.f. Bóna|1998}}
4213, 2143 1, 2, 6, 22, 88, 366, 1556, 6720, ... id=A165537}} algebraic (nonrational) g.f. Bevan|2016b}}
4312, 3142 1, 2, 6, 22, 88, 367, 1568, 6810, ... id=A165538}} algebraic (nonrational) g.f. Albert|Atkinson|Vatter|2014}}
4213, 3421 1, 2, 6, 22, 88, 367, 1571, 6861, ... id=A165539}} algebraic (nonrational) g.f. Bevan|2016a}}

4213, 3412

4123, 3142

1, 2, 6, 22, 88, 368, 1584, 6968, ...id=A109033}} algebraic (nonrational) g.f. Le|2005}}
4321, 3214 1, 2, 6, 22, 89, 376, 1611, 6901, ... id=A165540}} algebraic (nonrational) g.f. Bevan|2016a}}
4213, 3142 1, 2, 6, 22, 89, 379, 1664, 7460, ... id=A165541}} algebraic (nonrational) g.f. Albert|Atkinson|Vatter|2014}}
4231, 4123 1, 2, 6, 22, 89, 380, 1677, 7566, ... id=A165542}}Albert|Homberger|Pantone|Shar|2018}}
4321, 4213 1, 2, 6, 22, 89, 380, 1678, 7584, ... id=A165543}} algebraic (nonrational) g.f. Callan|2013b}}; see also {{harvtxt|Bloom|Vatter|2016}}
4123, 3412 1, 2, 6, 22, 89, 381, 1696, 7781, ... id=A165544}} algebraic (nonrational) g.f. Miner|Pantone|2018}}
4312, 4123 1, 2, 6, 22, 89, 382, 1711, 7922, ... id=A165545}}Albert|Homberger|Pantone|Shar|2018}}

4321, 4312

4312, 4231

4312, 4213

4312, 3412

4231, 4213

4213, 4132

4213, 4123

4213, 2413

4213, 3214

3142, 2413		1, 2, 6, 22, 90, 394, 1806, 8558, ...id=A006318}} Schröder numbers
algebraic (nonrational) g.f. 		Kremer|2000}}, {{harvtxt|Kremer|2003}}
3412, 2413 1, 2, 6, 22, 90, 395, 1823, 8741, ... id=A165546}} algebraic (nonrational) g.f. Miner|Pantone|2018}}
4321, 4231 1, 2, 6, 22, 90, 396, 1837, 8864, ... id=A053617}}Albert|Homberger|Pantone|Shar|2018}}

External links

The Database of Permutation Pattern Avoidance, maintained by Bridget Tenner, contains details of the enumeration of many other permutation classes with relatively few basis elements.

See also

  • Baxter permutation
  • Riffle shuffle permutation

References

  • {{Citation | last1=Albert | first1=Michael H. | author1-link=Michael H. Albert | last2=Elder | first2=Murray | last3=Rechnitzer | first3=Andrew | last4=Westcott | first4=P. | last5=Zabrocki | first5=Mike | title=On the Stanley-Wilf limit of 4231-avoiding permutations and a conjecture of Arratia | mr=2199982 | year=2006 | journal=Advances in Applied Mathematics | volume=36 | issue=2 | pages=96–105 | doi=10.1016/j.aam.2005.05.007}}.
  • {{Citation

|last1=Albert
|first1=Michael H.
|author1-link=Michael H. Albert
|last2=Atkinson
|first2=M. D.
|last3=Brignall
|first3=Robert
|title=The enumeration of permutations avoiding 2143 and 4231
|year=2011
|journal=Pure Mathematics and Applications
|volume=22
|pages=87–98
|url=http://puma.dimai.unifi.it/22_2/albert_atkinson_brignall.pdf
|mr=2924740

}}.

  • {{Citation

| last1=Albert | first1=Michael H. | author1-link=Michael H. Albert
| last2=Atkinson | first2=M. D.
| last3=Brignall | first3=Robert
| title=The enumeration of three pattern classes using monotone grid classes
| year=2012
| journal=Electronic Journal of Combinatorics
| volume=19 | issue = 3
| pages=Paper 20, 34 pp
| url=http://www.combinatorics.org/ojs/index.php/eljc/article/view/v19i3p20
| mr=2967225

}}.

  • {{Citation

| last1=Albert | first1=Michael H. | author1-link=Michael H. Albert
| last2=Atkinson | first2=M. D.
| last3=Vatter | first3=Vincent
| title=Counting 1324, 4231-avoiding permutations
| year=2009
| journal=Electronic Journal of Combinatorics
| volume=16 | issue = 1
| pages=Paper 136, 9 pp
| mr=2577304
| url=http://www.combinatorics.org/ojs/index.php/eljc/article/view/v16i1r136}}.
  • {{Citation

| last1=Albert | first1=Michael H. | author1-link=Michael H. Albert
| last2=Atkinson | first2=M. D.
| last3=Vatter | first3=Vincent
| title=Inflations of geometric grid classes: three case studies
| year=2014
| journal=Australasian Journal of Combinatorics
| volume=58 | issue = 1
| pages=27–47
| url=http://ajc.maths.uq.edu.au/pdf/58/ajc_v58_p027.pdf
| mr=3211768

}}.

  • {{Citation

| last1=Albert | first1=Michael H. | author1-link=Michael H. Albert
| last2=Homberger | first2=Cheyne
| last3=Pantone | first3=Jay
| last4=Shar | first4=Nathaniel
| last5=Vatter | first5=Vincent
| title=Generating permutations with restricted containers
| year=2018
| journal=Journal of Combinatorial Theory, Series A
| volume=157
| pages=205–232
| doi=10.1016/j.jcta.2018.02.006}}.
  • {{Citation

| last1=Atkinson | first1=M. D.
| title=Permutations which are the union of an increasing and a decreasing subsequence
| year=1998
| journal=Electronic Journal of Combinatorics
| volume=5
| pages=Paper 6, 13 pp
| mr=1490467
| url=http://www.combinatorics.org/ojs/index.php/eljc/article/view/v5i1r6}}.
  • {{Citation

| last1=Atkinson | first1=M. D.
| title=Restricted permutations
| year=1999
| journal=Discrete Mathematics
| volume=195
| issue=1–3
| pages=27–38
| mr=1663866
| doi=10.1016/S0012-365X(98)00162-9}}.
  • {{Citation

| last1=Atkinson | first1=M. D.
| last2=Sagan | first2=Bruce E. | author2-link=Bruce Sagan
| last3=Vatter | first3=Vincent
| title=Counting (3+1)-avoiding permutations
| year=2012
| journal=European Journal of Combinatorics
| volume=33
| pages=49–61
| mr=2854630
| doi=10.1016/j.ejc.2011.06.006}}.
  • {{Citation

| last1=Bevan | first1=David | author1-link=David Bevan (mathematician)
| title=Permutations avoiding 1324 and patterns in Łukasiewicz paths
| year=2015
| journal=J. London Math. Soc.
| volume=92
| issue = 1
| pages=105–122
| doi=10.1112/jlms/jdv020
| mr=3384507
| arxiv=1406.2890

}}.

  • {{Citation

| last1=Bevan | first1=David | author1-link=David Bevan (mathematician)
| title=The permutation classes Av(1234,2341) and Av(1243,2314)
| year=2016a
| journal=Australasian Journal of Combinatorics
| volume=64 | issue = 1
| pages=3–20
| url=http://ajc.maths.uq.edu.au/pdf/64/ajc_v64_p003.pdf
| mr=3426209

}}.

  • {{Citation

| last1=Bevan | first1=David | author1-link=David Bevan (mathematician)
| title=The permutation class Av(4213,2143)
| year=2016b
| journal=Discrete Mathematics & Theoretical Computer Science
| volume=18 | issue = 2
| pages=14 pp
| url=https://dmtcs.episciences.org/3236

}}.

  • {{Citation

| last1=Bevan | first1=David | author1-link=David Bevan (mathematician)
| last2=Brignall | first2=Robert
| last3=Elvey Price | first3=Andrew
| last4=Pantone | first4=Jay
| title=A structural characterisation of Av(1324) and new bounds on its growth rate
| year=2017
| arxiv=1711.10325
| bibcode=2017arXiv171110325B}}.
  • {{Citation

| last1=Bloom | first1=Jonathan
| last2=Vatter | first2=Vincent
| title=Two vignettes on full rook placements
| year=2016
| journal=Australasian Journal of Combinatorics
| volume=64 | issue = 1
| pages=77–87
| url=http://ajc.maths.uq.edu.au/pdf/64/ajc_v64_p077.pdf
| mr=3426214

}}.

  • {{Citation

| last1=Bóna | first1=Miklós | authorlink = Miklós Bóna
| title=Exact enumeration of 1342-avoiding permutations: a close link with labeled trees and planar maps
| mr=1485138 | year=1997 | journal=Journal of Combinatorial Theory, Series A | volume=80 | issue=2 | pages=257–272 | doi = 10.1006/jcta.1997.2800}}.
  • {{Citation

| last1=Bóna | first1=Miklós | authorlink = Miklós Bóna
| title=The permutation classes equinumerous to the smooth class
| year=1998
| journal=Electronic Journal of Combinatorics
| volume=5
| pages=Paper 31, 12 pp
| mr=1626487
| url=http://www.combinatorics.org/ojs/index.php/eljc/article/view/v5i1r31}}.
  • {{Citation

| last1=Bóna | first1=Miklós | authorlink = Miklós Bóna
| title=A new record for 1324-avoiding permutations
| year=2015
| journal=European Journal of Mathematics
| volume=1
| issue=1
| pages=198–206
| doi=10.1007/s40879-014-0020-6
| mr=3386234
| arxiv=1404.4033}}.
  • {{Citation

| last1=Callan | first1=David
| title=The number of 1243, 2134-avoiding permutations
| year=2013a
|arxiv=1303.3857
| bibcode=2013arXiv1303.3857C}}.
  • {{Citation

| last1=Callan | first1=David
| title=Permutations avoiding 4321 and 3241 have an algebraic generating function
| year=2013b
|arxiv=1306.3193
| bibcode=2013arXiv1306.3193C}}.
  • {{Citation

| last1=Conway | first1=Andrew
| last2=Guttmann | first2=Anthony
| title=On 1324-avoiding permutations
| journal=Advances in Applied Mathematics
| year=2015
| volume=64
| pages=50–69
| doi=10.1016/j.aam.2014.12.004
| mr=3300327

}}.

  • {{Citation

| last1=Conway | first1=Andrew
| last2=Guttmann | first2=Anthony
| last3=Zinn-Justin | first3=Paul
| title=1324-avoiding permutations revisited
| year=2018
| journal=Advances in Applied Mathematics
| volume=96
| pages=312–333
| doi=10.1016/j.aam.2018.01.002}}.
  • {{Citation | last1=Gessel | first1=Ira M. | title=Symmetric functions and P-recursiveness | mr=1041448 | year=1990 | journal=Journal of Combinatorial Theory, Series A | volume=53 | issue=2 | pages=257–285 | doi = 10.1016/0097-3165(90)90060-A}}.
  • {{Citation

| last1=Johansson | first1=Fredrik
| last2=Nakamura | first2=Brian
| title=Using functional equations to enumerate 1324-avoiding permutations
| journal=Advances in Applied Mathematics | year=2014 | volume=56 | pages=20–34
| doi=10.1016/j.aam.2014.01.006
| mr=3194205
| arxiv=1309.7117}}.
  • {{ Citation

| last=Knuth
| first=Donald E.
| author-link=Donald Knuth
| title=The Art Of Computer Programming Vol. 1
| publisher=Addison-Wesley
| place=Boston
| year=1968
| isbn=978-0-201-89683-1
| oclc=155842391
| mr=0286317
| title-link=The Art of Computer Programming
  • {{Citation

| last1=Kremer | first1=Darla
| title=Permutations with forbidden subsequences and a generalized Schröder number
| year=2000
| journal=Discrete Mathematics
| volume=218
| issue=1–3
| pages=121–130
| mr=1754331
| doi=10.1016/S0012-365X(99)00302-7}}.
  • {{Citation

| last1=Kremer | first1=Darla
| title=Postscript: "Permutations with forbidden subsequences and a generalized Schröder number"
| year=2003
| journal=Discrete Mathematics
| volume=270
| issue=1–3
| pages=333–334
| mr=1997910
| doi=10.1016/S0012-365X(03)00124-9}}.
  • {{Citation

| last1=Kremer | first1=Darla
| last2=Shiu | first2=Wai Chee
| title=Finite transition matrices for permutations avoiding pairs of length four patterns
| year=2003
| journal=Discrete Mathematics
| volume=268
| issue=1–3
| pages=171–183
| mr=1983276
| doi=10.1016/S0012-365X(03)00042-6}}.
  • {{Citation

| last1=Le | first1=Ian
| title=Wilf classes of pairs of permutations of length 4
| year=2005
| journal=Electronic Journal of Combinatorics
| volume=12
| pages=Paper 25, 27 pp
| mr=2156679
| url=http://www.combinatorics.org/ojs/index.php/eljc/article/view/v12i1r25}}.
  • {{ Citation

| last=MacMahon
| first=Percy A.
| author-link=Percy Alexander MacMahon
| title=Combinatory Analysis
| publisher=Cambridge University Press
| place=London
| year=1916
| mr=0141605

}}.

  • {{Citation

| last1=Marinov | first1=Darko
| last2=Radoičić | first2=Radoš
| title=Counting 1324-Avoiding Permutations
| year=2003
| journal=Electronic Journal of Combinatorics
| volume=9 | issue = 2
| pages=Paper 13, 9 pp
| mr=2028282
| url=http://www.combinatorics.org/ojs/index.php/eljc/article/view/v9i2r13

}}.

  • {{Citation

| last1=Miner | first1=Sam
| title=Enumeration of several two-by-four classes
| year=2016
|arxiv=1610.01908
| bibcode=2016arXiv161001908M}}.
  • {{Citation

| last1=Miner | first1=Sam
| last2=Pantone | first2=Jay
| title= Completing the structural analysis of the 2x4 permutation classes
| year=2018
| arxiv=1802.00483
| bibcode=2018arXiv180200483M}}.
  • {{Citation

| last1=Pantone | first1=Jay
| title=The Enumeration of Permutations Avoiding 3124 and 4312
| year=2017
| journal=Annals of Combinatorics
| volume=21
| number=2
| pages=293–315
| doi=10.1007/s00026-017-0352-2
| arxiv=1309.0832

}}.

  • {{Citation

| last1=Simion | first1=Rodica | author1-link = Rodica Simion
| last2=Schmidt | first2=Frank W.
| title=Restricted permutations
| year=1985
| journal=European Journal of Combinatorics
| volume=6
| issue=4 | pages=383–406
| mr=0829358
| doi=10.1016/s0195-6698(85)80052-4

}}.

  • {{Citation

| last1=Vatter | first1=Vincent
| title=Finding regular insertion encodings for permutation classes
| year=2012
| journal=Journal of Symbolic Computation
| volume=47
| issue=3
| pages=259–265
| mr=2869320
| doi=10.1016/j.jsc.2011.11.002}}.
  • {{Citation

| last1=West | first1=Julian
| title=Generating trees and forbidden subsequences
| year=1996
| journal=Discrete Mathematics
| volume=157
| issue=1–3
| pages=363–374
| mr=1417303
| doi=10.1016/S0012-365X(96)83023-8}}.

2 : Enumerative combinatorics|Permutation patterns
随便看

　

开放百科全书收录14589846条英语、德语、日语等多语种百科知识，基本涵盖了大多数领域的百科知识，是一部内容自由、开放的电子版国际百科全书。

　

Copyright © 2023 OENC.NET All Rights Reserved
京ICP备2021023879号 更新时间：2024/11/11 14:15:19