Kombinatorik der Mustervermeidung in Permutationen

Abstract

Diese Arbeit soll einen Überblick über die Kombinatorik der Mustervermeidung bei Permutationen liefern. Eine Permutation p der Länge n enthält die Permutation q der Länge k, wenn q ordungserhaltend auf eine Teilfolge der Länge k von p abgebildet werden kann. Ist dies nicht der Fall, so meidet p das Muster q. Von wesentlichem Interesse ist die Anzahl der Permutationen der Länge n, die gewisse Muster q meiden (diese Menge wird mit S_n(q) bezeichnet), sowie die Suche nach Wilf-äquivalenten Permutationen. Dafür betrachten wir unter anderem erzeugende Bäume, Young-Diagramme, Wachstumsdiagramme, sowie die strenge Wilf-Äquivalenz. Eine exponentielle obere Schranke von |S_n(q)| liefert die in 2003 von Adam Marcus und Gábor Tardos bewiesene Stanley-Wilf-Vermutung.

This thesis should provide an overview of the combinatorics of pattern avoidance in permutations. A permutation p of length n contains the permutation q of length k, if there exists an order preserving function, which maps q on a subsequence of p of the length k. If this is not the case, p avoids the pattern q. Of particular interest is the number of permutations of length n that avoid certain patterns q (denoted by S_n(q)), as well as the search for Wilf-equivalent permutations. For this we take a look at many objects and methods of combinatorics including generating trees, Young-diagrams, growth-diagrams and shape-wilf-equivalent permutations. An exponential upper bound of |S_n(q)| provides the Stanley-Wilf-conjecture, proven by Adam Marcus and Gábor Tardos in 2003.