Title: Kombinatorik der Mustervermeidung in Permutationen
Other Titles: Combinatorics of pattern avoidance in permutations
Language: Deutsch
Authors: Dürnle, Gerold 
Qualification level: Diploma
Keywords: Permutationen; Mustervermeidung; Stanley-Wilf-Vermutung; Wilf-Äquivalenz; erzeugende Bäume; P-rekursive Folgen
permutations; pattern avoidance; Stanley-Wilf conjecture; Wilf equivalence; generating trees; P-recursive sequences
Advisor: Gittenberger, Bernhard 
Issue Date: 2018
Number of Pages: 94
Qualification level: Diploma
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.
URI: https://resolver.obvsg.at/urn:nbn:at:at-ubtuw:1-112577
http://hdl.handle.net/20.500.12708/3410
Library ID: AC15076029
Organisation: E104 - Institut für Diskrete Mathematik und Geometrie 
Publication Type: Thesis
Hochschulschrift
Appears in Collections:Thesis

Files in this item:

Show full item record

Page view(s)

1
checked on Mar 29, 2021

Download(s)

1
checked on Mar 29, 2021

Google ScholarTM

Check


Items in reposiTUm are protected by copyright, with all rights reserved, unless otherwise indicated.