Bibliographic Metadata

Title
Kombinatorik der Mustervermeidung in Permutationen / von Gerold Dürnle
Additional Titles
Combinatorics of pattern avoidance in permutations
AuthorDürnle, Gerold
CensorGittenberger, Bernhard
PublishedWien, 2018
Descriptioniv, 94 Seiten : Diagramme
Institutional NoteTechnische Universität Wien, Diplomarbeit, 2018
Annotation
Zusammenfassung in englischer Sprache
Annotation
Abweichender Titel nach Übersetzung der Verfasserin/des Verfassers
LanguageGerman
Document typeThesis (Diplom)
Keywords (DE)Permutationen / Mustervermeidung / Stanley-Wilf-Vermutung / Wilf-Äquivalenz / erzeugende Bäume / P-rekursive Folgen
Keywords (EN)permutations / pattern avoidance / Stanley-Wilf conjecture / Wilf equivalence / generating trees / P-recursive sequences
URNurn:nbn:at:at-ubtuw:1-112577 Persistent Identifier (URN)
Restriction-Information
 The work is publicly available
Files
Kombinatorik der Mustervermeidung in Permutationen [0.71 mb]
Links
Reference
Classification
Abstract (German)

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.

Abstract (English)

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.

Stats
The PDF-Document has been downloaded 12 times.