Enumerations of specific permutation classes
In the study of permutation patterns, there has been considerable interest in enumerating specific permutation classes, especially those with relatively few basis elements.
Contents
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 |
1, 2, 5, 14, 42, 132, 429, 1430, ... | A000108 | algebraic (nonrational) g.f. Catalan numbers |
MacMahon (1915/16) 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 |
1, 2, 6, 23, 103, 512, 2740, 15485, ... | A022558 | algebraic (nonrational) g.f. | Bóna (1997) |
1234 |
1, 2, 6, 23, 103, 513, 2761, 15767, ... | A005802 | holonomic (nonalgebraic) g.f. | Gessel (1990) |
1324 | 1, 2, 6, 23, 103, 513, 2762, 15793, ... | A061552 |
No non-recursive formula counting 1324-avoiding permutations is known. A recursive formula was given by Marinov & Radoičić (2003). A more efficient algorithm using functional equations was given by Johansson & Nakamura (2014), which was enhanced by Conway & Guttmann (2015). Bevan (2015) has provided a lower bound and Bóna (2015) an upper bound 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 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 |
123, 231 | 1, 2, 4, 7, 11, 16, 22, 29, ... | A000124 | polynomial, ![]() |
123, 132 |
1, 2, 4, 8, 16, 32, 64, 128, ... | 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 Atkinson (1999) or 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, ... | A116699 | polynomial |
132, 4321 | 1, 2, 5, 13, 31, 66, 127, 225, ... | A116701 | polynomial |
321, 1324 | 1, 2, 5, 13, 32, 72, 148, 281, ... | A179257 | polynomial |
321, 1342 | 1, 2, 5, 13, 32, 74, 163, 347, ... | A116702 | rational g.f. |
321, 2143 | 1, 2, 5, 13, 33, 80, 185, 411, ... | A088921 | rational g.f. |
132, 4312 |
1, 2, 5, 13, 33, 81, 193, 449, ... | A005183 | rational g.f. |
132, 3214 | 1, 2, 5, 13, 33, 82, 202, 497, ... | A116703 | rational g.f. |
321, 2341 |
1, 2, 5, 13, 34, 89, 233, 610, ... | A001519 | rational g.f., alternate Fibonacci numbers |
Classes avoiding two patterns of length 4
There are 56 symmetry classes and 38 Wilf equivalence classes, of which 30 have been enumerated.
B | sequence enumerating Avn(B) | OEIS | type of sequence | exact enumeration reference |
---|---|---|---|---|
4321, 1234 | 1, 2, 6, 22, 86, 306, 882, 1764, ... | A206736 | finite | Erdős–Szekeres theorem |
4312, 1234 | 1, 2, 6, 22, 86, 321, 1085, 3266, ... | A116705 | polynomial | Kremer & Shiu (2003) |
4321, 3124 | 1, 2, 6, 22, 86, 330, 1198, 4087, ... | A116708 | rational g.f. | Kremer & Shiu (2003) |
4312, 2134 | 1, 2, 6, 22, 86, 330, 1206, 4174, ... | A116706 | rational g.f. | Kremer & Shiu (2003) |
4321, 1324 | 1, 2, 6, 22, 86, 332, 1217, 4140, ... | A165524 | polynomial | Vatter (2012) |
4321, 2143 | 1, 2, 6, 22, 86, 333, 1235, 4339, ... | A165525 | rational g.f. | Albert, Atkinson & Brignall (2012) |
4312, 1324 | 1, 2, 6, 22, 86, 335, 1266, 4598, ... | A165526 | rational g.f. | Albert, Atkinson & Brignall (2012) |
4231, 2143 | 1, 2, 6, 22, 86, 335, 1271, 4680, ... | A165527 | rational g.f. | Albert, Atkinson & Brignall (2011) |
4231, 1324 | 1, 2, 6, 22, 86, 336, 1282, 4758, ... | A165528 | rational g.f. | Albert, Atkinson & Vatter (2009) |
4213, 2341 | 1, 2, 6, 22, 86, 336, 1290, 4870, ... | A116709 | rational g.f. | Kremer & Shiu (2003) |
4312, 2143 | 1, 2, 6, 22, 86, 337, 1295, 4854, ... | A165529 | rational g.f. | Albert, Atkinson & Brignall (2012) |
4213, 1243 | 1, 2, 6, 22, 86, 337, 1299, 4910, ... | A116710 | rational g.f. | Kremer & Shiu (2003) |
4321, 3142 | 1, 2, 6, 22, 86, 338, 1314, 5046, ... | A165530 | rational g.f. | Vatter (2012) |
4213, 1342 | 1, 2, 6, 22, 86, 338, 1318, 5106, ... | A116707 | rational g.f. | Kremer & Shiu (2003) |
4312, 2341 | 1, 2, 6, 22, 86, 338, 1318, 5110, ... | A116704 | rational g.f. | Kremer & Shiu (2003) |
3412, 2143 | 1, 2, 6, 22, 86, 340, 1340, 5254, ... | A029759 | algebraic (nonrational) g.f. | Atkinson (1998) |
4321, 4123 |
1, 2, 6, 22, 86, 342, 1366, 5462, ... | A047849 | rational g.f. | Kremer & Shiu (2003) |
4123, 2341 | 1, 2, 6, 22, 87, 348, 1374, 5335, ... | A165531 | algebraic (nonrational) g.f. | Atkinson, Sagan & Vatter (2012) |
4231, 3214 | 1, 2, 6, 22, 87, 352, 1428, 5768, ... | A165532 | ||
4213, 1432 | 1, 2, 6, 22, 87, 352, 1434, 5861, ... | A165533 | ||
4312, 3421 |
1, 2, 6, 22, 87, 354, 1459, 6056, ... | A164651 | algebraic (nonrational) g.f. | Callan (preprint1) determined the enumeration; Le (2005) established the Wilf-equivalence. |
4312, 3124 | 1, 2, 6, 22, 88, 363, 1507, 6241, ... | A165534 | algebraic (nonrational) g.f. | Pantone (preprint) |
4231, 3124 | 1, 2, 6, 22, 88, 363, 1508, 6255, ... | A165535 | algebraic (nonrational) g.f. | Albert, Atkinson & Vatter (2014) |
4312, 3214 | 1, 2, 6, 22, 88, 365, 1540, 6568, ... | A165536 | ||
4231, 3412 |
1, 2, 6, 22, 88, 366, 1552, 6652, ... | A032351 | algebraic (nonrational) g.f. | Bóna (1998) |
4213, 2143 | 1, 2, 6, 22, 88, 366, 1556, 6720, ... | A165537 | algebraic (nonrational) g.f. | Bevan (preprint2) |
4312, 3142 | 1, 2, 6, 22, 88, 367, 1568, 6810, ... | A165538 | algebraic (nonrational) g.f. | Albert, Atkinson & Vatter (2014) |
4213, 3421 | 1, 2, 6, 22, 88, 367, 1571, 6861, ... | A165539 | algebraic (nonrational) g.f. | Bevan (preprint1) |
4213, 3412 |
1, 2, 6, 22, 88, 368, 1584, 6968, ... | A109033 | algebraic (nonrational) g.f. | Le (2005) |
4321, 3214 | 1, 2, 6, 22, 89, 376, 1611, 6901, ... | A165540 | algebraic (nonrational) g.f. | Bevan (preprint1) |
4213, 3142 | 1, 2, 6, 22, 89, 379, 1664, 7460, ... | A165541 | algebraic (nonrational) g.f. | Albert, Atkinson & Vatter (2014) |
4231, 4123 | 1, 2, 6, 22, 89, 380, 1677, 7566, ... | A165542 | ||
4321, 4213 | 1, 2, 6, 22, 89, 380, 1678, 7584, ... | A165543 | algebraic (nonrational) g.f. | Callan (preprint2) |
4123, 3412 | 1, 2, 6, 22, 89, 381, 1696, 7781, ... | A165544 | ||
4312, 4123 | 1, 2, 6, 22, 89, 382, 1711, 7922, ... | A165545 | ||
4321, 4312 |
1, 2, 6, 22, 90, 394, 1806, 8558, ... | A006318 | algebraic (nonrational) g.f. Schröder numbers |
Kremer (2000), Kremer (2003) |
3412, 2413 | 1, 2, 6, 22, 90, 395, 1823, 8741, ... | A165546 | ||
4321, 4231 | 1, 2, 6, 22, 90, 396, 1837, 8864, ... | A053617 |
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
References
- Lua error in package.lua at line 80: module 'strict' not found..
- Lua error in package.lua at line 80: module 'strict' not found..
- Lua error in package.lua at line 80: module 'strict' not found..
- Lua error in package.lua at line 80: module 'strict' not found..
- Lua error in package.lua at line 80: module 'strict' not found..
- Lua error in package.lua at line 80: module 'strict' not found..
- Lua error in package.lua at line 80: module 'strict' not found..
- Lua error in package.lua at line 80: module 'strict' not found..
- Lua error in package.lua at line 80: module 'strict' not found..
- Lua error in package.lua at line 80: module 'strict' not found..
- Lua error in package.lua at line 80: module 'strict' not found..
- Lua error in package.lua at line 80: module 'strict' not found..
- Lua error in package.lua at line 80: module 'strict' not found..
- Lua error in package.lua at line 80: module 'strict' not found..
- Lua error in package.lua at line 80: module 'strict' not found..
- Lua error in package.lua at line 80: module 'strict' not found..
- Lua error in package.lua at line 80: module 'strict' not found..
- Lua error in package.lua at line 80: module 'strict' not found..
- Lua error in package.lua at line 80: module 'strict' not found..
- Lua error in package.lua at line 80: module 'strict' not found..
- Lua error in package.lua at line 80: module 'strict' not found..
- Lua error in package.lua at line 80: module 'strict' not found..
- Lua error in package.lua at line 80: module 'strict' not found..
- Lua error in package.lua at line 80: module 'strict' not found..
- Lua error in package.lua at line 80: module 'strict' not found..
- Lua error in package.lua at line 80: module 'strict' not found..
- Lua error in package.lua at line 80: module 'strict' not found..
- Lua error in package.lua at line 80: module 'strict' not found..
- Lua error in package.lua at line 80: module 'strict' not found..
- Lua error in package.lua at line 80: module 'strict' not found..