Nicht-kreuzende Partition

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

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]

Definition

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

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

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

  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).

Auf dieser Seite verwendete Medien

Noncrossing partitions 4; Hasse.svg
Autor/Urheber:
Watchduck.svg Watchduck
You can name the author as "T. Piesk", "Tilman Piesk" or "Watchduck".
, Lizenz: CC BY 3.0
The 14 noncrossing partitions of a 4-element set ordered in a Hasse diagram
Noncrossing partitions 5.svg
Autor/Urheber:
Watchduck.svg Watchduck
You can name the author as "T. Piesk", "Tilman Piesk" or "Watchduck".
, Lizenz: CC BY 3.0

The C5 = 42 noncrossing partitions of a 5-element set with the other 10 partitions shown below There are Sloane'sA111275(5) = 10 different cyclic patterns (rows in this arrangement),

compare Noncrossing partition necklaces.svg