Permutation pattern

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  n (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 Av n (β) is used instead.) As noted above, MacMahon and Knuth showed that |Av n (123)| = |Av n (231)| = C n , the nth Catalan number. Thus these are isomorphic combinatorial classes. 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 for a survey. In general, if |Av n (β)| = |Av n (σ)| for all n, then β and σ are said to be Wilf-equivalent. Many Wilf-equivalences stem from the trivial fact that |Av n (β)| = |Av n (β −1 )| = |Av n (β rev )| for all n, where β −1 denotes the inverse of β and β rev denotes the reverse of β. (These two operations generate the Dihedral group D 8 with a natural action on permutation matrices.) However, there are also numerous examples of nontrivial Wilf-equivalences (such as that between 123 and 231): proved that the permutations 1342 and 2413 are Wilf-equivalent. proved that for any permutation β, the permutations 231 &oplus; β and 312 &oplus; β are Wilf-equivalent, where &oplus; denotes the direct sum operation. proved that for any permutation β and any positive integer m, the permutations 12...m &oplus; β and m...21 &oplus; β are Wilf-equivalent. From these two Wilf-equivalences and the inverse and reverse symmetries, it follows that there are three different sequences |Av n (β)| where β is of length four: In the late 1980s, Richard Stanley and Herbert Wilf conjectured that for every permutation β, there is some constant K such that |Av n (β)| n . This was known as the Stanley–Wilf conjecture until it was proved by Adam Marcus and Gábor Tardos. It is known that, asymptotically, at least 39.95% of all permutations π of length n satisfy μ(1, π)=0 (that is, the principal Möbius function is equal to zero), but for each n there exist permutations π such that μ(1, π) is an exponential function of n. ==Generalizations== The type of pattern defined above, in which entries do not need to occur consecutively, is called a classical (permutation) pattern. If the entries are required to be consecutive, then the pattern is called a consecutive pattern. There are several ways in which the notion of "pattern" has been generalized. 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. For a dashed pattern β and any permutation π, we write β(π) for the number of copies of β in π. Thus the number of inversions in π is 2−1(π), while the number of descents is 21(π). Going further, the number of valleys in π is 213(π) + 312(π), while the number of peaks is 231(π) + 132(π). These patterns were introduced by , who showed that almost all known Mahonian statistics could be expressed in terms of vincular permutations. For example, the Major index of π is equal to 1−32(π) + 2−31(π) + 3−21(π) + 21(π). Another generalization is that of a barred pattern, in which some of the entries are barred. For π to avoid the barred pattern β means that every set of entries of π which form a copy of the nonbarred entries of β can be extended to form a copy of all entries of β. introduced these types of patterns in his study of permutations which could be sorted by passing them twice through a stack. (Note that West's definition of sorting twice through a stack is not the same as sorting with two stacks in series.) Another example of barred patterns occurs in the work of , who showed that the Schubert variety corresponding to π is locally factorial if and only if π avoids 1324 and 21 3 54. ==External links== PermLab: software for permutation patterns, maintained by Michael Albert. Database of Permutation Pattern Avoidance, maintained by Bridget Tenner. PermPAL: The Permutation Pattern Avoidance Library, a database of algorithmically-derived theorems about permutation classes, maintained by Christian Bean, Émile Nadeau, Jay Pantone and Henning Ulfarsson.

Text derived from https://en.wikipedia.org/w/index.php?oldid=1353639132 under CC BY-SA 4.0; modifications have been made.

Names in other languages