<div class="csl-bib-body">
<div class="csl-entry">Dürnle, G. (2018). <i>Kombinatorik der Mustervermeidung in Permutationen</i> [Diploma Thesis, Technische Universität Wien]. reposiTUm. https://doi.org/10.34726/hss.2018.49983</div>
</div>
-
dc.identifier.uri
https://doi.org/10.34726/hss.2018.49983
-
dc.identifier.uri
http://hdl.handle.net/20.500.12708/3410
-
dc.description
Abweichender Titel nach Übersetzung der Verfasserin/des Verfassers
-
dc.description.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.
de
dc.description.abstract
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.
en
dc.language
Deutsch
-
dc.language.iso
de
-
dc.rights.uri
http://rightsstatements.org/vocab/InC/1.0/
-
dc.subject
Permutationen
de
dc.subject
Mustervermeidung
de
dc.subject
Stanley-Wilf-Vermutung
de
dc.subject
Wilf-Äquivalenz
de
dc.subject
erzeugende Bäume
de
dc.subject
P-rekursive Folgen
de
dc.subject
permutations
en
dc.subject
pattern avoidance
en
dc.subject
Stanley-Wilf conjecture
en
dc.subject
Wilf equivalence
en
dc.subject
generating trees
en
dc.subject
P-recursive sequences
en
dc.title
Kombinatorik der Mustervermeidung in Permutationen
de
dc.title.alternative
Combinatorics of pattern avoidance in permutations
en
dc.type
Thesis
en
dc.type
Hochschulschrift
de
dc.rights.license
In Copyright
en
dc.rights.license
Urheberrechtsschutz
de
dc.identifier.doi
10.34726/hss.2018.49983
-
dc.contributor.affiliation
TU Wien, Österreich
-
dc.rights.holder
Gerold Dürnle
-
dc.publisher.place
Wien
-
tuw.version
vor
-
tuw.thesisinformation
Technische Universität Wien
-
tuw.publication.orgunit
E104 - Institut für Diskrete Mathematik und Geometrie