Mustervermeidung

Die Mustervermeidung (Vorlage:EnS) 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 ${𝔖}_n$ bezeichnen wir die symmetrische Gruppe.

Betrachte die Permutationen $\pi =(p_1,\dots ,p_n)\in {𝔖}_n$ und $\sigma =(s_1,\dots ,s_k)\in {𝔖}_k$ wobei $n\ge 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 (Vorlage:EnS) 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 ${𝔖}_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

${𝔖}_n(132)={𝔖}_n(231)={𝔖}_n(312)={𝔖}_n(213).$

Es lässt sich auch ${𝔖}_n(123)={𝔖}_n(132)$ zeigen, somit werden alle Muster $\omega$ der Länge $3$ von derselben Anzahl von $n$-Permutationen vermieden, es gilt ${𝔖}_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 $\mathrm{\forall }n\in \mathbb{N}$ gilt

${𝔖}_n(\pi )\le c_{\pi }^n.$

Variante 2:

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

$\lim {\mathrm{\backslash limits}}_{n\to \mathrm{\infty }}\sqrt[n]{{𝔖}_n(\pi )}.$

Literatur

• Vorlage:Literatur