Mustervermeidung

Die Mustervermeidung (englisch pattern avoidance) ist ein mathematischer Begriff aus der Kombinatorik. Man spricht von Mustervermeidung, wenn eine Permutation $\pi$ nicht dasselbe Ordnungsmuster einer zweiten Permutation $\sigma$ besitzt, das heißt, würde man zwischen den Elementen der Permutationen ein $<$ oder $>$ schreiben, und diese Symbole als Folge interpretieren, so würde in $\pi$ die Folge von $\sigma$ nicht als Teilfolge enthalten sein.

Definition

Mit ${\mathfrak {S}}_{n}$ bezeichnen wir die symmetrische Gruppe.

Betrachte die Permutationen $\pi =(p_{1},\dots ,p_{n})\in {\mathfrak {S}}_{n}$ und $\sigma =(s_{1},\dots ,s_{k})\in {\mathfrak {S}}_{k}$ wobei $n\geq k$. Man sagt $\pi$ vermeidet $\sigma$ falls keine Teilfolge $(p_{i_{1}},\dots ,p_{i_{k}})\subseteq \pi$ der Länge $k$ mit $i_{1}<i_{2}<\cdots <i_{k}$ existiert, so dass wenn $p_{i_{a}}<p_{i_{b}}$ auch $s_{a}<s_{b}$ gilt. Ansonsten sagt man das Muster von $\sigma$ ist in $\pi$ enthalten.

Beispiele

• Die Permutation $\pi =2134$ vermeidet $\sigma =821$, da sich das absteigende Muster $8>2>1$ nicht finden lässt.
• Die Permutation $\pi =7381264$ enthält die Permutation $\omega =2314$. In $\pi$ gibt es die Teilfolge $7<8>2<6$, welche das Muster von $2<3>1<4$ besitzt. Diese Teilfolge ist aber nicht die einzige Folge, die das Muster von $\omega$ besitzt. Hingegen vermeidet $\pi$ das absteigende Muster $\sigma =4321$.

Eigenschaften

Mit $\pi ^{r}=(p_{n},\dots ,p_{1})$ bezeichnet man die Umkehrung (englisch reverse) einer Permutation $\pi =(p_{1},\dots ,p_{n})$ und mit $\pi ^{c}=(p_{1}^{c},\dots ,p_{n}^{c})$ das Komplement, so dass $p_{i}^{c}=n+1-p_{i}$. Als Beispiel sei $\pi =231$, dann ist $\pi ^{r}=132$ und $\pi ^{c}=213$.

Muster der Länge 3

Es gibt $6$ mögliche Muster für eine Permutation der Länge $3$

$123,132,213,231,312,321$

Bezeichne mit ${\mathfrak {S}}_{n}(132)$ die Anzahl der $n$-Permutationen, die das Muster von $\omega =132$ vermeiden. Wenn nun eine Permutation $\pi$ das Muster von $w$ vermeidet, dann vermeidet $\pi ^{r}$ die Umkehrung $\omega ^{r}=231$ und $\pi ^{c}$ vermeidet $\omega ^{c}=312$, somit gilt

${\mathfrak {S}}_{n}(132)={\mathfrak {S}}_{n}(231)={\mathfrak {S}}_{n}(312)={\mathfrak {S}}_{n}(213).$

Es lässt sich auch ${\mathfrak {S}}_{n}(123)={\mathfrak {S}}_{n}(132)$ zeigen, somit werden alle Muster $\omega$ der Länge $3$ von derselben Anzahl von $n$-Permutationen vermieden, es gilt ${\mathfrak {S}}_{n}(\omega )=C_{n}$ wobei $C_{n}$ die Catalan-Zahlen bezeichnen.

Vermutung von Stanley-Wilf

Die Vermutung von Stanley-Wilf wurde 1980 aufgestellt und 2004 von Adam W. Marcus und Gábor Tardos bewiesen. Es existieren zwei gleichwertige Varianten des Satzes:

Sei $\pi$ eine Permutation, dann existiert eine Konstante $c_{\pi }$, so dass $\forall n\in \mathbb {N}$ gilt

${\mathfrak {S}}_{n}(\pi )\leq c_{\pi }^{n}.$

Variante 2:

Sei $\pi$ eine Permutation, dann existiert der Grenzwert

$\lim \limits _{n\to \infty }{\sqrt[{n}]{{\mathfrak {S}}_{n}(\pi )}}.$

Literatur

• Miklós Bóna: Combinatorics of Permutations. Hrsg.: Chapman and Hall/CRC. 2004, ISBN 978-0-367-22258-1.