Permutation pattern

Definition

Let $k \le n$ be positive integers. Write a permutation $\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 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 $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 gives an exponential bound on $\abs{\operatorname{Av}_n(\sigma)}$ for every $\sigma$ .

Reading path

To understand this page from the ground up, read these 4 pages in order. The foundations come first.

Show the path as a graph

Each page uses the pages above it. The colour of the bar on a box shows how strong the evidence is, and the box also gives it as text. The list has the same pages.

no evidence level

Permutation definition
Sequence definition
Subsequence definition
Permutation pattern definition

Tag	`DF69BF6841`
URI	`m2://DF69BF6841`
Kind	definition
Writing	W0 stub
MSC	05A05, 05A15
Defines	Permutation pattern
Uses	Permutation, Subsequence
Changed	2 November 2026

Permutation pattern

Definition

Remarks

Reading path

Further reading

What this page needs for W1

What links here