Motif (permutations)

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 permutation to the digit sequence 123...; for instance the digit 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 digits of π has the same relative order as all of the digits of σ. For instance, permutation π contains the pattern 213 whenever π has three digits 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 digits with the same ordering as 213. 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 10 subsequences of three digits, but none of these 10 subsequences has the same ordering as 213. A case can be made that 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 must contain either the pattern or the pattern .