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 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

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 2413	1, 2, 6, 23, 103, 512, 2740, 15485, ...	A022558	algebraic (nonrational) g.f.
1234 1243 1432 2143	1, 2, 6, 23, 103, 513, 2761, 15767, ...	A005802	holonomic (nonalgebraic) g.f.
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 . 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 [10.271, 13.5].

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 Avn(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, $(\genfrac{}{}{0ex}{}{n}{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 or .

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

File:Heatmaps of all non-finite permutation classes avoiding two length four patterns 11 by 5.png

Heatmaps of 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 ; 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 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	;
4321, 3124	1, 2, 6, 22, 86, 330, 1198, 4087, ...	A116708	rational g.f.	;
4312, 2134	1, 2, 6, 22, 86, 330, 1206, 4174, ...	A116706	rational g.f.	;
4321, 1324	1, 2, 6, 22, 86, 332, 1217, 4140, ...	A165524	polynomial
4321, 2143	1, 2, 6, 22, 86, 333, 1235, 4339, ...	A165525	rational g.f.
4312, 1324	1, 2, 6, 22, 86, 335, 1266, 4598, ...	A165526	rational g.f.
4231, 2143	1, 2, 6, 22, 86, 335, 1271, 4680, ...	A165527	rational g.f.
4231, 1324	1, 2, 6, 22, 86, 336, 1282, 4758, ...	A165528	rational g.f.
4213, 2341	1, 2, 6, 22, 86, 336, 1290, 4870, ...	A116709	rational g.f.	;
4312, 2143	1, 2, 6, 22, 86, 337, 1295, 4854, ...	A165529	rational g.f.
4213, 1243	1, 2, 6, 22, 86, 337, 1299, 4910, ...	A116710	rational g.f.	;
4321, 3142	1, 2, 6, 22, 86, 338, 1314, 5046, ...	A165530	rational g.f.
4213, 1342	1, 2, 6, 22, 86, 338, 1318, 5106, ...	A116707	rational g.f.	;
4312, 2341	1, 2, 6, 22, 86, 338, 1318, 5110, ...	A116704	rational g.f.	;
3412, 2143	1, 2, 6, 22, 86, 340, 1340, 5254, ...	A029759	algebraic (nonrational) g.f.
4321, 4123 4321, 3412 4123, 3214 4123, 2143	1, 2, 6, 22, 86, 342, 1366, 5462, ...	A047849	rational g.f.
4123, 2341	1, 2, 6, 22, 87, 348, 1374, 5335, ...	A165531	algebraic (nonrational) g.f.
4231, 3214	1, 2, 6, 22, 87, 352, 1428, 5768, ...	A165532	algebraic (nonrational) g.f.
4213, 1432	1, 2, 6, 22, 87, 352, 1434, 5861, ...	A165533	algebraic (nonrational) g.f.
4312, 3421 4213, 2431	1, 2, 6, 22, 87, 354, 1459, 6056, ...	A164651	algebraic (nonrational) g.f.	proved the Wilf-equivalence; established the g.f..
4312, 3124	1, 2, 6, 22, 88, 363, 1507, 6241, ...	A165534	algebraic (nonrational) g.f.
4231, 3124	1, 2, 6, 22, 88, 363, 1508, 6255, ...	A165535	algebraic (nonrational) g.f.
4312, 3214	1, 2, 6, 22, 88, 365, 1540, 6568, ...	A165536	algebraic (nonrational) g.f.
4231, 3412 4231, 3142 4213, 3241 4213, 3124 4213, 2314	1, 2, 6, 22, 88, 366, 1552, 6652, ...	A032351	algebraic (nonrational) g.f.
4213, 2143	1, 2, 6, 22, 88, 366, 1556, 6720, ...	A165537	algebraic (nonrational) g.f.
4312, 3142	1, 2, 6, 22, 88, 367, 1568, 6810, ...	A165538	algebraic (nonrational) g.f.
4213, 3421	1, 2, 6, 22, 88, 367, 1571, 6861, ...	A165539	algebraic (nonrational) g.f.
4213, 3412 4123, 3142	1, 2, 6, 22, 88, 368, 1584, 6968, ...	A109033	algebraic (nonrational) g.f.
4321, 3214	1, 2, 6, 22, 89, 376, 1611, 6901, ...	A165540	algebraic (nonrational) g.f.
4213, 3142	1, 2, 6, 22, 89, 379, 1664, 7460, ...	A165541	algebraic (nonrational) g.f.
4231, 4123	1, 2, 6, 22, 89, 380, 1677, 7566, ...	A165542	conjectured to not satisfy any ADE; see
4321, 4213	1, 2, 6, 22, 89, 380, 1678, 7584, ...	A165543	algebraic (nonrational) g.f.	; see also
4123, 3412	1, 2, 6, 22, 89, 381, 1696, 7781, ...	A165544	algebraic (nonrational) g.f.
4312, 4123	1, 2, 6, 22, 89, 382, 1711, 7922, ...	A165545	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, ...	A006318	Schröder numbers algebraic (nonrational) g.f.	; see also
3412, 2413	1, 2, 6, 22, 90, 395, 1823, 8741, ...	A165546	algebraic (nonrational) g.f.
4321, 4231	1, 2, 6, 22, 90, 396, 1837, 8864, ...	A053617	conjectured to not satisfy any ADE; see

See also

• Baxter permutation
• Riffle shuffle permutation

References

• .
• .
• .
• .
• .
• .
• .
• .
• .
• .
• .
• .
• .
• .
• .
• .
• .
• .
• .
• .
• .
• .
• .
• .
• .
• .
• .
• .
• .
• .
• .
• .
• .
• .
• .
• .
• .

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.