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 number 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
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 Av_n	OEIS	type of sequence	exact enumeration reference
	1, 2, 6, 23, 103, 512, 2740, 15485,...		algebraic g.f.
2143	1, 2, 6, 23, 103, 513, 2761, 15767,...		holonomic g.f.
1324	1, 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.
currently have the best rigorously established lower and upper bounds for the growth rate of this class, having established that this growth rate lies in the interval .

Classes avoiding two patterns of length 3

There are five symmetry classes and three Wilf classes, all of which were enumerated in.

B	sequence enumerating Av_n	OEIS	type of sequence
	1, 2, 4, 4, 0, 0, 0, 0,...	n/a	finite
	1, 2, 4, 7, 11, 16, 22, 29,...		polynomial,
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.

B	sequence enumerating Av_n	OEIS	type of sequence
	1, 2, 5, 13, 25, 25, 0, 0,...	n/a	finite
	1, 2, 5, 13, 30, 61, 112, 190,...		polynomial
	1, 2, 5, 13, 31, 66, 127, 225,...		polynomial
	1, 2, 5, 13, 32, 72, 148, 281,...		polynomial
	1, 2, 5, 13, 32, 74, 163, 347,...		rational g.f.
	1, 2, 5, 13, 33, 80, 185, 411,...		rational g.f.
	1, 2, 5, 13, 33, 81, 193, 449,...		rational g.f.
	1, 2, 5, 13, 33, 82, 202, 497,...		rational g.f.
	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.
Heatmaps of each of the non-finite classes are shown on the right, from
. 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 represents how many permutations have value at index. Higher resolution versions can be obtained at

B	sequence enumerating Av_n	OEIS	type of sequence	exact enumeration reference
	1, 2, 6, 22, 86, 306, 882, 1764,...		finite	Erdős–Szekeres theorem
	1, 2, 6, 22, 86, 321, 1085, 3266,...		polynomial	;
	1, 2, 6, 22, 86, 330, 1198, 4087,...		rational g.f.	;
	1, 2, 6, 22, 86, 330, 1206, 4174,...		rational g.f.	;
	1, 2, 6, 22, 86, 332, 1217, 4140,...		polynomial
	1, 2, 6, 22, 86, 333, 1235, 4339,...		rational g.f.
	1, 2, 6, 22, 86, 335, 1266, 4598,...		rational g.f.
	1, 2, 6, 22, 86, 335, 1271, 4680,...		rational g.f.
	1, 2, 6, 22, 86, 336, 1282, 4758,...		rational g.f.
	1, 2, 6, 22, 86, 336, 1290, 4870,...		rational g.f.	;
	1, 2, 6, 22, 86, 337, 1295, 4854,...		rational g.f.
	1, 2, 6, 22, 86, 337, 1299, 4910,...		rational g.f.	;
	1, 2, 6, 22, 86, 338, 1314, 5046,...		rational g.f.
	1, 2, 6, 22, 86, 338, 1318, 5106,...		rational g.f.	;
	1, 2, 6, 22, 86, 338, 1318, 5110,...		rational g.f.	;
3412, 2143	1, 2, 6, 22, 86, 340, 1340, 5254,...		algebraic g.f.
	1, 2, 6, 22, 86, 342, 1366, 5462,...		rational g.f.
	1, 2, 6, 22, 87, 348, 1374, 5335,...		algebraic g.f.
	1, 2, 6, 22, 87, 352, 1428, 5768,...		algebraic g.f.
	1, 2, 6, 22, 87, 352, 1434, 5861,...		algebraic g.f.
	1, 2, 6, 22, 87, 354, 1459, 6056,...		algebraic g.f.	proved the Wilf-equivalence; established the g.f..
	1, 2, 6, 22, 88, 363, 1507, 6241,...		algebraic g.f.
	1, 2, 6, 22, 88, 363, 1508, 6255,...		algebraic g.f.
	1, 2, 6, 22, 88, 365, 1540, 6568,...		algebraic g.f.
	1, 2, 6, 22, 88, 366, 1552, 6652,...		algebraic g.f.
	1, 2, 6, 22, 88, 366, 1556, 6720,...		algebraic g.f.
	1, 2, 6, 22, 88, 367, 1568, 6810,...		algebraic g.f.
	1, 2, 6, 22, 88, 367, 1571, 6861,...		algebraic g.f.
	1, 2, 6, 22, 88, 368, 1584, 6968,...		algebraic g.f.
	1, 2, 6, 22, 89, 376, 1611, 6901,...		algebraic g.f.
	1, 2, 6, 22, 89, 379, 1664, 7460,...		algebraic g.f.
	1, 2, 6, 22, 89, 380, 1677, 7566,...		conjectured to not satisfy any ADE; see
	1, 2, 6, 22, 89, 380, 1678, 7584,...		algebraic g.f.	; see also
	1, 2, 6, 22, 89, 381, 1696, 7781,...		algebraic g.f.
	1, 2, 6, 22, 89, 382, 1711, 7922,...		conjectured to not satisfy any ADE; see
3142, 2413	1, 2, 6, 22, 90, 394, 1806, 8558,...		Schröder numbers algebraic g.f.	; see also
	1, 2, 6, 22, 90, 395, 1823, 8741,...		algebraic g.f.
	1, 2, 6, 22, 90, 396, 1837, 8864,...		conjectured to not satisfy any ADE; see