Nicht-kreuzende Partition

mathematische Kombinatorik

Nicht-kreuzende Partitionen wurden von Germain Kreweras[1] in der Kombinatorik eingeführt und spielen seitdem in verschiedenen mathematischen Gebieten eine wichtige Rolle.[2] Insbesondere sind sie in der freien Wahrscheinlichkeitstheorie von großer Bedeutung.[3]

Es gibt 42 nicht-kreuzende (oben) und 10 kreuzende (unten) Partitionen einer 5-elementigen Menge
Die partielle Ordnung auf den 14 nicht-kreuzenden Partitionen einer 4-elementigen Menge wird hier durch ein Hasse-Diagramm dargestellt. Das Kreweras-Komplement wird durch Spiegelung an der horizontalen Mittelachse erhalten

Definition

Bearbeiten

Eine Partition einer Menge   ist eine Zerlegung von   in paarweise disjunkte nicht-leere Teilmengen (welche man Blöcke der Partition nennt), deren Vereinigung   ergibt. Falls die endliche Menge   linear geordnet ist, dann kann man nicht-kreuzende Partitionen betrachten. Ohne Einschränkung können wir annehmen, dass   gilt. Eine nicht-kreuzende Partition von   ist eine Partition, deren Blöcke sich nicht kreuzen; d. h., es gibt keine  , so dass   und   im selben Block liegen,   und   im gleichen Block liegen, und diese beiden Blöcke verschieden sind. Anstatt die Punkte   linear anzuordnen, kann man sie auch zyklisch angeordnet auf einem Kreis als die Eckpunkte eines regulären  -Ecks betrachten. Dann kann man einen Block einer Partition mit der konvexen Hülle seiner Punkte identifizieren, und die Bedingung nicht-kreuzend bedeutet, dass die Blöcke sich in dieser graphischen Darstellung nicht schneiden.

Die Menge aller nicht-kreuzenden Partitionen von   wird mit   bezeichnet. Es gibt einen offensichtlichen Isomorphismus zwischen   und   für zwei endliche linear geordnete Mengen   der gleichen Größe. Das heißt,   hängt im Wesentlichen nur von der Anzahl der Elemente in   ab. und wir bezeichnen mit   die nicht-kreuzenden Partitionen einer Menge mit   Elementen. Die Anzahl der Elemente in   wird durch die Catalan-Zahlen gezählt.

Verbandsstruktur

Bearbeiten

Genauso wie die Menge aller Partitionen von   ist die Menge aller nicht-kreuzenden Partitionen ein Verband bezüglich der partiellen Ordnung, welche durch Verfeinerung der Blöcke gegeben wird. Allerdings ist der Verband der nicht-kreuzenden Partitionen kein Unterverband von allen Partitionen. Die partielle Ordnung ist für beide Verbände zwar die gleiche, das Maximum von zwei nicht-kreuzenden Partitionen kann aber in beiden Verbänden verschieden sein. (Das Minimum hingegen ist in beiden Verbänden gleich.)

Im Gegensatz zum Verband aller Partitionen ist der Verband der nicht-kreuzenden Partitionen selbstdual, d. h. es existiert eine bijektive Abbildung (das sogenannte Kreweras Komplement) von   auf sich selbst, welche die partielle Ordnung umdreht.

Bedeutung in der freien Wahrscheinlichkeitstheorie

Bearbeiten

Der Verband der nicht-kreuzenden Partitionen spielt bei der Definition der freien Kumulanten in der freien Wahrscheinlichkeitstheorie die gleiche Rolle wie der Verband aller Partitionen bei der Definition der üblichen Kumulanten in der klassischen Wahrscheinlichkeitstheorie. Sei   ein nicht-kommutativer Wahrscheinlichkeitsraum und   eine nicht-kommutative Zufallsvariable mit freien Kumulanten  . Dann gilt die freie Momenten-Kumulanten-Formel

 ,

wobei   die Anzahl der Elemente des Blockes   bezeichnet.

Dies ist das freie Gegenstück zu der klassischen Momenten-Kumulanten-Formel.

Einzelnachweise

Bearbeiten
  1. Germain Kreweras: Sur les partitions non croisées d'un cycle. Discrete Mathematics, volume 1, number 4, S. 333–350, 1972.
  2. Rodica Simion: Noncrossing partitions. Discrete Mathematics, volume 217, numbers 1–3, S. 367–409, April 2000.
  3. Roland Speicher: Free probability and noncrossing partitions. Séminaire Lotharingien de Combinatoire, B39c (1997).