Stefan Preyer

Verallgemeinerte Catalan-Zahlen und Primzerlegungen von balancierten Klammerausdrücken

Betreuer: Klaus Kriegel
Abschluss: Bachelor of Science (B.Sc.)
Abgabedatum: 07.02.2017

Kurzbeschreibung

In der Arbeit haben wir zwei Varianten zur Verallgemeinerung der aus der Kombinatorik bekannten Catalan-Zahlen diskutiert. Zum einen ging es um die von Manuel Wettstein in seinem Artikel „Trapezoidal Diagrams, Upward Triangulations, and Prime Catalan Numbers“ vorgeschlagene Variante, die Catalan-Zahlen als Anzahl balancierter Klammerausdrücke (BKA) zu definieren. Diese hat sich mathematisch als besonders fruchtbar herausgestellt. Das liegt vor allem daran, dass es möglich ist, für die d-dimensionalen Catalan-Zahlen eine geschlossene Formel anzugeben. Für einige Objektklassen haben wir gezeigt, dass sie sich in das Konzept der d-dimensionalen Catalan-Zahlen im Sinne von Wettstein einbetten lassen: bei den Standard-Young-Tableaus benötigten wir dazu noch die schwer zu beweisende Hook-Length-Formel als zusätzliches Hilfsmittel, bei den Gitterwegen und Dyck-Pfaden ergaben sich im d-dimensionalen natürliche Bijektionen.

Andere schon lange bekannte Interpretationen der Catalan-Zahlen passen jedoch nicht dazu. Die Catalan-Zahlen zählen die binären Bäume, jedoch weiß man, dass die Anzahl echter d-närer Bäume nicht den d-dimensionalen Catalan-Zahlen entspricht. Auch die Triangulation von konvexen Polygonen lässt sich nicht so auf höhere Dimensionen verallgemeinern, dass wir wieder die Catalan-Zahlen erhalten.

Wir haben trotzdem eine überraschende Erkenntnis über den Zusammenhang zwischen d-nären Bäumen und den primen BKA, die Wettstein eingeführt hat, gefunden. Nachdem wir nämlich eine Primzerlegung von BKA eingeführt haben und einfache BKA definiert haben, ergab sich die zentrale Erkenntnis, dass es eine Bijektion zwischen der Menge der echten d-nären Bäume und der Menge der einfachen BKA gibt. Außerdem haben wir Bijektionen zwischen zwei Mengen von geschlossenen Dyck-Pfaden und der Menge der primen BKA gefunden.