permutation pattern

A permutation pattern is simply a permutation viewed as its representation in one-line notation. Let $\pi ={\pi }_1{\pi }_2\mathrm{\dots }{\pi }_k$ be a permutation pattern on $k$ symbols. Then for any permutation $\sigma ={\sigma }_1{\sigma }_2\mathrm{\dots }{\sigma }_n\in {𝔖}_n$, we say that $\sigma$ contains $\pi$ if there is a (not necessarily contiguous) subword of $\sigma$ of length $k$ that is order-isomorphic to $\pi$. More formally, for any subset $J=\{j_1,\mathrm{\dots },j_k\}\subset \{1,\mathrm{\dots },n\}$ of cardinality $k$, write

$${\sigma }_J={\sigma }_{j_1}{\sigma }_{j_2}\mathrm{\dots }{\sigma }_{j_k}.$$

There is a isomorphism (http://planetmath.org/GroupHomomorphism) ${𝔖}_J\to {𝔖}_k$. We say that $\sigma$ contains $\pi$ if there is some $J\subset \{1,\mathrm{\dots },n\}$ of cardinality $k$ such that ${\sigma }_J\mapsto \pi$ under the isomorphism.

If a permutation $\sigma$ does not contain $\pi$, then we say that $\sigma$ avoids the pattern $\pi$.

For example, let $\pi =132$. Then the permutation $\sigma =1234$ avoids $\pi$, since $\sigma$ is strictly increasing but $\pi$ has a descent. On the other hand, $\tau =1423$ contains $\pi$ 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