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.