Mustervermeidung

mathematischer Begriff aus der Kombinatorik

Die Mustervermeidung (englisch pattern avoidance) ist ein mathematischer Begriff aus der Kombinatorik. Man spricht von Mustervermeidung, wenn eine Permutation nicht dasselbe Ordnungsmuster einer zweiten Permutation 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 die Folge von nicht als Teilfolge enthalten sein.

Definition

Bearbeiten

Mit   bezeichnen wir die symmetrische Gruppe.

Betrachte die Permutationen   und   wobei  . Man sagt   vermeidet   falls keine Teilfolge   der Länge   mit   existiert, so dass wenn   auch   gilt. Ansonsten sagt man das Muster von   ist in   enthalten.[1]

Beispiele

Bearbeiten
  • Die Permutation   vermeidet  , da sich das absteigende Muster   nicht finden lässt.
  • Die Permutation   enthält die Permutation  . In   gibt es die Teilfolge  , welche das Muster von   besitzt. Diese Teilfolge ist aber nicht die einzige Folge, die das Muster von   besitzt. Hingegen vermeidet   das absteigende Muster  .

Eigenschaften

Bearbeiten

Mit   bezeichnet man die Umkehrung (englisch reverse) einer Permutation   und mit   das Komplement, so dass  . Als Beispiel sei  , dann ist   und  .

Muster der Länge 3

Bearbeiten

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

 

Bezeichne mit   die Anzahl der  -Permutationen, die das Muster von   vermeiden. Wenn nun eine Permutation   das Muster von   vermeidet, dann vermeidet   die Umkehrung   und   vermeidet  , somit gilt

 

Es lässt sich auch   zeigen, somit werden alle Muster   der Länge   von derselben Anzahl von  -Permutationen vermieden, es gilt   wobei   die Catalan-Zahlen bezeichnen.[2]

Vermutung von Stanley-Wilf

Bearbeiten

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   eine Permutation, dann existiert eine Konstante  , so dass   gilt

 

Variante 2:

Sei   eine Permutation, dann existiert der Grenzwert

 

Literatur

Bearbeiten

Einzelnachweise

Bearbeiten
  1. Miklós Bóna: Combinatorics of Permutations. Hrsg.: Chapman and Hall/CRC. 2004, ISBN 978-0-367-22258-1, S. 129.
  2. Miklós Bóna: Combinatorics of Permutations. Hrsg.: Chapman and Hall/CRC. 2004, ISBN 978-0-367-22258-1, S. 130–133.