Noncrossing Trennwand - Noncrossing partition

Es gibt 42 nicht kreuzende und 10 kreuzende Partitionen eines 5-Elemente-Sets

Die 14 nicht kreuzenden Partitionen eines 4-Elemente-Sets sind in einem Hasse-Diagramm angeordnet

In der kombinatorischen Mathematik hat das Thema der nicht kreuzenden Partitionen aufgrund seiner Anwendung auf die Theorie der freien Wahrscheinlichkeit (unter anderem) eine gewisse Bedeutung erlangt . Die Anzahl der nicht kreuzenden Partitionen einer Menge von n Elementen ist die n- te katalanische Zahl . Die Anzahl der Partitionen eines noncrossing n -Glied Satz mit k Blöcken wird in der gefundenen Narayanas Zahl Dreieck.

Definition

Eine Partition einer Menge S ist eine Menge nicht leerer, paarweise disjunkter Teilmengen von S , die als "Teile" oder "Blöcke" bezeichnet werden und deren Vereinigung alle aus S besteht . Betrachten Sie eine endliche Menge, die linear geordnet oder (für die Zwecke dieser Definition äquivalent) in einer zyklischen Reihenfolge wie die Eckpunkte eines regulären n- Gons angeordnet ist. Es geht keine Allgemeinheit verloren, wenn diese Menge als S = {1, ..., n } angenommen wird. Eine nicht kreuzende Partition von S ist eine Partition, in der sich keine zwei Blöcke "kreuzen", dh wenn a und b zu einem Block und x und y zu einem anderen gehören, sind sie nicht in der Reihenfolge axby angeordnet . Wenn man einen Bogen basierend auf a und b und einen anderen Bogen basierend auf x und y zeichnet, kreuzen sich die beiden Bögen, wenn die Reihenfolge axby ist, aber nicht, wenn es axyb oder abxy ist . In den letzten beiden Ordnungen ist die Partition {{ a , b }, { x , y }} nicht kreuzend.

Wenn wir die Eckpunkte eines regulären Gleichwertig, beschriften n -gon mit den Zahlen 1 bis n , die konvexen Hüllen von verschiedenen Blöcken der Trennwand sind disjunkt voneinander, das heißt, sie auch nicht „Kreuz“ sich. Die Menge aller nicht kreuzenden Partitionen von S wird bezeichnet . Es gibt einen offensichtlichen Ordnungsisomorphismus zwischen und für zwei endliche Mengen mit derselben Größe. Das heißt, hängt im Wesentlichen nur von der Größe von ab und wir bezeichnen durch die nicht kreuzenden Partitionen auf jedem Satz von Größe n . ${\ displaystyle {\ text {NC}} (S)}$${\ displaystyle {\ text {NC}} (S_ {1})}$${\ displaystyle {\ text {NC}} (S_ {2})}$${\ displaystyle S_ {1}, S_ {2}}$${\ displaystyle {\ text {NC}} (S)}$${\ displaystyle S}$${\ displaystyle {\ text {NC}} (n)}$

Gitterstruktur

Wie die Menge aller Partitionen der Menge {1, ..., n } ist die Menge aller nicht kreuzenden Partitionen ein Gitter, wenn sie teilweise geordnet wird, indem gesagt wird, dass eine feinere Partition "kleiner als" eine gröbere Partition ist. Obwohl es sich um eine Teilmenge des Gitters aller Partitionen handelt, handelt es sich nicht um ein Untergitter des Gitters aller Partitionen, da die Verknüpfungsoperationen nicht übereinstimmen. Mit anderen Worten, die feinste Partition, die gröber als beide nicht kreuzenden Partitionen ist, ist nicht immer die feinste nicht kreuzende Partition, die gröber als beide ist.

Im Gegensatz zum Gitter aller Partitionen der Menge ist das Gitter aller nicht kreuzenden Partitionen einer Menge selbst-dual, dh es ist ordnungsisomorph zu dem Gitter, das sich aus der Umkehrung der Teilreihenfolge ergibt ("Umdrehen"). . Dies kann gesehen werden, indem beobachtet wird, dass jede nicht kreuzende Partition ein Komplement aufweist. In der Tat ist jedes Intervall innerhalb dieses Gitters selbst dual.

Rolle in der Theorie der freien Wahrscheinlichkeit

Das Gitter nicht kreuzender Partitionen spielt bei der Definition freier Kumulanten in der Theorie der freien Wahrscheinlichkeit dieselbe Rolle wie das Gitter aller Partitionen bei der Definition gemeinsamer Kumulanten in der klassischen Wahrscheinlichkeitstheorie . Genauer gesagt sei ein nicht kommutativer Wahrscheinlichkeitsraum ( Terminologie siehe freie Wahrscheinlichkeit ), eine nicht kommutative Zufallsvariable mit freien Kumulanten . Dann ${\ displaystyle ({\ mathcal {A}}, \ phi)}$${\ displaystyle a \ in {\ mathcal {A}}}$${\ displaystyle (k_ {n}) _ {n \ in \ mathbb {N}}}$

${\ displaystyle \ phi (a ^ {n}) = \ sum _ {\ pi \ in {\ text {NC}} (n)} \ prod _ {j} k_ {j} ^ {N_ {j} (\ pi)}}$

Dabei bezeichnet die Anzahl der Längenblöcke in der nicht kreuzenden Partition . Das heißt, die Momente einer nicht kommutativen Zufallsvariablen können als Summe freier Kumulanten über der Summe nicht kreuzender Partitionen ausgedrückt werden. Dies ist das freie Analogon der Moment-Kumulativ-Formel in der klassischen Wahrscheinlichkeit. Siehe auch Wigner-Halbkreisverteilung . ${\ displaystyle N_ {j} (\ pi)}$${\ displaystyle j}$${\ displaystyle \ pi}$

Verweise

• Germain Kreweras, "Sur les partitions non croisées d'un cycle", Diskrete Mathematik , Band 1, Nummer 4, Seiten 333–350, 1972.
• Rodica Simion , "Noncrossing Partitions", Discrete Mathematics , Band 217, Nummern 1–3, Seiten 367–409, April 2000.
• Roland Speicher, "Freie Wahrscheinlichkeit und nicht kreuzende Partitionen" , Séminaire Lotharingien de Combinatoire , B39c (1997), 38 Seiten, 1997