---
tag: 1H8Z1WMG23
kind: concept
name: Permutation pattern
msc: [05A05, 05A15]
sources:
  - url: https://en.wikipedia.org/wiki/Permutation_pattern
same_as:
  wikidata: Q7169371
  wikipedia: Permutation pattern
---

## Summary

A permutation pattern is a short [[permutation|05RWFKVTJ7]] that may occur inside a longer one, see the [[definition|DF69BF6841]].
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|KWJS2QYJ1K]], now a theorem, which bounds these counts by an exponential.

## Explanations

### L1 human

Write a permutation as a row of numbers, such as $3\,1\,4\,2$.
Pick some of the entries, keep their order, and look only at which is larger than which.
Picking $3, 1, 2$ gives the shape "high, low, middle", which is the pattern $312$.
The row $3\,1\,4\,2$ has no three entries that increase from left to right, so it avoids the pattern $123$.