---
tag: DF69BF6841
kind: definition
name: Permutation pattern
msc: [05A05, 05A15]
defines: 1H8Z1WMG23
uses: [0BQMWCNS8S, 0R8J3ZQMJS]
sources:
  - url: https://en.wikipedia.org/wiki/Permutation_pattern
---

## Definition

Let $k \le n$ be positive integers.
Write a [[permutation|0BQMWCNS8S]] $\pi$ of $\set{1, \ldots, n}$ in one-line notation $\pi(1) \pi(2) \cdots \pi(n)$, and let $\sigma$ be a permutation of $\set{1, \ldots, k}$.
The permutation $\pi$ *contains* $\sigma$ as a *pattern* if there are indices $i_1 < i_2 < \cdots < i_k$ such that, for all $a, b \in \set{1, \ldots, k}$,
$$\pi(i_a) < \pi(i_b) \iff \sigma(a) < \sigma(b).$$
Otherwise $\pi$ *avoids* $\sigma$.
The set of permutations of $\set{1, \ldots, n}$ that avoid $\sigma$ is written $\operatorname{Av}_n(\sigma)$.

## Remarks

Example: $\pi = 3\,1\,4\,2$ contains $\sigma = 312$.
Take the indices $1, 2, 4$, with values $3, 1, 2$; the first is the largest and the second is the smallest, as in $312$.

Non-example: $\pi = 3\,1\,4\,2$ avoids $123$.
Its increasing [[subsequences|0R8J3ZQMJS]] are $3\,4$, $1\,4$ and $1\,2$ and single entries, and none has length $3$.

For every $\sigma$ of length $3$, the number $\abs{\operatorname{Av}_n(\sigma)}$ is the [[Catalan number|0YWZJEABB2]] $C_n$.
Knuth showed that the permutations that can be sorted by a single stack are exactly those that avoid $231$.
The [[Stanley–Wilf conjecture|KWJS2QYJ1K]] gives an exponential bound on $\abs{\operatorname{Av}_n(\sigma)}$ for every $\sigma$.