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.

Classes avoiding one pattern of length 3

There are two symmetry classes and a single Wilf class for single permutations of length three.

Classes avoiding one pattern of length 4

There are seven symmetry classes and three Wilf classes for single permutations of length four.

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). Bevan (2015) has provided a lower bound and Bóna (2015) an upper bound 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 Avn(B)	OEIS	type of sequence
123, 321	1, 2, 4, 4, 0, 0, 0, 0, ...	n/a	finite
123, 231	1, 2, 4, 7, 11, 16, 22, 29, ...	A000124	polynomial,
123, 132 132, 312 231, 312	1, 2, 4, 8, 16, 32, 64, 128, ...	A000079	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 Atkinson (1999) or West (1996).

Classes avoiding two patterns of length 4

There are 56 symmetry classes and 38 Wilf equivalence classes. Only 8 of these remain unenumerated, and the generating functions for 3 of those 8 classes are conjectured not to satisfy any algebraic differential equation (ADE) by Albert et al. (preprint); in particular, their conjecture would imply that the generating functions are not D-finite.

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.

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: 96–105, doi:10.1016/j.aam.2005.05.007, MR 2199982 .
• Albert, Michael H.; Atkinson, M. D.; Brignall, Robert (2011), "The enumeration of permutations avoiding 2143 and 4231" (PDF), Pure Mathematics and Applications, 22: 87–98, MR 2924740 .
• Albert, Michael H.; Atkinson, M. D.; Brignall, Robert (2012), "The enumeration of three pattern classes using monotone grid classes", Electronic Journal of Combinatorics, 19 (3): Paper 20, 34 pp. .
• Albert, Michael H.; Atkinson, M. D.; Vatter, Vincent (2009), "Counting 1324, 4231-avoiding permutations", Electronic Journal of Combinatorics, 16 (1): Paper 136, 9 pp., MR 2577304 .
• Albert, Michael H.; Atkinson, M. D.; Vatter, Vincent (2014), "Inflations of geometric grid classes: three case studies" (PDF), Australasian Journal of Combinatorics, 58 (1): 27–47, MR 3211768 .
• Albert, Michael H.; Homberger, Cheyne; Pantone, Jay; Shar, Nathaniel; Vatter, Vincent (preprint), Generating permutations with restricted containers, arXiv:1510.00269  Check date values in: |date= (help).
• 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., MR 1490467 .
• Atkinson, M. D. (1999), "Restricted permutations", Discrete Mathematics, 195: 27–38, doi:10.1016/S0012-365X(98)00162-9, MR 1663866 .
• Atkinson, M. D.; Sagan, Bruce E.; Vatter, Vincent (2012), "Counting (3+1)-avoiding permutations", European Journal of Combinatorics, 33: 49–61, doi:10.1016/j.ejc.2011.06.006, MR 2854630 .
• Bevan, David (2015), "Permutations avoiding 1324 and patterns in Łukasiewicz paths", J. London Math. Soc., 92 (1): 105–122, doi:10.1112/jlms/jdv020, MR 3384507 .
• Bevan, David (2016), "The permutation classes Av(1234,2341) and Av(1243,2314)" (PDF), Australasian Journal of Combinatorics, 64 (1): 3–20, MR 3426209 .
• Bevan, David (preprint), The permutation class Av(4213,2143), arXiv:1510.06328  Check date values in: |date= (help).
• Bloom, Jonathan; Vatter, Vincent (2016), "Two vignettes on full rook placements" (PDF), Australasian Journal of Combinatorics, 64 (1): 77–87, MR 3426214 .
• Bóna, Miklós (1997), "Exact enumeration of 1342-avoiding permutations: a close link with labeled trees and planar maps", J. Combin. Theory Ser. A, 80: 257–272, doi:10.1006/jcta.1997.2800, MR 1485138 .
• Bóna, Miklós (1998), "The permutation classes equinumerous to the smooth class", Electronic Journal of Combinatorics, 5: Paper 31, 12 pp., MR 1626487 .
• Bóna, Miklós (2015), "A new record for 1324-avoiding permutations", European Journal of Combinatorics: 198–206, doi:10.1007/s40879-014-0020-6, MR 3386234 .
• Callan, David (preprint1), The number of 1243, 2134-avoiding permutations, arXiv:1303.3857  Check date values in: |date= (help).
• Callan, David (preprint2), Permutations avoiding 4321 and 3241 have an algebraic generating function, arXiv:1306.3193  Check date values in: |date= (help).
• Conway, Andrew; Guttmann, Anthony (2015), "On 1324-avoiding permutations", Adv. Appl. Math., 64: 50–69, doi:10.1016/j.aam.2014.12.004, MR 3300327 .
• Gessel, Ira M. (1990), "Symmetric functions and P-recursiveness", J. Combin. Theory Ser. A, 53: 257–285, doi:10.1016/0097-3165(90)90060-A, MR 1041448 .
• Johansson, Fredrik; Nakamura, Brian (2014), "Using functional equations to enumerate 1324-avoiding permutations", Adv. Appl. Math., 56: 20–34, doi:10.1016/j.aam.2014.01.006, MR 3194205 .
• Knuth, Donald E. (1968), The Art Of Computer Programming Vol. 1, Boston: Addison-Wesley, ISBN 0-201-89683-4, MR 0286317, OCLC 155842391 .
• Kremer, Darla (2000), "Permutations with forbidden subsequences and a generalized Schröder number", Discrete Mathematics, 218: 121–130, doi:10.1016/S0012-365X(99)00302-7, MR 1754331 .
• Kremer, Darla (2003), "Postscript: “Permutations with forbidden subsequences and a generalized Schröder number”", Discrete Mathematics, 270: 333–334, doi:10.1016/S0012-365X(03)00124-9, MR 1997910 .
• Kremer, Darla; Shiu, Wai Chee (2003), "Finite transition matrices for permutations avoiding pairs of length four patterns", Discrete Mathematics, 268: 171–183, doi:10.1016/S0012-365X(03)00042-6, MR 1983276 .
• Le, Ian (2005), "Wilf classes of pairs of permutations of length 4", Electronic Journal of Combinatorics, 12: Paper 25, 27 pp., MR 2156679 .
• 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., MR 2028282 .
• Miner, Sam (preprint), Enumeration of several two-by-four classes, arXiv:1610.01908  Check date values in: |date= (help).
• Pantone, Jay (preprint), The Enumeration of Permutations Avoiding 3124 and 4312, arXiv:1309.0832  Check date values in: |date= (help).
• Simion, Rodica; Schmidt, Frank W. (1985), "Restricted permutations", European Journal of Combinatorics, 6: 383–406, doi:10.1016/s0195-6698(85)80052-4, MR 0829358 .
• Vatter, Vincent (2012), "Finding regular insertion encodings for permutation classes", Journal of Symbolic Computation, 47: 259–265, doi:10.1016/j.jsc.2011.11.002, MR 2869320 .
• West, Julian (1996), "Generating trees and forbidden subsequences", Discrete Mathematics, 157: 363–374, doi:10.1016/S0012-365X(96)83023-8, MR 1417303 .