# 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 {\U0001d516}_{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) ${\U0001d516}_{J}\to {\U0001d516}_{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 |