Enumerations of specific permutation classes

From testwiki
Revision as of 22:57, 2 November 2024 by imported>David Eppstein (Bridget Tenner)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to navigation Jump to search

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, ... Template:OEIS link algebraic (nonrational) g.f.
Catalan numbers		 Template:Harvtxt
Template:Harvtxt

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, ... Template:OEIS link algebraic (nonrational) g.f. Template:Harvtxt

1234
1243
1432
2143

1, 2, 6, 23, 103, 513, 2761, 15767, ... Template:OEIS link holonomic (nonalgebraic) g.f. Template:Harvtxt
1324 1, 2, 6, 23, 103, 513, 2762, 15793, ... Template:OEIS link

No non-recursive formula counting 1324-avoiding permutations is known. A recursive formula was given by Template:Harvtxt. A more efficient algorithm using functional equations was given by Template:Harvtxt, which was enhanced by Template:Harvtxt, and then further enhanced by Template:Harvtxt who give the first 50 terms of the enumeration. Template:Harvtxt 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 Template:Harvtxt.

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, ... Template:OEIS link polynomial, (n2)+1

231, 321
132, 312
231, 312

1, 2, 4, 8, 16, 32, 64, 128, ... Template:OEIS link rational g.f., 2n−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 Template:Harvtxt or Template:Harvtxt.

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, ... Template:OEIS link polynomial
132, 4321 1, 2, 5, 13, 31, 66, 127, 225, ... Template:OEIS link polynomial
321, 1324 1, 2, 5, 13, 32, 72, 148, 281, ... Template:OEIS link polynomial
321, 1342 1, 2, 5, 13, 32, 74, 163, 347, ... Template:OEIS link rational g.f.
321, 2143 1, 2, 5, 13, 33, 80, 185, 411, ... Template:OEIS link rational g.f.

132, 4312
132, 4231

1, 2, 5, 13, 33, 81, 193, 449, ... Template:OEIS link rational g.f.
132, 3214 1, 2, 5, 13, 33, 82, 202, 497, ... Template:OEIS link 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, ... Template:OEIS link 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 Template:Harvtxt; 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, ... Template:OEIS link finite Erdős–Szekeres theorem
4312, 1234 1, 2, 6, 22, 86, 321, 1085, 3266, ... Template:OEIS link polynomial Template:Harvtxt
4321, 3124 1, 2, 6, 22, 86, 330, 1198, 4087, ... Template:OEIS link rational g.f. Template:Harvtxt
4312, 2134 1, 2, 6, 22, 86, 330, 1206, 4174, ... Template:OEIS link rational g.f. Template:Harvtxt
4321, 1324 1, 2, 6, 22, 86, 332, 1217, 4140, ... Template:OEIS link polynomial Template:Harvtxt
4321, 2143 1, 2, 6, 22, 86, 333, 1235, 4339, ... Template:OEIS link rational g.f. Template:Harvtxt
4312, 1324 1, 2, 6, 22, 86, 335, 1266, 4598, ... Template:OEIS link rational g.f. Template:Harvtxt
4231, 2143 1, 2, 6, 22, 86, 335, 1271, 4680, ... Template:OEIS link rational g.f. Template:Harvtxt
4231, 1324 1, 2, 6, 22, 86, 336, 1282, 4758, ... Template:OEIS link rational g.f. Template:Harvtxt
4213, 2341 1, 2, 6, 22, 86, 336, 1290, 4870, ... Template:OEIS link rational g.f. Template:Harvtxt
4312, 2143 1, 2, 6, 22, 86, 337, 1295, 4854, ... Template:OEIS link rational g.f. Template:Harvtxt
4213, 1243 1, 2, 6, 22, 86, 337, 1299, 4910, ... Template:OEIS link rational g.f. Template:Harvtxt
4321, 3142 1, 2, 6, 22, 86, 338, 1314, 5046, ... Template:OEIS link rational g.f. Template:Harvtxt
4213, 1342 1, 2, 6, 22, 86, 338, 1318, 5106, ... Template:OEIS link rational g.f. Template:Harvtxt
4312, 2341 1, 2, 6, 22, 86, 338, 1318, 5110, ... Template:OEIS link rational g.f. Template:Harvtxt
3412, 2143 1, 2, 6, 22, 86, 340, 1340, 5254, ... Template:OEIS link algebraic (nonrational) g.f. Template:Harvtxt

