Permutation pattern

Summary

A permutation pattern is a short permutation that may occur inside a longer one, see the definition. A permutation contains a pattern if some of its entries appear in the same relative order as the pattern, and avoids it otherwise. The study of pattern avoidance counts the permutations that avoid given patterns. Its central result is the Stanley–Wilf conjecture, now a theorem, which bounds these counts by an exponential.