Enumerations Of Specific Permutation Classes on:
[Wikipedia]
[Google]
[Amazon]
In the study of
There are 56 symmetry classes and 38 Wilf equivalence classes. Only 3 of these remain unenumerated, and their
PermPal
maintained by Bridget Tenner, contains details of the enumeration of many other permutation classes with relatively few basis elements.
permutation pattern In combinatorial mathematics and theoretical computer science, a permutation pattern is a sub-permutation of a longer permutation. Any permutation may be written in one-line notation as a sequence of digits representing the result of applying the p ...
s, there has been considerable interest in enumerating specific permutation class In the study of permutations and permutation patterns, a permutation class is a set C of permutations for which every pattern within a permutation in C is also in C. In other words, a permutation class is a hereditary property of permutations, or a ...
es, 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 singleWilf class In the study of permutations and permutation patterns, Wilf equivalence is an equivalence relation on permutation classes.
Two permutation classes are Wilf equivalent when they have the same numbers of permutations of each possible length, or equiv ...
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 . A more efficient algorithm using functional equations was given by , which was enhanced by , and then further enhanced by who give the first 50 terms of the enumeration. 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 .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 .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 function
In mathematics, a generating function is a way of encoding an infinite sequence of numbers () by treating them as the coefficients of a formal power series. This series is called the generating function of the sequence. Unlike an ordinary seri ...
s are conjectured not to satisfy any algebraic differential equation
In mathematics, an algebraic differential equation is a differential equation that can be expressed by means of differential algebra. There are several such notions, according to the concept of differential algebra used.
The intention is to i ...
(ADE) by ; 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 1,000,000 permutations of length 300 are sampled uniformly at random from the class. The color of the point represents how many permutations have value at index . Higher resolution versions can be obtained oPermPal
External links
Thmaintained by Bridget Tenner, contains details of the enumeration of many other permutation classes with relatively few basis elements.
See also
*Baxter permutation In combinatorial mathematics, a Baxter permutation is a permutation \sigma \in S_n which satisfies the following generalized pattern avoidance property:
* There are no indices ''i'' < ''j'' < ''k'' such that ''σ''(''j'' + 1) < ''σ''(''i'') < ''σ ...
* Riffle shuffle permutation In the mathematics of permutations and the study of shuffling playing cards, a riffle shuffle permutation is one of the permutations of a set of n items that can be obtained by a single riffle shuffle, in which a sorted deck of n cards is cut into ...
References
*. *. *. *. *. *. *. *. *. *. *. *. *. *. *. *. *. *. *. *. *. *. *. * . *. *. *. *. * . *. *. *. *. *. *. *{{Citation , last1=West , first1=Julian , title=Generating trees and forbidden subsequences , year=1996 , journal=Discrete Mathematics
Discrete mathematics is the study of mathematical structures that can be considered "discrete" (in a way analogous to discrete variables, having a bijection with the set of natural numbers) rather than "continuous" (analogously to continuous f ...
, volume=157
, issue=1–3
, pages=363–374
, mr=1417303
, doi=10.1016/S0012-365X(96)83023-8, doi-access=free
.
Enumerative combinatorics
Permutation patterns