Enumerations of specific permutation classes

From Wikipedia, the free encyclopedia
Jump to: navigation, search

In the study of permutation patterns, there has been considerable interest in enumerating specific permutation classes, especially those with relatively few basis elements.

Classes avoiding one pattern of length 3[edit]

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, ... A000108 algebraic (nonrational) g.f.
Catalan numbers
MacMahon (1915/16)
Knuth (1968)

Classes avoiding one pattern of length 4[edit]

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, ... A022558 algebraic (nonrational) g.f. Bóna (1997)

1234
1243
1432
2143

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 (preprint), which was enhanced by Conway & Guttmann (preprint). Bevan (preprint1) has provided a lower bound and Bóna (preprint) an upper bound for the growth of this class.

Classes avoiding two patterns of length 3[edit]

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, {n\choose 2}+1

123, 132
132, 312
231, 312

1, 2, 4, 8, 16, 32, 64, 128, ... A000079 rational g.f., 2^{n-1}

Classes avoiding one pattern of length 3 and one of length 4[edit]

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
132, 4231

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
321, 3412
321, 3142
132, 1234
132, 4213
132, 4123
132, 3124
132, 2134
132, 3412

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

Classes avoiding two patterns of length 4[edit]

There are 56 symmetry classes and 38 Wilf equivalence classes, of which 29 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
4321, 3412
4123, 3142
4123, 2143

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
4213, 2431

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
4231, 3142
4213, 3241
4213, 3124
4213, 2314

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
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 (preprint2)

4213, 3412
4123, 3142

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 (preprint2)
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
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, ... 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[edit]

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[edit]

References[edit]