# 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. 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 Av$_n$(β) | 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 (1916) 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 Av$_n$(β) | 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 (2014), which was enhanced by Conway & Guttmann (2015), and then further enhanced by Conway, Guttmann & Zinn-Justin (2018) who give the first 50 terms of the enumeration. Bevan et al. (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 Simion & Schmidt (1985).
| B | sequence enumerating Av$_n$(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, ... | A000124 | polynomial, ${n \choose 2}+1$ |
| 231, 321 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

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 Av$_n$(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

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 Albert et al. (2018); in particular, their conjecture would imply that these generating functions are not D-finite.
Heatmaps of each of the non-finite classes are shown on the right. The lexicographically minimal symmetry is used for each class, and the classes are ordered in lexicographical order. To create each heatmap, one million permutations of length 300 were sampled uniformly at random from the class. The color of the point $(i,j)$ represents how many permutations have value $j$ at index $i$. Higher resolution versions can be obtained at PermPal
| B | sequence enumerating Av$_n$(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, 3214 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 | algebraic (nonrational) g.f. | Miner (2016) |
| 4213, 1432 | 1, 2, 6, 22, 87, 352, 1434, 5861, ... | A165533 | algebraic (nonrational) g.f. | Miner (2016) |
| 4312, 3421 4213, 2431 | 1, 2, 6, 22, 87, 354, 1459, 6056, ... | A164651 | algebraic (nonrational) g.f. | Le (2005) established the Wilf-equivalence; Callan (2013a) determined the enumeration. |
| 4312, 3124 | 1, 2, 6, 22, 88, 363, 1507, 6241, ... | A165534 | algebraic (nonrational) g.f. | Pantone (2017) |
| 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 | algebraic (nonrational) g.f. | Miner (2016) |
| 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 | algebraic (nonrational) g.f. | Bevan (2016b) |
| 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 (2016a) |
| 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 (2016a) |
| 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 | conjectured to not satisfy any ADE, see Albert et al. (2018) | |
| 4321, 4213 | 1, 2, 6, 22, 89, 380, 1678, 7584, ... | A165543 | algebraic (nonrational) g.f. | Callan (2013b); see also Bloom & Vatter (2016) |
| 4123, 3412 | 1, 2, 6, 22, 89, 381, 1696, 7781, ... | A165544 | algebraic (nonrational) g.f. | Miner & Pantone (2018) |
| 4312, 4123 | 1, 2, 6, 22, 89, 382, 1711, 7922, ... | A165545 | conjectured to not satisfy any ADE, see Albert et al. (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, ... | A006318 | Schröder numbers algebraic (nonrational) g.f. | Kremer (2000), Kremer (2003) |
| 3412, 2413 | 1, 2, 6, 22, 90, 395, 1823, 8741, ... | A165546 | algebraic (nonrational) g.f. | Miner & Pantone (2018) |
| 4321, 4231 | 1, 2, 6, 22, 90, 396, 1837, 8864, ... | A053617 | conjectured to not satisfy any ADE, see Albert et al. (2018) | |