Enumerations of specific permutation classes
Encyclopedia
In the study of permutation pattern
s, there has been considerable interest in enumerating specific permutation classes, especially those with relatively few basis elements.
No non-recursive formula counting 1324-avoiding permutations is known. A recursive formula was given by and have provided lower bounds for the growth of this class.
Permutation pattern
In combinatorial mathematics and theoretical computer science, a permutation pattern is a sub-permutation of a longer permutation. The permutation π, written as a word in one-line notation , is said to contain the permutation σ if there exists a subsequence of entries of π that has the same...
s, 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.| β | sequence enumerating Avn(β) | OEIS On-Line Encyclopedia of Integer Sequences The On-Line Encyclopedia of Integer Sequences , also cited simply as Sloane's, is an online database of integer sequences, created and maintained by N. J. A. Sloane, a researcher at AT&T Labs... | type of sequence | exact enumeration reference |
|---|---|---|---|---|
| 123 231 |
1, 2, 5, 14, 42, 132, 429, 1430, ... | algebraic (nonrational) g.f. Generating function In mathematics, a generating function is a formal power series in one indeterminate, whose coefficients encode information about a sequence of numbers an that is indexed by the natural numbers. Generating functions were first introduced by Abraham de Moivre in 1730, in order to solve the general... Catalan numbers |
|
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 On-Line Encyclopedia of Integer Sequences The On-Line Encyclopedia of Integer Sequences , also cited simply as Sloane's, is an online database of integer sequences, created and maintained by N. J. A. Sloane, a researcher at AT&T Labs... | type of sequence | exact enumeration reference |
|---|---|---|---|---|
| 1342 2413 |
1, 2, 6, 23, 103, 512, 2740, 15485, ... | algebraic (nonrational) g.f. Generating function In mathematics, a generating function is a formal power series in one indeterminate, whose coefficients encode information about a sequence of numbers an that is indexed by the natural numbers. Generating functions were first introduced by Abraham de Moivre in 1730, in order to solve the general... |
||
| 1234 1243 1432 2143 |
1, 2, 6, 23, 103, 513, 2761, 15767, ... | holonomic (nonalgebraic) g.f. Generating function In mathematics, a generating function is a formal power series in one indeterminate, whose coefficients encode information about a sequence of numbers an that is indexed by the natural numbers. Generating functions were first introduced by Abraham de Moivre in 1730, in order to solve the general... |
||
| 1324 | 1, 2, 6, 23, 103, 513, 2762, 15793, ... |
No non-recursive formula counting 1324-avoiding permutations is known. A recursive formula was given by and have provided lower 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 .| B | sequence enumerating Avn(B) | OEIS On-Line Encyclopedia of Integer Sequences The On-Line Encyclopedia of Integer Sequences , also cited simply as Sloane's, is an online database of integer sequences, created and maintained by N. J. A. Sloane, a researcher at AT&T Labs... | 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, ... | polynomial,  |
|
| 123, 132 132, 312 231, 312 |
1, 2, 4, 8, 16, 32, 64, 128, ... | rational g.f. Generating function In mathematics, a generating function is a formal power series in one indeterminate, whose coefficients encode information about a sequence of numbers an that is indexed by the natural numbers. Generating functions were first introduced by Abraham de Moivre in 1730, in order to solve the general... ,  |
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 or .| B | sequence enumerating Avn(B) | OEIS On-Line Encyclopedia of Integer Sequences The On-Line Encyclopedia of Integer Sequences , also cited simply as Sloane's, is an online database of integer sequences, created and maintained by N. J. A. Sloane, a researcher at AT&T Labs... | 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, ... | polynomial | |
| 132, 4321 | 1, 2, 5, 13, 31, 66, 127, 225, ... | polynomial | |
| 321, 1324 | 1, 2, 5, 13, 32, 72, 148, 281, ... | polynomial | |
| 321, 1342 | 1, 2, 5, 13, 32, 74, 163, 347, ... | rational g.f. Generating function In mathematics, a generating function is a formal power series in one indeterminate, whose coefficients encode information about a sequence of numbers an that is indexed by the natural numbers. Generating functions were first introduced by Abraham de Moivre in 1730, in order to solve the general... |
|
| 321, 2143 | 1, 2, 5, 13, 33, 80, 185, 411, ... | rational g.f. Generating function In mathematics, a generating function is a formal power series in one indeterminate, whose coefficients encode information about a sequence of numbers an that is indexed by the natural numbers. Generating functions were first introduced by Abraham de Moivre in 1730, in order to solve the general... |
|
| 132, 4312 132, 4231 |
1, 2, 5, 13, 33, 81, 193, 449, ... | rational g.f. Generating function In mathematics, a generating function is a formal power series in one indeterminate, whose coefficients encode information about a sequence of numbers an that is indexed by the natural numbers. Generating functions were first introduced by Abraham de Moivre in 1730, in order to solve the general... |
|
| 132, 3214 | 1, 2, 5, 13, 33, 82, 202, 497, ... | rational g.f. Generating function In mathematics, a generating function is a formal power series in one indeterminate, whose coefficients encode information about a sequence of numbers an that is indexed by the natural numbers. Generating functions were first introduced by Abraham de Moivre in 1730, in order to solve the general... |
|
| 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, ... | rational g.f. Generating function In mathematics, a generating function is a formal power series in one indeterminate, whose coefficients encode information about a sequence of numbers an that is indexed by the natural numbers. Generating functions were first introduced by Abraham de Moivre in 1730, in order to solve the general... , alternate Fibonacci number Fibonacci number In mathematics, the Fibonacci numbers are the numbers in the following integer sequence:0,\;1,\;1,\;2,\;3,\;5,\;8,\;13,\;21,\;34,\;55,\;89,\;144,\; \ldots\; .... s |
Classes avoiding two patterns of length 4
There are 56 symmetry classes and 38 Wilf equivalence classes, of which 18 have been enumerated.| B | sequence enumerating Avn(B) | OEIS On-Line Encyclopedia of Integer Sequences The On-Line Encyclopedia of Integer Sequences , also cited simply as Sloane's, is an online database of integer sequences, created and maintained by N. J. A. Sloane, a researcher at AT&T Labs... | type of sequence | exact enumeration reference |
|---|---|---|---|---|
| 4321, 1234 | 1, 2, 6, 22, 86, 306, 882, 1764, ... | n/a | finite | Erdős–Szekeres theorem Erdos–Szekeres theorem In mathematics, the Erdős–Szekeres theorem is a finitary result that makes precise one of the corollaries of Ramsey's theorem. While Ramsey's theorem makes it easy to prove that every sequence of distinct real numbers contains either a monotonically increasing infinite subsequence, or a... |
| 4312, 1234 | 1, 2, 6, 22, 86, 321, 1085, 3266, ... | polynomial | ||
| 4321, 3124 | 1, 2, 6, 22, 86, 330, 1198, 4087, ... | rational g.f. Generating function In mathematics, a generating function is a formal power series in one indeterminate, whose coefficients encode information about a sequence of numbers an that is indexed by the natural numbers. Generating functions were first introduced by Abraham de Moivre in 1730, in order to solve the general... |
||
| 4312, 2134 | 1, 2, 6, 22, 86, 330, 1206, 4174, ... | rational g.f. Generating function In mathematics, a generating function is a formal power series in one indeterminate, whose coefficients encode information about a sequence of numbers an that is indexed by the natural numbers. Generating functions were first introduced by Abraham de Moivre in 1730, in order to solve the general... |
||
| 4321, 1324 | 1, 2, 6, 22, 86, 332, 1217, 4140, ... | polynomial | ||
| 4321, 2143 | 1, 2, 6, 22, 86, 333, 1235, 4339, ... | |||
| 4312, 1324 | 1, 2, 6, 22, 86, 335, 1266, 4598, ... | |||
| 4231, 2143 | 1, 2, 6, 22, 86, 335, 1271, 4680, ... | rational g.f. Generating function In mathematics, a generating function is a formal power series in one indeterminate, whose coefficients encode information about a sequence of numbers an that is indexed by the natural numbers. Generating functions were first introduced by Abraham de Moivre in 1730, in order to solve the general... |
||
| 4231, 1324 | 1, 2, 6, 22, 86, 336, 1282, 4758, ... | rational g.f. Generating function In mathematics, a generating function is a formal power series in one indeterminate, whose coefficients encode information about a sequence of numbers an that is indexed by the natural numbers. Generating functions were first introduced by Abraham de Moivre in 1730, in order to solve the general... |
||
| 4213, 2341 | 1, 2, 6, 22, 86, 336, 1290, 4870, ... | rational g.f. Generating function In mathematics, a generating function is a formal power series in one indeterminate, whose coefficients encode information about a sequence of numbers an that is indexed by the natural numbers. Generating functions were first introduced by Abraham de Moivre in 1730, in order to solve the general... |
||
| 4312, 2143 | 1, 2, 6, 22, 86, 337, 1295, 4854, ... | |||
| 4213, 1243 | 1, 2, 6, 22, 86, 337, 1299, 4910, ... | rational g.f. Generating function In mathematics, a generating function is a formal power series in one indeterminate, whose coefficients encode information about a sequence of numbers an that is indexed by the natural numbers. Generating functions were first introduced by Abraham de Moivre in 1730, in order to solve the general... |
||
| 4321, 3142 | 1, 2, 6, 22, 86, 338, 1314, 5046, ... | rational g.f. Generating function In mathematics, a generating function is a formal power series in one indeterminate, whose coefficients encode information about a sequence of numbers an that is indexed by the natural numbers. Generating functions were first introduced by Abraham de Moivre in 1730, in order to solve the general... |
||
| 4213, 1342 | 1, 2, 6, 22, 86, 338, 1318, 5106, ... | rational g.f. Generating function In mathematics, a generating function is a formal power series in one indeterminate, whose coefficients encode information about a sequence of numbers an that is indexed by the natural numbers. Generating functions were first introduced by Abraham de Moivre in 1730, in order to solve the general... |
||
| 4312, 2341 | 1, 2, 6, 22, 86, 338, 1318, 5110, ... | rational g.f. Generating function In mathematics, a generating function is a formal power series in one indeterminate, whose coefficients encode information about a sequence of numbers an that is indexed by the natural numbers. Generating functions were first introduced by Abraham de Moivre in 1730, in order to solve the general... |
||
| 3412, 2143 | 1, 2, 6, 22, 86, 340, 1340, 5254, ... | algebraic (nonrational) g.f. Generating function In mathematics, a generating function is a formal power series in one indeterminate, whose coefficients encode information about a sequence of numbers an that is indexed by the natural numbers. Generating functions were first introduced by Abraham de Moivre in 1730, in order to solve the general... |
||
| 4321, 4123 4321, 3412 4123, 3142 4123, 2143 |
1, 2, 6, 22, 86, 342, 1366, 5462, ... | rational g.f. Generating function In mathematics, a generating function is a formal power series in one indeterminate, whose coefficients encode information about a sequence of numbers an that is indexed by the natural numbers. Generating functions were first introduced by Abraham de Moivre in 1730, in order to solve the general... |
||
| 4123, 2341 | 1, 2, 6, 22, 87, 348, 1374, 5335, ... | algebraic (nonrational) g.f. Generating function In mathematics, a generating function is a formal power series in one indeterminate, whose coefficients encode information about a sequence of numbers an that is indexed by the natural numbers. Generating functions were first introduced by Abraham de Moivre in 1730, in order to solve the general... |
||
| 4231, 3214 | 1, 2, 6, 22, 87, 352, 1428, 5768, ... | |||
| 4213, 1432 | 1, 2, 6, 22, 87, 352, 1434, 5861, ... | |||
| 4312, 3421 4213, 2431 |
1, 2, 6, 22, 87, 354, 1459, 6056, ... | see , but g.f. Generating function In mathematics, a generating function is a formal power series in one indeterminate, whose coefficients encode information about a sequence of numbers an that is indexed by the natural numbers. Generating functions were first introduced by Abraham de Moivre in 1730, in order to solve the general... unknown |
||
| 4312, 3124 | 1, 2, 6, 22, 88, 363, 1507, 6241, ... | |||
| 4231, 3124 | 1, 2, 6, 22, 88, 363, 1508, 6255, ... | |||
| 4312, 3214 | 1, 2, 6, 22, 88, 365, 1540, 6568, ... | |||
| 4231, 3412 4231, 3142 4213, 3241 4213, 3124 4213, 2314 |
1, 2, 6, 22, 88, 366, 1552, 6652, ... | algebraic (nonrational) g.f. Generating function In mathematics, a generating function is a formal power series in one indeterminate, whose coefficients encode information about a sequence of numbers an that is indexed by the natural numbers. Generating functions were first introduced by Abraham de Moivre in 1730, in order to solve the general... |
||
| 4213, 2143 | 1, 2, 6, 22, 88, 366, 1556, 6720, ... | |||
| 4312, 3142 | 1, 2, 6, 22, 88, 367, 1568, 6810, ... | |||
| 4213, 3421 | 1, 2, 6, 22, 88, 367, 1571, 6861, ... | |||
| 4213, 3412 4123, 3142 |
1, 2, 6, 22, 88, 368, 1584, 6968, ... | algebraic (nonrational) g.f. Generating function In mathematics, a generating function is a formal power series in one indeterminate, whose coefficients encode information about a sequence of numbers an that is indexed by the natural numbers. Generating functions were first introduced by Abraham de Moivre in 1730, in order to solve the general... |
||
| 4321, 3214 | 1, 2, 6, 22, 89, 376, 1611, 6901, ... | |||
| 4213, 3142 | 1, 2, 6, 22, 89, 379, 1664, 7460, ... | |||
| 4231, 4123 | 1, 2, 6, 22, 89, 380, 1677, 7566, ... | |||
| 4321, 4213 | 1, 2, 6, 22, 89, 380, 1678, 7584, ... | |||
| 4123, 3412 | 1, 2, 6, 22, 89, 381, 1696, 7781, ... | |||
| 4312, 4123 | 1, 2, 6, 22, 89, 382, 1711, 7922, ... | |||
| 4321, 4312 4312, 4231 4312, 4213 4312, 3412 4231, 4213 4213, 4132 4213, 4123 4213, 2413 4213, 3214 3142, 2413 Separable permutation In combinatorial mathematics, a separable permutation is a permutation that can be obtained from the trivial permutation 1 by direct sums and skew sums. Separable permutations can also be characterized as the permutations that contain neither 2413 nor 3142... |
1, 2, 6, 22, 90, 394, 1806, 8558, ... | algebraic (nonrational) g.f. Generating function In mathematics, a generating function is a formal power series in one indeterminate, whose coefficients encode information about a sequence of numbers an that is indexed by the natural numbers. Generating functions were first introduced by Abraham de Moivre in 1730, in order to solve the general... Schröder number Schröder number In mathematics, a Schröder number describes the number of paths from the southwest corner of an n × n grid to the northeast corner , using only single steps north, northeast, or east, that do not rise above the SW–NE diagonal.The first few Schröder numbers are-Examples:The following... s |
, | |
| 3412, 2413 | 1, 2, 6, 22, 90, 395, 1823, 8741, ... | |||
| 4321, 4231 | 1, 2, 6, 22, 90, 396, 1837, 8864, ... |