Enumerations of specific permutation classes

Last updated November 03, 2024

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 Av_n(β)	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 Av_n(β)	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ć (2003). A more efficient algorithm using functional equations was given by Johansson & Nakamura (2014), which was enhanced by Conway & Guttmann (2015), and then further enhanced by Conway, Guttmann & Zinn-Justin (2018) who give the first 50 terms of the enumeration. Bevan et al. (2017) 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 (1985).

B	sequence enumerating Av_n(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, ${n \choose 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 Atkinson (1999) or West (1996).

B	sequence enumerating Av_n(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

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 et al. (2018); 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 Av_n(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 (2003)
4321, 3124	1, 2, 6, 22, 86, 330, 1198, 4087, ...	A116708	rational g.f.	Kremer & Shiu (2003)
4312, 2134	1, 2, 6, 22, 86, 330, 1206, 4174, ...	A116706	rational g.f.	Kremer & Shiu (2003)
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 & Brignall (2012)
4312, 1324	1, 2, 6, 22, 86, 335, 1266, 4598, ...	A165526	rational g.f.	Albert, Atkinson & Brignall (2012)
4231, 2143	1, 2, 6, 22, 86, 335, 1271, 4680, ...	A165527	rational g.f.	Albert, Atkinson & Brignall (2011)
4231, 1324	1, 2, 6, 22, 86, 336, 1282, 4758, ...	A165528	rational g.f.	Albert, Atkinson & Vatter (2009)
4213, 2341	1, 2, 6, 22, 86, 336, 1290, 4870, ...	A116709	rational g.f.	Kremer & Shiu (2003)
4312, 2143	1, 2, 6, 22, 86, 337, 1295, 4854, ...	A165529	rational g.f.	Albert, Atkinson & Brignall (2012)
4213, 1243	1, 2, 6, 22, 86, 337, 1299, 4910, ...	A116710	rational g.f.	Kremer & Shiu (2003)
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 (2003)
4312, 2341	1, 2, 6, 22, 86, 338, 1318, 5110, ...	A116704	rational g.f.	Kremer & Shiu (2003)
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 (2003)
4123, 2341	1, 2, 6, 22, 87, 348, 1374, 5335, ...	A165531	algebraic (nonrational) g.f.	Atkinson, Sagan & Vatter (2012)
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 & Vatter (2014)
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 & Vatter (2014)
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 & Vatter (2014)
4231, 4123	1, 2, 6, 22, 89, 380, 1677, 7566, ...	A165542	conjectured to not satisfy any ADE, see Albert et al. (2018)
4321, 4213	1, 2, 6, 22, 89, 380, 1678, 7584, ...	A165543	algebraic (nonrational) g.f.	Callan (2013b); see also Bloom & Vatter (2016)
4123, 3412	1, 2, 6, 22, 89, 381, 1696, 7781, ...	A165544	algebraic (nonrational) g.f.	Miner & Pantone (2018)
4312, 4123	1, 2, 6, 22, 89, 382, 1711, 7922, ...	A165545	conjectured to not satisfy any ADE, see Albert et al. (2018)
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 (2018)
4321, 4231	1, 2, 6, 22, 90, 396, 1837, 8864, ...	A053617	conjectured to not satisfy any ADE, see Albert et al. (2018)

Related Research Articles

A polyomino is a plane geometric figure formed by joining one or more equal squares edge to edge. It is a polyform whose cells are squares. It may be regarded as a finite subset of the regular square tiling.

In graph theory, a uniquely colorable graph is a $k$ -chromatic graph that has only one possible (proper) $k$ -coloring up to permutation of the colors. Equivalently, there is only one way to partition its vertices into $k$ independent sets and there is no way to partition them into $k - 1$ independent sets.

In graph theory, a subcoloring is an assignment of colors to a graph's vertices such that each color class induces a vertex disjoint union of cliques. That is, each color class should form a cluster graph.

In the mathematical study of permutations and permutation patterns, a superpattern or universal permutation is a permutation that contains all of the patterns of a given length. More specifically, a k-superpattern contains all possible patterns of length k.

The Stanley–Wilf conjecture, formulated independently by Richard P. Stanley and Herbert Wilf in the late 1980s, states that the growth rate of every proper permutation class is singly exponential. It was proved by Adam Marcus and Gábor Tardos and is no longer a conjecture. Marcus and Tardos actually proved a different conjecture, due to Zoltán Füredi and Péter Hajnal, which had been shown to imply the Stanley–Wilf conjecture by Klazar (2000).

In the mathematical field of graph theory, a permutation graph is a graph whose vertices represent the elements of a permutation, and whose edges represent pairs of elements that are reversed by the permutation. Permutation graphs may also be defined geometrically, as the intersection graphs of line segments whose endpoints lie on two parallel lines. Different permutations may give rise to the same permutation graph; a given graph has a unique representation if it is prime with respect to the modular decomposition.

In the mathematical field of graph theory, the Fibonacci cubes or Fibonacci networks are a family of undirected graphs with rich recursive properties derived from its origin in number theory. Mathematically they are similar to the hypercube graphs, but with a Fibonacci number of vertices. Fibonacci cubes were first explicitly defined in Hsu (1993) in the context of interconnection topologies for connecting parallel or distributed systems. They have also been applied in chemical graph theory.

In combinatorial mathematics and theoretical computer science, a (classical) permutation pattern is a sub-permutation of a longer permutation. Any permutation may be written in one-line notation as a sequence of entries representing the result of applying the permutation to the sequence 123...; for instance the sequence 213 represents the permutation on three elements that swaps elements 1 and 2. If π and σ are two permutations represented in this way, then π is said to contain σ as a pattern if some subsequence of the entries of π has the same relative order as all of the entries of σ.

In combinatorial mathematics, a partial permutation, or sequence without repetition, on a finite set S is a bijection between two specified subsets of S. That is, it is defined by two subsets U and V of equal size, and a one-to-one mapping from U to V. Equivalently, it is a partial function on S that can be extended to a permutation.

In mathematics, the telephone numbers or the involution numbers form a sequence of integers that count the ways $n$ people can be connected by person-to-person telephone calls. These numbers also describe the number of matchings of a complete graph on $n$ vertices, the number of permutations on $n$ elements that are involutions, the sum of absolute values of coefficients of the Hermite polynomials, the number of standard Young tableaux with $n$ cells, and the sum of the degrees of the irreducible representations of the symmetric group. Involution numbers were first studied in 1800 by Heinrich August Rothe, who gave a recurrence equation by which they may be calculated, giving the values

In combinatorial mathematics, a Baxter permutation is a permutation $which satisfies the following generalized pattern avoidance property:$

Richard Alejandro Arratia is a mathematician noted for his work in combinatorics and probability theory.

Rodica Eugenia Simion was a Romanian-American mathematician. She was the Columbian School Professor of Mathematics at George Washington University. Her research concerned combinatorics: she was a pioneer in the study of permutation patterns, and an expert on noncrossing partitions.

In graph theory, a distinguishing coloring or distinguishing labeling of a graph is an assignment of colors or labels to the vertices of the graph that destroys all of the nontrivial symmetries of the graph. The coloring does not need to be a proper coloring: adjacent vertices are allowed to be given the same color. For the colored graph, there should not exist any one-to-one mapping of the vertices to themselves that preserves both adjacency and coloring. The minimum number of colors in a distinguishing coloring is called the distinguishing number of the graph.

Mireille Bousquet-Mélou is a French mathematician who specializes in enumerative combinatorics and who works as a senior researcher for the Centre national de la recherche scientifique (CNRS) at the computer science department (LaBRI) of the University of Bordeaux.

David Bevan is an English mathematician, computer scientist and software developer. He is known for Bevan's theorem, which gives the asymptotic enumeration of grid classes of permutations and for his work on enumerating the class of permutations avoiding the pattern 1324. He is also known for devising weighted reference counting, an approach to computer memory management that is suitable for use in distributed systems.

In the theory of permutation patterns, a skew-merged permutation is a permutation that can be partitioned into an increasing sequence and a decreasing sequence. They were first studied by Stankova (1994) and given their name by Atkinson (1998).

In the mathematics of permutations, a layered permutation is a permutation that reverses contiguous blocks of elements. Equivalently, it is the direct sum of decreasing permutations.

In mathematics and computer science, the sorting numbers are a sequence of numbers introduced in 1950 by Hugo Steinhaus for the analysis of comparison sort algorithms. These numbers give the worst-case number of comparisons used by both binary insertion sort and merge sort. However, there are other algorithms that use fewer comparisons.

Hunter Snevily (1956–2013) was an American mathematician with expertise and contributions in Set theory, Graph theory, Discrete geometry, and Ramsey theory on the integers.

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 , hdl: 10453/98769 , 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, arXiv: 1108.0989 , 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, doi: 10.37236/2442 , MR 2967225 .
Albert, Michael H.; Atkinson, M. D.; Vatter, Vincent (2009), "Counting 1324, 4231-avoiding permutations", Electronic Journal of Combinatorics , 16 (1): Paper 136, 9 pp, arXiv: 1102.5568 , doi:10.37236/225, 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 (2018), "Generating permutations with restricted containers", Journal of Combinatorial Theory, Series A , 157: 205–232, arXiv: 1510.00269 , doi:10.1016/j.jcta.2018.02.006, MR 3780412 .
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 , MR 1490467 .
Atkinson, M. D. (1999), "Restricted permutations", Discrete Mathematics , 195 (1–3): 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, arXiv: 1406.2890 , doi:10.1112/jlms/jdv020, MR 3384507 .
Bevan, David (2016a), "The permutation classes Av(1234,2341) and Av(1243,2314)" (PDF), Australasian Journal of Combinatorics , 64 (1): 3–20, MR 3426209 .
Bevan, David (2016b), "The permutation class Av(4213,2143)", Discrete Mathematics & Theoretical Computer Science , 18 (2): 14 pp, arXiv: 1510.06328 , doi:10.46298/dmtcs.1309 .
Bevan, David; Brignall, Robert; Elvey Price, Andrew; Pantone, Jay (2017), A structural characterisation of Av(1324) and new bounds on its growth rate, arXiv: 1711.10325 , Bibcode:2017arXiv171110325B .
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", Journal of Combinatorial Theory, Series A , 80 (2): 257–272, arXiv: math/9702223 , 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, doi: 10.37236/1369 , MR 1626487 .
Bóna, Miklós (2015), "A new record for 1324-avoiding permutations", European Journal of Mathematics , 1 (1): 198–206, arXiv: 1404.4033 , doi:10.1007/s40879-014-0020-6, MR 3386234 .
Callan, David (2013a), "The number of {1243, 2134}-avoiding permutations", Discrete Mathematics & Theoretical Computer Science, arXiv: 1303.3857 , Bibcode:2013arXiv1303.3857C, doi:10.46298/dmtcs.5287 .
Callan, David (2013b), "Permutations avoiding 4321 and 3241 have an algebraic generating function", Discrete Mathematics & Theoretical Computer Science, arXiv: 1306.3193 , Bibcode:2013arXiv1306.3193C, doi:10.46298/dmtcs.5286 .
Conway, Andrew; Guttmann, Anthony (2015), "On 1324-avoiding permutations", Advances in Applied Mathematics , 64: 50–69, doi:10.1016/j.aam.2014.12.004, MR 3300327 .
Conway, Andrew; Guttmann, Anthony; Zinn-Justin, Paul (2018), "1324-avoiding permutations revisited", Advances in Applied Mathematics , 96: 312–333, arXiv: 1709.01248 , 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, MR 1041448 .
Johansson, Fredrik; Nakamura, Brian (2014), "Using functional equations to enumerate 1324-avoiding permutations", Advances in Applied Mathematics , 56: 20–34, arXiv: 1309.7117 , 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 978-0-201-89683-1, MR 0286317, 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, MR 1754331 .
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, MR 1997910 .
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, MR 1983276 .
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 , MR 2156679 .
MacMahon, Percy A. (1916), Combinatory Analysis, London: Cambridge University Press, MR 0141605 .
Marinov, Darko; Radoičić, Radoš (2003), "Counting 1324-avoiding permutations", Electronic Journal of Combinatorics , 9 (2): Paper 13, 9 pp, doi: 10.37236/1685 , MR 2028282 .
Miner, Sam (2016), Enumeration of several two-by-four classes, arXiv: 1610.01908 , Bibcode:2016arXiv161001908M .
Miner, Sam; Pantone, Jay (2018), Completing the structural analysis of the 2x4 permutation classes, arXiv: 1802.00483 , Bibcode:2018arXiv180200483M .
Pantone, Jay (2017), "The enumeration of permutations avoiding 3124 and 4312", Annals of Combinatorics , 21 (2): 293–315, arXiv: 1309.0832 , doi:10.1007/s00026-017-0352-2 .
Simion, Rodica; Schmidt, Frank W. (1985), "Restricted permutations", European Journal of Combinatorics , 6 (4): 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 (3): 259–265, arXiv: 0911.2683 , doi:10.1016/j.jsc.2011.11.002, MR 2869320 .
West, Julian (1996), "Generating trees and forbidden subsequences", Discrete Mathematics , 157 (1–3): 363–374, doi:10.1016/S0012-365X(96)83023-8, MR 1417303 .

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.

This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.