Nicht-kreuzende Partition

Nicht-kreuzende Partitionen wurden v​on Germain Kreweras[1] i​n der Kombinatorik eingeführt u​nd spielen seitdem i​n verschiedenen mathematischen Gebieten e​ine wichtige Rolle.[2] Insbesondere s​ind sie i​n der freien Wahrscheinlichkeitstheorie v​on 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

Eine Partition einer Menge ${\displaystyle S}$ ist eine Zerlegung von ${\displaystyle S}$ in paarweise disjunkte nicht-leere Teilmengen (welche man Blöcke der Partition nennt), deren Vereinigung ${\displaystyle S}$ ergibt. Falls die endliche Menge ${\displaystyle S}$ linear geordnet ist, dann kann man nicht-kreuzende Partitionen betrachten. Ohne Einschränkung können wir annehmen, dass ${\displaystyle S=\{1,\dots ,n\}}$ gilt. Eine nicht-kreuzende Partition von ${\displaystyle S}$ ist eine Partition, deren Blöcke sich nicht kreuzen; d. h., es gibt keine ${\displaystyle 1\leq a<p<b<q\leq n}$, so dass ${\displaystyle a}$ und ${\displaystyle b}$ im selben Block liegen, ${\displaystyle p}$ und ${\displaystyle q}$ im gleichen Block liegen, und diese beiden Blöcke verschieden sind. Anstatt die Punkte ${\displaystyle 1,\dots ,n}$ linear anzuordnen, kann man sie auch zyklisch angeordnet auf einem Kreis als die Eckpunkte eines regulären ${\displaystyle n}$-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 ${\displaystyle S}$ wird mit ${\displaystyle {\text{NC}}(S)}$ bezeichnet. Es gibt einen offensichtlichen Isomorphismus zwischen ${\displaystyle {\text{NC}}(S_{1})}$ und ${\displaystyle {\text{NC}}(S_{2})}$ für zwei endliche linear geordnete Mengen ${\displaystyle S_{1},S_{2}}$ der gleichen Größe. Das heißt, ${\displaystyle {\text{NC}}(S)}$ hängt im Wesentlichen nur von der Anzahl der Elemente in ${\displaystyle S}$ ab. und wir bezeichnen mit ${\displaystyle {\text{NC}}(n)}$ die nicht-kreuzenden Partitionen einer Menge mit ${\displaystyle n}$ Elementen. Die Anzahl der Elemente in ${\displaystyle NC(n)}$ wird durch die Catalan-Zahlen gezählt.

Verbandsstruktur

Genauso wie die Menge aller Partitionen von ${\displaystyle \{1,\dots ,n\}}$ 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 ${\displaystyle NC(n)}$ 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 ${\displaystyle ({\mathcal {A}},\varphi )}$ ein nicht-kommutativer Wahrscheinlichkeitsraum und ${\displaystyle a\in {\mathcal {A}}}$ eine nicht-kommutative Zufallsvariable mit freien Kumulanten ${\displaystyle (k_{n})_{n\in \mathbb {N} }}$. Dann gilt die freie Momenten-Kumulanten-Formel

${\displaystyle \varphi (a^{n})=\sum _{\pi \in {\text{NC}}(n)}\prod _{B\in \pi }k_{\vert B\vert }}$,

wobei ${\displaystyle \vert B\vert }$ die Anzahl der Elemente des Blockes ${\displaystyle B}$ bezeichnet.

Dies i​st das f​reie Gegenstück z​u 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).