If π and σ are two permutations represented in this way (these variable names are standard for permutations and are unrelated to the number pi), 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 σ.
The permutation 32415 on five elements contains 213 as a pattern in several different ways: 3··15, ··415, 32··5, 324··, and ·2·15 all form triples of entries with the same ordering as 213.
A case can be made that Percy MacMahon (1915) was the first to prove a result in the field with his study of "lattice permutations".
The study of permutation patterns began in earnest with Donald Knuth's consideration of stack-sorting in 1968.
In particular, Knuth's question asking how many permutation of n elements are obtainable with the use of a deque remains open.
[5] Shortly thereafter, Robert Tarjan (1972) investigated sorting by networks of stacks,[6] while Vaughan Pratt (1973) showed that the permutation π can be sorted by a deque if and only if for all k, π avoids 5,2,7,4,...,4k+1,4k−2,3,4k,1, and 5,2,7,4,...,4k+3,4k,1,4k+2,3, and every permutation that can be obtained from either of these by interchanging the last two elements or the 1 and the 2.
[8] In his paper, Pratt remarked that this permutation pattern order “seems to be the only partial order on permutation that arises in a simple and natural way” and concludes by noting that “from an abstract point of view”, the permutation pattern order “is even more interesting than the networks we were characterizing”.
As noted above, MacMahon and Knuth showed that |Avn(123)| = |Avn(231)| = Cn, the nth Catalan number.
(These two operations generate the Dihedral group D8 with a natural action on permutation matrices.)
Every class can be defined by the minimal permutations which do not lie inside it, its basis.
As the set of permutations under the containment order forms a poset it is natural to ask about its Möbius function, a goal first explicitly presented by Wilf (2002).
[17] The goal in such investigations is to find a formula for the Möbius function of an interval [σ, π] in the permutation pattern poset which is more efficient than the naïve recursive definition.
The first such result was established by Sagan & Vatter (2006), who gave a formula for the Möbius function of an interval of layered permutations.
[18] Later, Burstein et al. (2011) generalized this result to intervals of separable permutations.
There are several variants on the PPM problem, as surveyed by Bruner and Lackner.
[24] For example, if the match is required to consist of contiguous entries then the problem can be solved in polynomial time.
[25] A different natural variant is obtained when the pattern is restricted to a proper permutation class
Another variant is when both the pattern and text are restricted to a proper permutation class
and showed that the same bound holds for the class of skew-merged permutations.
-PPM problem can be solved in polynomial time for every fixed proper permutation class
This question was answered negatively by Jelínek and Kynčl who showed that
In his address to the SIAM meeting on Discrete Mathematics in 1992, Wilf defined the packing density of the permutation β of length k as An unpublished argument of Fred Galvin shows that the quantity inside this limit is nonincreasing for n ≥ k, and so the limit exists.
Walter Stromquist (unpublished) settled this case by showing that the packing density of 132 is 2√3 − 3, approximately 0.46410.
Presutti & Stromquist (2010) provided a lower bound on the packing density of 2413.
This lower bound, which can be expressed in terms of an integral, is approximately 0.10474, and conjectured to be the true packing density.
For example, a vincular pattern is a permutation containing dashes indicating which adjacent pairs of entries need not occur consecutively.
For example, the permutation 314265 has two copies of the dashed pattern 2−31−4, given by the entries 3426 and 3425.
These patterns were introduced by Babson & Steingrímsson (2000), who showed that almost all known Mahonian statistics could be expressed in terms of vincular permutations.
West (1993) introduced these types of patterns in his study of permutations which could be sorted by passing them twice through a stack.
Another example of barred patterns occurs in the work of Bousquet-Mélou & Butler (2007), who showed that the Schubert variety corresponding to π is locally factorial if and only if π avoids 1324 and 21354.