Английская Википедия: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 |
---|---|---|---|---|
1, 2, 5, 14, 42, 132, 429, 1430, ... | Шаблон:OEIS link | algebraic (nonrational) g.f. Catalan numbers |
Шаблон:Harvtxt Шаблон: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 |
---|---|---|---|---|
1, 2, 6, 23, 103, 512, 2740, 15485, ... | Шаблон:OEIS link | algebraic (nonrational) g.f. | Шаблон:Harvtxt | |
1, 2, 6, 23, 103, 513, 2761, 15767, ... | Шаблон:OEIS link | holonomic (nonalgebraic) g.f. | Шаблон:Harvtxt | |
1324 | 1, 2, 6, 23, 103, 513, 2762, 15793, ... | Шаблон:OEIS link |
No non-recursive formula counting 1324-avoiding permutations is known. A recursive formula was given by Шаблон:Harvtxt. A more efficient algorithm using functional equations was given by Шаблон:Harvtxt, which was enhanced by Шаблон:Harvtxt, and then further enhanced by Шаблон:Harvtxt who give the first 50 terms of the enumeration. Шаблон: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 Шаблон: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, ... | Шаблон:OEIS link | polynomial, <math>{n\choose 2}+1</math> |
1, 2, 4, 8, 16, 32, 64, 128, ... | Шаблон:OEIS link | rational g.f., <math>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 Шаблон:Harvtxt or Шаблон: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, ... | Шаблон:OEIS link | polynomial |
132, 4321 | 1, 2, 5, 13, 31, 66, 127, 225, ... | Шаблон:OEIS link | polynomial |
321, 1324 | 1, 2, 5, 13, 32, 72, 148, 281, ... | Шаблон:OEIS link | polynomial |
321, 1342 | 1, 2, 5, 13, 32, 74, 163, 347, ... | Шаблон:OEIS link | rational g.f. |
321, 2143 | 1, 2, 5, 13, 33, 80, 185, 411, ... | Шаблон:OEIS link | rational g.f. |
1, 2, 5, 13, 33, 81, 193, 449, ... | Шаблон:OEIS link | rational g.f. | |
132, 3214 | 1, 2, 5, 13, 33, 82, 202, 497, ... | Шаблон:OEIS link | rational g.f. |
321, 2341 |
1, 2, 5, 13, 34, 89, 233, 610, ... | Шаблон:OEIS link | 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 Шаблон: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 <math>(i,j)</math> represents how many permutations have value <math>j</math> at index <math>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, ... | Шаблон:OEIS link | finite | Erdős–Szekeres theorem |
4312, 1234 | 1, 2, 6, 22, 86, 321, 1085, 3266, ... | Шаблон:OEIS link | polynomial | Шаблон:Harvtxt |
4321, 3124 | 1, 2, 6, 22, 86, 330, 1198, 4087, ... | Шаблон:OEIS link | rational g.f. | Шаблон:Harvtxt |
4312, 2134 | 1, 2, 6, 22, 86, 330, 1206, 4174, ... | Шаблон:OEIS link | rational g.f. | Шаблон:Harvtxt |
4321, 1324 | 1, 2, 6, 22, 86, 332, 1217, 4140, ... | Шаблон:OEIS link | polynomial | Шаблон:Harvtxt |
4321, 2143 | 1, 2, 6, 22, 86, 333, 1235, 4339, ... | Шаблон:OEIS link | rational g.f. | Шаблон:Harvtxt |
4312, 1324 | 1, 2, 6, 22, 86, 335, 1266, 4598, ... | Шаблон:OEIS link | rational g.f. | Шаблон:Harvtxt |
4231, 2143 | 1, 2, 6, 22, 86, 335, 1271, 4680, ... | Шаблон:OEIS link | rational g.f. | Шаблон:Harvtxt |
4231, 1324 | 1, 2, 6, 22, 86, 336, 1282, 4758, ... | Шаблон:OEIS link | rational g.f. | Шаблон:Harvtxt |
4213, 2341 | 1, 2, 6, 22, 86, 336, 1290, 4870, ... | Шаблон:OEIS link | rational g.f. | Шаблон:Harvtxt |
4312, 2143 | 1, 2, 6, 22, 86, 337, 1295, 4854, ... | Шаблон:OEIS link | rational g.f. | Шаблон:Harvtxt |
4213, 1243 | 1, 2, 6, 22, 86, 337, 1299, 4910, ... | Шаблон:OEIS link | rational g.f. | Шаблон:Harvtxt |
4321, 3142 | 1, 2, 6, 22, 86, 338, 1314, 5046, ... | Шаблон:OEIS link | rational g.f. | Шаблон:Harvtxt |
4213, 1342 | 1, 2, 6, 22, 86, 338, 1318, 5106, ... | Шаблон:OEIS link | rational g.f. | Шаблон:Harvtxt |
4312, 2341 | 1, 2, 6, 22, 86, 338, 1318, 5110, ... | Шаблон:OEIS link | rational g.f. | Шаблон:Harvtxt |
3412, 2143 | 1, 2, 6, 22, 86, 340, 1340, 5254, ... | Шаблон:OEIS link | algebraic (nonrational) g.f. | Шаблон:Harvtxt |
1, 2, 6, 22, 86, 342, 1366, 5462, ... | Шаблон:OEIS link | rational g.f. | Шаблон:Harvtxt | |
4123, 2341 | 1, 2, 6, 22, 87, 348, 1374, 5335, ... | Шаблон:OEIS link | algebraic (nonrational) g.f. | Шаблон:Harvtxt |
4231, 3214 | 1, 2, 6, 22, 87, 352, 1428, 5768, ... | Шаблон:OEIS link | algebraic (nonrational) g.f. | Шаблон:Harvtxt |
4213, 1432 | 1, 2, 6, 22, 87, 352, 1434, 5861, ... | Шаблон:OEIS link | algebraic (nonrational) g.f. | Шаблон:Harvtxt |
1, 2, 6, 22, 87, 354, 1459, 6056, ... | Шаблон:OEIS link | algebraic (nonrational) g.f. | Шаблон:Harvtxt established the Wilf-equivalence; Шаблон:Harvtxt determined the enumeration. | |
4312, 3124 | 1, 2, 6, 22, 88, 363, 1507, 6241, ... | Шаблон:OEIS link | algebraic (nonrational) g.f. | Шаблон:Harvtxt |
4231, 3124 | 1, 2, 6, 22, 88, 363, 1508, 6255, ... | Шаблон:OEIS link | algebraic (nonrational) g.f. | Шаблон:Harvtxt |
4312, 3214 | 1, 2, 6, 22, 88, 365, 1540, 6568, ... | Шаблон:OEIS link | algebraic (nonrational) g.f. | Шаблон:Harvtxt |
1, 2, 6, 22, 88, 366, 1552, 6652, ... | Шаблон:OEIS link | algebraic (nonrational) g.f. | Шаблон:Harvtxt | |
4213, 2143 | 1, 2, 6, 22, 88, 366, 1556, 6720, ... | Шаблон:OEIS link | algebraic (nonrational) g.f. | Шаблон:Harvtxt |
4312, 3142 | 1, 2, 6, 22, 88, 367, 1568, 6810, ... | Шаблон:OEIS link | algebraic (nonrational) g.f. | Шаблон:Harvtxt |
4213, 3421 | 1, 2, 6, 22, 88, 367, 1571, 6861, ... | Шаблон:OEIS link | algebraic (nonrational) g.f. | Шаблон:Harvtxt |
1, 2, 6, 22, 88, 368, 1584, 6968, ... | Шаблон:OEIS link | algebraic (nonrational) g.f. | Шаблон:Harvtxt | |
4321, 3214 | 1, 2, 6, 22, 89, 376, 1611, 6901, ... | Шаблон:OEIS link | algebraic (nonrational) g.f. | Шаблон:Harvtxt |
4213, 3142 | 1, 2, 6, 22, 89, 379, 1664, 7460, ... | Шаблон:OEIS link | algebraic (nonrational) g.f. | Шаблон:Harvtxt |
4231, 4123 | 1, 2, 6, 22, 89, 380, 1677, 7566, ... | Шаблон:OEIS link | conjectured to not satisfy any ADE, see Шаблон:Harvtxt | |
4321, 4213 | 1, 2, 6, 22, 89, 380, 1678, 7584, ... | Шаблон:OEIS link | algebraic (nonrational) g.f. | Шаблон:Harvtxt; see also Шаблон:Harvtxt |
4123, 3412 | 1, 2, 6, 22, 89, 381, 1696, 7781, ... | Шаблон:OEIS link | algebraic (nonrational) g.f. | Шаблон:Harvtxt |
4312, 4123 | 1, 2, 6, 22, 89, 382, 1711, 7922, ... | Шаблон:OEIS link | conjectured to not satisfy any ADE, see Шаблон:Harvtxt | |
4321, 4312 |
1, 2, 6, 22, 90, 394, 1806, 8558, ... | Шаблон:OEIS link | Schröder numbers algebraic (nonrational) g.f. |
Шаблон:Harvtxt, Шаблон:Harvtxt |
3412, 2413 | 1, 2, 6, 22, 90, 395, 1823, 8741, ... | Шаблон:OEIS link | algebraic (nonrational) g.f. | Шаблон:Harvtxt |
4321, 4231 | 1, 2, 6, 22, 90, 396, 1837, 8864, ... | Шаблон:OEIS link | conjectured to not satisfy any ADE, see Шаблон:Harvtxt |
See also
References
- Шаблон:Citation.
- Шаблон:Citation.
- Шаблон:Citation.
- Шаблон:Citation.
- Шаблон:Citation.
- Шаблон:Citation.
- Шаблон:Citation.
- Шаблон:Citation.
- Шаблон:Citation.
- Шаблон:Citation.
- Шаблон:Citation.
- Шаблон:Citation.
- Шаблон:Citation.
- Шаблон:Citation.
- Шаблон:Citation.
- Шаблон:Citation.
- Шаблон:Citation.
- Шаблон:Citation.
- Шаблон:Citation.
- Шаблон:Citation.
- Шаблон:Citation.
- Шаблон:Citation.
- Шаблон:Citation.
- Шаблон:Citation.
- Шаблон:Citation.
- Шаблон:Citation.
- Шаблон:Citation.
- Шаблон:Citation.
- Шаблон:Citation.
- Шаблон:Citation.
- Шаблон:Citation.
- Шаблон:Citation.
- Шаблон:Citation.
- Шаблон:Citation.
- Шаблон:Citation.
- Шаблон:Citation.
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.