permutation pattern

A permutation patternMathworldPlanetmath is simply a permutationMathworldPlanetmath viewed as its representation in one-line notation. Let π=π1π2πk be a permutation pattern on k symbols. Then for any permutation σ=σ1σ2σn𝔖n, we say that σ contains π if there is a (not necessarily contiguous) subword of σ of length k that is order-isomorphic to π. More formally, for any subset J={j1,,jk}{1,,n} of cardinality k, write


There is a isomorphismMathworldPlanetmathPlanetmathPlanetmathPlanetmathPlanetmathPlanetmathPlanetmathPlanetmath ( 𝔖J𝔖k. We say that σ contains π if there is some J{1,,n} of cardinality k such that σJπ under the isomorphism.

If a permutation σ does not contain π, then we say that σ avoids the pattern π.

For example, let π=132. Then the permutation σ=1234 avoids π, since σ is strictly increasing but π has a descent. On the other hand, τ=1423 contains π twice, once as the subword 142 and once as the subword 143.

Knuth showed that a permutation is stack-sortable if and only if it avoids the permutation pattern 231.

Title permutation pattern
Canonical name PermutationPattern
Date of creation 2013-03-22 16:24:41
Last modified on 2013-03-22 16:24:41
Owner mps (409)
Last modified by mps (409)
Numerical id 4
Author mps (409)
Entry type Definition
Classification msc 05A05
Classification msc 05A15
Defines pattern avoidance