The area of pattern avoidance is a young and rapidly growing field of discrete mathematics. Its roots can be discerned both in computer science within the theory of sorting algorithms and in a far-reaching generalization of the concept of inversions in permutations.<br />The objects analysed within pattern avoidance are so-called "restricted permutations". Permutations are the objects at the heart of discrete mathematics and algebra that can either be seen as linear orderings or as bijective maps from a set onto itself. Restricted permutations are permutations with a special inherent structure, namely such a structure that does not allow for certain patterns to appear. A pattern is to be understood as a subsequence of a permutation in which the elements lie in a certain, pre-defined order to each other. The central problem of pattern avoidance can be formulated as follows: How many n-permutations are there that avoid a given pattern? For patterns of length three it is relatively easy to find an answer to this question. Surprisingly enough, the integer sequence obtained is the very well-known sequence of Catalan numbers. For longer patterns, this problem turns out to be a lot more complicated. Results achieved so far are presented. Further to this, a more general result that received a lot of attention, the so-called Stanley-Wilf-conjecture, is recorded here along with its detailed proof.<br />In this thesis our interest focusses on permutations on multisets, i.e.<br />sets in which elements may appear more than once. It is only a few years ago that one ventured into this natural extension of the field of pattern avoidance.<br />The two main articles within this young field dealing with enumeration questions for multiset-permutations avoiding (multiset)-patterns are presented.<br />Following this, we show that several methods used for ordinary permutations can successfully be extended to multiset-permutations. With the help of generating trees and recursions, accompanied by generating functions and the Kernel method, we close a gap in the study of 122- avoiding permutations. In all cases where in addition to 122 an ordinary pattern of length three is avoided, we manage to develop closed enumeration formulae. Again, well-known sequences emerge, e.g. (generalized) Catalan and Fibonacci numbers. In some special cases, we provide additional insight by constructing bijections to other objects enumerated by the same sequences.<br />An appendix to this thesis contains an excerpt of a series of riddles that we call "MOUNTAINOUS PATTERNS" and that hopefully give a playful insight into the fascinating topic of pattern avoidance.<br />
en
Die Mustervermeidung ist ein junges und schnell wachsendes Teilgebiet der diskreten Mathematik. Ihr Ursprung kann einerseits in den Computerwissenschaften, genauer gesagt in der Theorie der Sortieralgorithmen, andererseits in einer weitreichenden Verallgemeinerung des Konzepts der Inversion einer Permutation gefunden werden.<br />Zentrales Untersuchungsobjekt der Mustervermeidung sind sogenannte "restricted permutations" (=eingeschränkte Permutationen), wobei Permutationen jene elementaren Bausteine der diskreten Mathematik und Algebra sind, die sowohl als lineare Ordnungen als auch als Bijektionen von einer endlichen Menge auf sich selbst aufgefasst werden können.<br />Die Einschränkung besteht darin, dass nur Permutationen, die eine gewisse Struktur aufweisen, nämlich eine, die ein bestimmtes Muster (oder mehrere Muster) nicht erlaubt, zugelassen sind. Unter einem Muster verstehen wir dabei eine Teilfolge einer Permutation, in der die Elemente in einer fest vorgegebenen Ordnungsrelation zueinander stehen. Die Frage, die im Mittelpunkt der Mustervermeidung steht, ist jene nach der Anzahl von Permutationen der Länge n, welche ein vorgegebenes Muster vermeiden. Für Muster mit drei Elementen ist die Beantwortung dieser Frage einfach und man erhält überraschenderweise eine wohlbekannte Zahlenfolge als Antwort: die der Catalan-Zahlen. Für längere Muster stellt sich diese Fragestellung jedoch als viel komplizierter heraus. Bekannte Resultate sowie Abzählformeln werden vorgestellt und die stark beachtete Stanley-Wilf-Vermutung, die eine allgemeine Aussage über die Anzahl an eingeschränkten Permutationen trifft, wird zusammen mit ihrem Beweis anschaulich präsentiert.<br />Ausführlich beschäftigt sich diese Arbeit mit Permutationen auf Multimengen, also Mengen in denen Elemente öfter als ein Mal vorkommen dürfen. Dieses Gebiet wurde bisher weit weniger erforscht als jenes der eingeschränkten Muster auf gewöhnlichen Mengen. Es konnte hier gezeigt werden, dass sich viele der bei gewöhnlichen Permutationen verwendeten Methoden auch auf Multimengen-Permutationen übertragen lassen.<br />Mithilfe von erzeugenden Bäumen und Rekursionen, fallweise erzeugenden Funktionen und der Kernel Methode, ist es in dieser Arbeit gelungen die Untersuchung jener Permutationen, die das Muster 122 vermeiden zu vervollständigen. Für alle Fälle, in denen noch ein weiteres, gewöhnliches Muster der Länge drei vermieden wird, konnten geschlossene Abzählformeln bewiesen werden. Auch hier treten wieder bekannte Zahlenfolgen auf, etwa (verallgemeinerte) Catalan-Zahlen oder Fibonacci-Zahlen. Darüber hinaus war es in einigen speziellen Fällen möglich, Bijektionen zu anderen Objekten, die durch dieselben Folgen abgezählt werden, zu konstruieren.<br />In einem Anhang dieser Arbeit wird ein Auszug einer Serie von mathematischen Rätseln, die wir MOUNTAINOUS PATTERNS nennen, vorgestellt.<br />Dieser ermöglicht hoffentlich einen spielerischen Einblick in die faszinierende Welt der Mustervermeidung.<br />
