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 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 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 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ć). A more efficient algorithm using functional equations was given by (Johansson Nakamura), which was enhanced by (Conway Guttmann), and then further enhanced by (Conway Guttmann) who give the first 50 terms of the enumeration. (Bevan Brignall) 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).

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, [math]\displaystyle{ {n\choose 2}+1 }[/math]
231, 321 132, 312 231, 312	1, 2, 4, 8, 16, 32, 64, 128, ...	A000079	rational g.f., [math]\displaystyle{ 2^{n-1} }[/math]

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

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 (Albert Homberger); 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 [math]\displaystyle{ (i,j) }[/math] represents how many permutations have value [math]\displaystyle{ j }[/math] at index [math]\displaystyle{ i }[/math]. 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	(Kremer Shiu)
4321, 3124	1, 2, 6, 22, 86, 330, 1198, 4087, ...	A116708	rational g.f.	(Kremer Shiu)
4312, 2134	1, 2, 6, 22, 86, 330, 1206, 4174, ...	A116706	rational g.f.	(Kremer Shiu)
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)
4312, 1324	1, 2, 6, 22, 86, 335, 1266, 4598, ...	A165526	rational g.f.	(Albert Atkinson)
4231, 2143	1, 2, 6, 22, 86, 335, 1271, 4680, ...	A165527	rational g.f.	(Albert Atkinson)
4231, 1324	1, 2, 6, 22, 86, 336, 1282, 4758, ...	A165528	rational g.f.	(Albert Atkinson)
4213, 2341	1, 2, 6, 22, 86, 336, 1290, 4870, ...	A116709	rational g.f.	(Kremer Shiu)
4312, 2143	1, 2, 6, 22, 86, 337, 1295, 4854, ...	A165529	rational g.f.	(Albert Atkinson)
4213, 1243	1, 2, 6, 22, 86, 337, 1299, 4910, ...	A116710	rational g.f.	(Kremer Shiu)
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)
4312, 2341	1, 2, 6, 22, 86, 338, 1318, 5110, ...	A116704	rational g.f.	(Kremer Shiu)
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)
4123, 2341	1, 2, 6, 22, 87, 348, 1374, 5335, ...	A165531	algebraic (nonrational) g.f.	(Atkinson Sagan)
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)
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)
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)
4231, 4123	1, 2, 6, 22, 89, 380, 1677, 7566, ...	A165542	conjectured to not satisfy any ADE, see (Albert Homberger)
4321, 4213	1, 2, 6, 22, 89, 380, 1678, 7584, ...	A165543	algebraic (nonrational) g.f.	(Callan 2013b); see also (Bloom Vatter)
4123, 3412	1, 2, 6, 22, 89, 381, 1696, 7781, ...	A165544	algebraic (nonrational) g.f.	(Miner Pantone)
4312, 4123	1, 2, 6, 22, 89, 382, 1711, 7922, ...	A165545	conjectured to not satisfy any ADE, see (Albert Homberger)
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)
4321, 4231	1, 2, 6, 22, 90, 396, 1837, 8864, ...	A053617	conjectured to not satisfy any ADE, see (Albert Homberger)

See also

• Baxter permutation
• Riffle shuffle permutation

References

