# permutation pattern

A permutation pattern  is simply a permutation  viewed as its representation in one-line notation. Let $\pi=\pi_{1}\pi_{2}\dots\pi_{k}$ be a permutation pattern on $k$ symbols. Then for any permutation $\sigma=\sigma_{1}\sigma_{2}\dots\sigma_{n}\in\mathfrak{S}_{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},\dots,j_{k}\}\subset\{1,\dots,n\}$ of cardinality $k$, write

 $\sigma_{J}=\sigma_{j_{1}}\sigma_{j_{2}}\dots\sigma_{j_{k}}.$

There is a isomorphism         (http://planetmath.org/GroupHomomorphism) $\mathfrak{S}_{J}\to\mathfrak{S}_{k}$. We say that $\sigma$ contains $\pi$ if there is some $J\subset\{1,\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 PermutationPattern 2013-03-22 16:24:41 2013-03-22 16:24:41 mps (409) mps (409) 4 mps (409) Definition msc 05A05 msc 05A15 pattern avoidance