4321, 4123
4321, 3412
4123, 3214
4123, 2143

1, 2, 6, 22, 86, 342, 1366, 5462, ... Template:OEIS link rational g.f. Template:Harvtxt
4123, 2341 1, 2, 6, 22, 87, 348, 1374, 5335, ... Template:OEIS link algebraic (nonrational) g.f. Template:Harvtxt
4231, 3214 1, 2, 6, 22, 87, 352, 1428, 5768, ... Template:OEIS link algebraic (nonrational) g.f. Template:Harvtxt
4213, 1432 1, 2, 6, 22, 87, 352, 1434, 5861, ... Template:OEIS link algebraic (nonrational) g.f. Template:Harvtxt

4312, 3421
4213, 2431

1, 2, 6, 22, 87, 354, 1459, 6056, ... Template:OEIS link algebraic (nonrational) g.f. Template:Harvtxt established the Wilf-equivalence;
Template:Harvtxt determined the enumeration.
4312, 3124 1, 2, 6, 22, 88, 363, 1507, 6241, ... Template:OEIS link algebraic (nonrational) g.f. Template:Harvtxt
4231, 3124 1, 2, 6, 22, 88, 363, 1508, 6255, ... Template:OEIS link algebraic (nonrational) g.f. Template:Harvtxt
4312, 3214 1, 2, 6, 22, 88, 365, 1540, 6568, ... Template:OEIS link algebraic (nonrational) g.f. Template:Harvtxt

4231, 3412
4231, 3142
4213, 3241
4213, 3124
4213, 2314

1, 2, 6, 22, 88, 366, 1552, 6652, ... Template:OEIS link algebraic (nonrational) g.f. Template:Harvtxt
4213, 2143 1, 2, 6, 22, 88, 366, 1556, 6720, ... Template:OEIS link algebraic (nonrational) g.f. Template:Harvtxt
4312, 3142 1, 2, 6, 22, 88, 367, 1568, 6810, ... Template:OEIS link algebraic (nonrational) g.f. Template:Harvtxt
4213, 3421 1, 2, 6, 22, 88, 367, 1571, 6861, ... Template:OEIS link algebraic (nonrational) g.f. Template:Harvtxt

4213, 3412
4123, 3142

1, 2, 6, 22, 88, 368, 1584, 6968, ... Template:OEIS link algebraic (nonrational) g.f. Template:Harvtxt
4321, 3214 1, 2, 6, 22, 89, 376, 1611, 6901, ... Template:OEIS link algebraic (nonrational) g.f. Template:Harvtxt
4213, 3142 1, 2, 6, 22, 89, 379, 1664, 7460, ... Template:OEIS link algebraic (nonrational) g.f. Template:Harvtxt
4231, 4123 1, 2, 6, 22, 89, 380, 1677, 7566, ... Template:OEIS link conjectured to not satisfy any ADE, see Template:Harvtxt
4321, 4213 1, 2, 6, 22, 89, 380, 1678, 7584, ... Template:OEIS link algebraic (nonrational) g.f. Template:Harvtxt; see also Template:Harvtxt
4123, 3412 1, 2, 6, 22, 89, 381, 1696, 7781, ... Template:OEIS link algebraic (nonrational) g.f. Template:Harvtxt
4312, 4123 1, 2, 6, 22, 89, 382, 1711, 7922, ... Template:OEIS link conjectured to not satisfy any ADE, see Template:Harvtxt

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, ... Template:OEIS link Schröder numbers
algebraic (nonrational) g.f.		 Template:Harvtxt, Template:Harvtxt
3412, 2413 1, 2, 6, 22, 90, 395, 1823, 8741, ... Template:OEIS link algebraic (nonrational) g.f. Template:Harvtxt
4321, 4231 1, 2, 6, 22, 90, 396, 1837, 8864, ... Template:OEIS link conjectured to not satisfy any ADE, see Template:Harvtxt

See also

References

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.

Retrieved from "https://en.wiki.beta.math.wmflabs.org/w/index.php?title=Enumerations_of_specific_permutation_classes&oldid=30861"