Objekt-Metadaten
Differenzen in Permutationen : über den Zusammenhang von Permutationen, Polyominos und Motzkin-Pfaden

Autor :Astrid Reifegerste
Herkunft :OvGU Magdeburg, Fakultät für Mathematik
Datum :09.10.2002
 
Dokumente :
Dataobject from HALCoRe_document_00004306
 
Typ :Dissertation
Format :Text
Kurzfassung :Die Arbeit untersucht die Summen der positiven Differenzen zwischen Stellen und Bildern (dexc) bzw. aufeinanderfolgenden Bildern einer Permutation (ddes). Diese Statistiken sind natürliche Erweiterungen der klassischen Anzahl der Auf- (exc) bzw. Abstiege (des).

Permutationsstatistiken und insbesondere ihre Verteilungen sind in den letzten Jahren sehr intensiv studiert worden. Die Untersuchungen werden dabei sowohl durch Fragen der reinen Mathematik, speziell der Theorie der symmetrischen Funktionen, als auch durch Problemstellungen der angewandten Mathematik, insbesondere der Informationsübertragung und Signalverarbeitung, motiviert. Zudem besteht seitens der Informatik großes Interesse, da Permutationsstatistiken die Grundlage für Analysen von Sortieralgorithmen bilden.

Es werden zunächst einige fundamentale Eigenschaften von dexc und ddes, unter anderem ihre Gleichverteilung, bewiesen. Es zeigt sich, daß dexc in sehr engem Zusammenhang zur Anzahl der Inversionen, einer weiteren klassischen Permutationsstatistik, steht. Diese Beziehung spielt in der Arbeit eine zentrale Rolle; sie ermöglicht es, die Verteilung der Statistiken über der symmetrischen Gruppe von der Verteilung über einer kleinen Teilmenge abzuleiten. Die Elemente dieser Menge werden als bi-ansteigend (oder auch 321-frei) charakterisiert.

Zur Diskussion der Verteilung von dexc bzw. ddes auf den bi-ansteigenden Permutationen werden diese durch zwei wohlbekannte kombinatorische Objekte verschlüsselt. Zum einen werden Korrespondenzen zwischen Permutationen und Parallelogrammpolyominos, zum anderen zwischen Permutationen und 2-Motzkin-Pfaden entwickelt. Die Statistiken dexc und ddes (und auch die Klassiker exc und des) finden sich dabei als natürliche Polyomino- bzw. Pfadparameter wieder. Somit ist es möglich, die Bestimmung der Verteilung auf die Enumeration von Polyominos und Gitterpfaden zurückzuführen.

Nebenbei legen die vorgestellten Bijektionen Zusammenhänge zwischen klassischen Korrespondenzen zwischen diesen Objekten offen und liefern neue Interpretationen für die berühmten Catalan-Zahlen.
Darüber hinaus werden Anwendungen der Bijektionen vorgestellt, die von einem diagrammbasierten Ansatz zur Untersuchung verbotener Muster in Permutationen bis zur Enumeration von Schiefdiagrammen bezüglich ihres Ranges reichen.
Rechte :Dieser Text ist urheberrechtlich geschützt.
 
Erstellt am :24.07.2008 - 07:21:46
Letzte Änderung :22.04.2010 - 09:31:13
MyCoRe ID :HALCoRe_document_00004306
Statische URL :http://edoc.bibliothek.uni-halle.de/servlets/DocumentServlet?id=4306