• Albert, Michael H.; Elder, Murray; Rechnitzer, Andrew; Westcott, P.; Zabrocki, Mike (2006), "On the Stanley–Wilf limit of 4231-avoiding permutations and a conjecture of Arratia", Advances in Applied Mathematics 36 (2): 96–105, doi:10.1016/j.aam.2005.05.007 .
• Albert, Michael H.; Atkinson, M. D.; Brignall, Robert (2011), "The enumeration of permutations avoiding 2143 and 4231", Pure Mathematics and Applications 22: 87–98, http://puma.dimai.unifi.it/22_2/albert_atkinson_brignall.pdf .
• "The enumeration of three pattern classes using monotone grid classes", Electronic Journal of Combinatorics 19 (3): Paper 20, 34 pp, 2012, doi:10.37236/2442, http://www.combinatorics.org/ojs/index.php/eljc/article/view/v19i3p20 .
• "Counting 1324, 4231-avoiding permutations", Electronic Journal of Combinatorics 16 (1): Paper 136, 9 pp, 2009, doi:10.37236/225, http://www.combinatorics.org/ojs/index.php/eljc/article/view/v16i1r136 .
• "Inflations of geometric grid classes: three case studies", Australasian Journal of Combinatorics 58 (1): 27–47, 2014, http://ajc.maths.uq.edu.au/pdf/58/ajc_v58_p027.pdf .
• "Generating permutations with restricted containers", Journal of Combinatorial Theory, Series A 157: 205–232, 2018, doi:10.1016/j.jcta.2018.02.006 .
• Atkinson, M. D. (1998), "Permutations which are the union of an increasing and a decreasing subsequence", Electronic Journal of Combinatorics 5: Paper 6, 13 pp, doi:10.37236/1344, http://www.combinatorics.org/ojs/index.php/eljc/article/view/v5i1r6 .
• Atkinson, M. D. (1999), "Restricted permutations", Discrete Mathematics 195 (1–3): 27–38, doi:10.1016/S0012-365X(98)00162-9 .
• Atkinson, M. D. (2012), "Counting (3+1)-avoiding permutations", European Journal of Combinatorics 33: 49–61, doi:10.1016/j.ejc.2011.06.006 .
• "Permutations avoiding 1324 and patterns in Łukasiewicz paths", J. London Math. Soc. 92 (1): 105–122, 2015, doi:10.1112/jlms/jdv020 .
• "The permutation classes Av(1234,2341) and Av(1243,2314)", Australasian Journal of Combinatorics 64 (1): 3–20, 2016a, http://ajc.maths.uq.edu.au/pdf/64/ajc_v64_p003.pdf .
• "The permutation class Av(4213,2143)", Discrete Mathematics & Theoretical Computer Science 18 (2): 14 pp, 2016b, https://dmtcs.episciences.org/3236 .
• A structural characterisation of Av(1324) and new bounds on its growth rate, 2017, Bibcode: 2017arXiv171110325B .
• Bloom, Jonathan; Vatter, Vincent (2016), "Two vignettes on full rook placements", Australasian Journal of Combinatorics 64 (1): 77–87, http://ajc.maths.uq.edu.au/pdf/64/ajc_v64_p077.pdf .
• "Exact enumeration of 1342-avoiding permutations: a close link with labeled trees and planar maps", Journal of Combinatorial Theory, Series A 80 (2): 257–272, 1997, doi:10.1006/jcta.1997.2800 .
• "The permutation classes equinumerous to the smooth class", Electronic Journal of Combinatorics 5: Paper 31, 12 pp, 1998, doi:10.37236/1369, http://www.combinatorics.org/ojs/index.php/eljc/article/view/v5i1r31 .
• "A new record for 1324-avoiding permutations", European Journal of Mathematics 1 (1): 198–206, 2015, doi:10.1007/s40879-014-0020-6 .
• Callan, David (2013a), The number of 1243, 2134-avoiding permutations, Bibcode: 2013arXiv1303.3857C .
• Callan, David (2013b), Permutations avoiding 4321 and 3241 have an algebraic generating function, Bibcode: 2013arXiv1306.3193C .
• Conway, Andrew; Guttmann, Anthony (2015), "On 1324-avoiding permutations", Advances in Applied Mathematics 64: 50–69, doi:10.1016/j.aam.2014.12.004 .
• Conway, Andrew; Guttmann, Anthony; Zinn-Justin, Paul (2018), "1324-avoiding permutations revisited", Advances in Applied Mathematics 96: 312–333, doi:10.1016/j.aam.2018.01.002 .
• Gessel, Ira M. (1990), "Symmetric functions and P-recursiveness", Journal of Combinatorial Theory, Series A 53 (2): 257–285, doi:10.1016/0097-3165(90)90060-A .
• Johansson, Fredrik; Nakamura, Brian (2014), "Using functional equations to enumerate 1324-avoiding permutations", Advances in Applied Mathematics 56: 20–34, doi:10.1016/j.aam.2014.01.006 .
• Knuth, Donald E. (1968), The Art Of Computer Programming Vol. 1, Boston: Addison-Wesley, ISBN 978-0-201-89683-1, OCLC 155842391 .
• Kremer, Darla (2000), "Permutations with forbidden subsequences and a generalized Schröder number", Discrete Mathematics 218 (1–3): 121–130, doi:10.1016/S0012-365X(99)00302-7 .
• Kremer, Darla (2003), "Postscript: "Permutations with forbidden subsequences and a generalized Schröder number"", Discrete Mathematics 270 (1–3): 333–334, doi:10.1016/S0012-365X(03)00124-9 .
• Kremer, Darla; Shiu, Wai Chee (2003), "Finite transition matrices for permutations avoiding pairs of length four patterns", Discrete Mathematics 268 (1–3): 171–183, doi:10.1016/S0012-365X(03)00042-6 .
• Le, Ian (2005), "Wilf classes of pairs of permutations of length 4", Electronic Journal of Combinatorics 12: Paper 25, 27 pp, doi:10.37236/1922, http://www.combinatorics.org/ojs/index.php/eljc/article/view/v12i1r25 .
• MacMahon, Percy A. (1916), Combinatory Analysis, London: Cambridge University Press .
• Marinov, Darko; Radoičić, Radoš (2003), "Counting 1324-avoiding permutations", Electronic Journal of Combinatorics 9 (2): Paper 13, 9 pp, doi:10.37236/1685, http://www.combinatorics.org/ojs/index.php/eljc/article/view/v9i2r13 .
• Miner, Sam (2016), Enumeration of several two-by-four classes, Bibcode: 2016arXiv161001908M .
• Miner, Sam; Pantone, Jay (2018), Completing the structural analysis of the 2x4 permutation classes, Bibcode: 2018arXiv180200483M .
• Pantone, Jay (2017), "The enumeration of permutations avoiding 3124 and 4312", Annals of Combinatorics 21 (2): 293–315, doi:10.1007/s00026-017-0352-2 .
• "Restricted permutations", European Journal of Combinatorics 6 (4): 383–406, 1985, doi:10.1016/s0195-6698(85)80052-4 .
• Vatter, Vincent (2012), "Finding regular insertion encodings for permutation classes", Journal of Symbolic Computation 47 (3): 259–265, doi:10.1016/j.jsc.2011.11.002 .
• West, Julian (1996), "Generating trees and forbidden subsequences", Discrete Mathematics 157 (1–3): 363–374, doi:10.1016/S0012-365X(96)83023-8 .

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.