Permutation pattern

The permutation π written in the one-line notation is said to contain the permutation σ if there exists a subsequence of entries of π that has the same relative order as σ, and in this case σ is said to be a pattern of π. Otherwise, π is said to avoid the permutation σ.

Note that subsequence of π need not consist of consecutive entries. For example, permutation π = 391867452 (written in one-line notation) contains the pattern σ = 51342, as can be seen by consider the subsequence 91672. Such a subsequence is called a copy of σ.