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 AvnOEIStype of sequenceexact enumeration reference

123

231		1, 2, 5, 14, 42, 132, 429, 1430,...algebraic g.f.
Catalan numbers

Classes avoiding one pattern of length 4

There are seven symmetry classes and three Wilf classes for single permutations of length four.
βsequence enumerating AvnOEIStype of sequenceexact enumeration reference

1342

2413		1, 2, 6, 23, 103, 512, 2740, 15485,...algebraic g.f.

1234

1243

1432

2143		1, 2, 6, 23, 103, 513, 2761, 15767,...holonomic g.f.
13241, 2, 6, 23, 103, 513, 2762, 15793,...

No non-recursive formula counting 1324-avoiding permutations is known. A recursive formula was given by.
A more efficient algorithm using functional equations was given by, which was enhanced by, and then further enhanced by who give the first 50 terms of the enumeration.
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.
Bsequence enumerating AvnOEIStype of sequence
123, 3211, 2, 4, 4, 0, 0, 0, 0,...n/afinite
213, 3211, 2, 4, 7, 11, 16, 22, 29,...polynomial,

231, 321

132, 312

231, 312		1, 2, 4, 8, 16, 32, 64, 128,...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 or.
Bsequence enumerating AvnOEIStype of sequence
321, 12341, 2, 5, 13, 25, 25, 0, 0,...n/afinite
321, 21341, 2, 5, 13, 30, 61, 112, 190,...polynomial
132, 43211, 2, 5, 13, 31, 66, 127, 225,...polynomial
321, 13241, 2, 5, 13, 32, 72, 148, 281,...polynomial
321, 13421, 2, 5, 13, 32, 74, 163, 347,...rational g.f.
321, 21431, 2, 5, 13, 33, 80, 185, 411,...rational g.f.

132, 4312

132, 4231		1, 2, 5, 13, 33, 81, 193, 449,...rational g.f.
132, 32141, 2, 5, 13, 33, 82, 202, 497,...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,...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 by ; in particular, their conjecture would imply that these generating functions are not D-finite.
Bsequence enumerating AvnOEIStype of sequenceexact enumeration referenceinsertion encoding is regular
4321, 12341, 2, 6, 22, 86, 306, 882, 1764,...finiteErdős–Szekeres theorem✔
4312, 12341, 2, 6, 22, 86, 321, 1085, 3266,...polynomial✔
4321, 31241, 2, 6, 22, 86, 330, 1198, 4087,...rational g.f.✔
4312, 21341, 2, 6, 22, 86, 330, 1206, 4174,...rational g.f.✔
4321, 13241, 2, 6, 22, 86, 332, 1217, 4140,...polynomial✔
4321, 21431, 2, 6, 22, 86, 333, 1235, 4339,...rational g.f.
4312, 13241, 2, 6, 22, 86, 335, 1266, 4598,...rational g.f.
4231, 21431, 2, 6, 22, 86, 335, 1271, 4680,...rational g.f.
4231, 13241, 2, 6, 22, 86, 336, 1282, 4758,...rational g.f.
4213, 23411, 2, 6, 22, 86, 336, 1290, 4870,...rational g.f.✔
4312, 21431, 2, 6, 22, 86, 337, 1295, 4854,...rational g.f.
4213, 12431, 2, 6, 22, 86, 337, 1299, 4910,...rational g.f.✔
4321, 31421, 2, 6, 22, 86, 338, 1314, 5046,...rational g.f.✔
4213, 13421, 2, 6, 22, 86, 338, 1318, 5106,...rational g.f.✔
4312, 23411, 2, 6, 22, 86, 338, 1318, 5110,...rational g.f.✔
3412, 21431, 2, 6, 22, 86, 340, 1340, 5254,...algebraic g.f.

4321, 4123

4321, 3412

4123, 3214

4123, 2143		1, 2, 6, 22, 86, 342, 1366, 5462,...rational g.f.
True for the first three
4123, 23411, 2, 6, 22, 87, 348, 1374, 5335,...algebraic g.f.
4231, 32141, 2, 6, 22, 87, 352, 1428, 5768,...algebraic g.f.
4213, 14321, 2, 6, 22, 87, 352, 1434, 5861,...algebraic g.f.

4312, 3421

4213, 2431		1, 2, 6, 22, 87, 354, 1459, 6056,...algebraic g.f. established the Wilf-equivalence;
determined the enumeration.
4312, 31241, 2, 6, 22, 88, 363, 1507, 6241,...algebraic g.f.
4231, 31241, 2, 6, 22, 88, 363, 1508, 6255,...algebraic g.f.
4312, 32141, 2, 6, 22, 88, 365, 1540, 6568,...algebraic g.f.

4231, 3412

4231, 3142

4213, 3241

4213, 3124

4213, 2314		1, 2, 6, 22, 88, 366, 1552, 6652,...algebraic g.f.
4213, 21431, 2, 6, 22, 88, 366, 1556, 6720,...algebraic g.f.
4312, 31421, 2, 6, 22, 88, 367, 1568, 6810,...algebraic g.f.
4213, 34211, 2, 6, 22, 88, 367, 1571, 6861,...algebraic g.f.

4213, 3412

4123, 3142		1, 2, 6, 22, 88, 368, 1584, 6968,...algebraic g.f.
4321, 32141, 2, 6, 22, 89, 376, 1611, 6901,...algebraic g.f.
4213, 31421, 2, 6, 22, 89, 379, 1664, 7460,...algebraic g.f.
4231, 41231, 2, 6, 22, 89, 380, 1677, 7566,...conjectured to not satisfy any ADE, see
4321, 42131, 2, 6, 22, 89, 380, 1678, 7584,...algebraic g.f.; see also
4123, 34121, 2, 6, 22, 89, 381, 1696, 7781,...algebraic g.f.
4312, 41231, 2, 6, 22, 89, 382, 1711, 7922,...conjectured to not satisfy any ADE, see

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,...Schröder numbers
algebraic g.f.		,
3412, 24131, 2, 6, 22, 90, 395, 1823, 8741,...algebraic g.f.
4321, 42311, 2, 6, 22, 90, 396, 1837, 8864,...conjectured to not satisfy any ADE, see