In combinatorial mathematics and theoretical computer science, a (classical) permutation pattern is a sub-permutation of a longer permutation. Any permutation may be written in one-line notation as a sequence of entries representing the result of applying the permutation to the sequence 123...; for instance the sequence 213 represents the permutation on three elements that swaps elements 1 and 2. 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 σ. For instance, permutation π contains the pattern 213 whenever π has three entries x, y, and z that appear within π in the order x...y...z but whose values are ordered as y < x < z, the same as the ordering of the values in the permutation 213. 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. Note that the entries do not need to be consecutive. Each of the subsequences 315, 415, 325, 324, and 215 is called a copy, instance, or occurrence of the pattern. The fact that π contains σ is written more concisely as σ ≤ π. If a permutation π does not contain a pattern σ, then π is said to avoid σ. The permutation 51342 avoids 213; it has ten subsequences of three entries, but none of these ten subsequences has the same ordering as 213. An international conference dedicated to permutation patterns and related topics has been held annually since 2003, called Permutation Patterns.
Early results 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". In particular MacMahon shows that the permutations which can be divided into two decreasing subsequences (i.e., the 123-avoiding permutations) are counted by the Catalan numbers. Another early landmark result in the field is the Erdős–Szekeres theorem; in permutation pattern language, the theorem states that for any positive integers a and b every permutation of length at least ( a − 1 ) ( b − 1 ) + 1 {\displaystyle (a-1)(b-1)+1} must contain either the pattern 1 , 2 , 3 , … , a {\displaystyle 1,2,3,\dots ,a} or the pattern b , b − 1 , … , 2 , 1 {\displaystyle b,b-1,\dots ,2,1} .
Computer science origins The study of permutation patterns began in earnest with Donald Knuth's consideration of stack-sorting in 1968. Knuth showed that the permutation π can be sorted by a stack if and only if π avoids 231, and that the stack-sortable permutations are enumerated by the Catalan numbers. Knuth also raised questions about sorting with deques. In particular, Knuth's question asking how many permutation of n elements are obtainable with the use of a deque remains open. Shortly thereafter, Robert Tarjan (1972) investigated sorting by networks of stacks, 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. Because this collection of permutations is infinite (in fact, it is the first published example of an infinite antichain of permutations), it is not immediately clear how long it takes to decide if a permutation can be sorted by a deque. Rosenstiehl & Tarjan (1984) later presented a linear (in the length of π) time algorithm which determines if π can be sorted by a deque. 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”.
Enumerative origins
A prominent goal in the study of permutation patterns is in the enumeration of permutations avoiding a fixed (and typically short) permutation or set of permutations. Let Avn(B) denote the set of permutations of length n which avoid all of the permutations in the set B. (In the case B is a singleton, say {β}, the abbreviation Avn(β) is used instead.) As noted above, MacMahon and Knuth showed that |Avn(123)| = |Avn(231)| = Cn, the nth Catalan number. Thus these are isomorphic combinatorial classes. Simion & Schmidt (1985) was the first paper to focus solely on enumeration. Among other results, Simion and Schmidt counted even and odd permutations avoiding a pattern of length three, counted permutations avoiding two patterns of length three, and gave the first bijective proof that 123- and 231-avoiding permutations are equinumerous. Since their paper, many other bijections have been given, see Claesson & Kitaev (2008) for a survey. In general, if |Avn(β)| = |Avn(σ)| for all n, then β and σ are said to be Wilf-equivalent. Many Wilf-equivalences stem from the trivial fact that |Avn(β)| = |Avn(β−1)| = |Avn(βrev)| for all n, where β−1 denotes the inverse of β and βrev denotes the reverse of β. (These two operations generate the Dihedral group D8 with a natural action on permutation matrices.) However, there are also numerous examples of nontrivial Wilf-equivalences (such as that between 123 and 231):
Stankova (1994) proved that the permutations 1342 and 2413 are Wilf-equivalent. Stankova & West (2002) proved that for any permutation β, the permutations 231 ⊕ β and 312 ⊕ β are Wilf-equivalent, where ⊕ denotes the direct sum operation. Backelin, West & Xin (2007) proved that for any permutation β and any positive integer m, the permutations 12...m ⊕ β and m...21 ⊕ β are Wilf-equivalent. From these two Wilf-equivalences and the inverse and reverse symmetries, it follows that there are three different sequences |Avn(β)| where β is of length four:
… excerpt ends here. Continue reading the full article.
