🔢 Catalan-Zahlen

Ein konvexes (n+2)-Eck kann durch Ziehen von n–1 kreuzungsfreien Diagonalen in Dreiecke zerlegt werden; die Anzahl der Möglichkeiten dafür ist Cₙ. Für ein Viereck (n = 2): zwei Triangulationen. Für ein Fünfeck (n = 3): fünf Triangulationen. Die Bijektion zu Klammerfolgen funktioniert, indem man eine Kante des Polygons als „Wurzel“ fixiert und feststellt, dass das Dreieck an dieser Kante das restliche Polygon in zwei kleinere Polygone aufteilt, was die Catalan-Rekursion Cₙ = Σᵢ₌₀ⁿ⁻¹ Cᵢ Cₙ₋₁₋ᵢ widerspiegelt. Triangulationen treten in der computergestützten Geometrie (optimale Polygon-Triangulation, Delaunay-Triangulation), bei numerischen Methoden (Finite-Elemente-Vernetzung) und im Compilerbau (Syntaxbäume) auf.

Ein kreuzungsfreies Sehnendiagramm besteht aus 2n Punkten auf einem Kreis, die durch n einander nicht schneidende Sehnen verbunden sind. Die C₃ = 5 Möglichkeiten, 6 Punkte mit 3 kreuzungsfreien Sehnen zu verbinden, sind genau die fünf Catalan-Objekte für n = 3. Diese Diagramme treten bei der Vorhersage von RNA-Sekundärstrukturen auf (Basenpaare sind kreuzungsfreie Sehnen auf der Sequenz), in der Knotentheorie (Temperley–Lieb-Algebren) und in der freien Wahrscheinlichkeitstheorie (kreuzungsfreie Partitionen definieren die freien Kumulanten von Wahrscheinlichkeitsverteilungen). Die Anzahl der kreuzungsfreien Partitionen von {1, …, n} ist ebenfalls Cₙ.

Die Catalan-Zahlen erfüllen die Rekursion C₀ = 1 und Cₙ₊₁ = Σᵢ₌₀ⁿ Cᵢ Cₙ₋ᵢ. Diese Formel spiegelt die „Teilung an der Wurzel“-Struktur wider, die allen fünf bijektiven Familien gemeinsam ist: Bei einer Klammerfolge wird die Wurzel „(“ an einer bestimmten Position geschlossen, wodurch die Folge in zwei unabhängige, ausgeglichene Teilfolgen der Längen 2i und 2(n–i) aufgeteilt wird. Die Summierung über alle Teilungspositionen ergibt die Rekursion. Die erzeugende Funktion C(x) = Σ Cₙ xⁿ erfüllt x C(x)² – C(x) + 1 = 0, mit der Lösung C(x) = (1 – √(1 – 4x)) / (2x).

Der vereinheitlichende Grund ist, dass alle Catalan-Familien dieselbe rekursive Struktur teilen: Ein Objekt der Größe n kann eindeutig konstruiert werden, indem man eine „Wurzel“ wählt, die die verbleibenden Daten in zwei unabhängige Teilobjekte der Größen i und n–1–i (oder ähnlich) aufteilt, summiert über alle Teilungen. Dies ist genau die Catalan-Rekursion. Bijektionen zwischen diesen Familien sind oft elegant: Ein „(“ in einer Klammerfolge wird zu einer Links-Kind-Kante in einem Binärbaum und zu einem Aufwärtsschritt in einem Dyck-Pfad, sodass die kombinatorischen Daten buchstäblich dasselbe Objekt in drei verschiedenen Kostümen sind.

Catalan-Zahlen wachsen exponentiell: nach der Stirling-Näherung gilt Cₙ ~ 4ⁿ / (n^(3/2) √π). Das Verhältnis Cₙ₊₁/Cₙ = 2(2n+1)/(n+2) konvergiert gegen 4, sodass jede aufeinanderfolgende Catalan-Zahl etwa das Vierfache der vorherigen beträgt. C₁₀ = 16.796; C₂₀ ≈ 6,56 × 10¹⁰; C₅₀ ≈ 1,37 × 10²⁸. Für n = 8 (das Maximum in dieser Simulation) ist C₈ = 1.430 — genug, um alle Objekte einzeln zu zeichnen. Ab n ≈ 10 wird es unpraktisch, sie alle aufzuzählen, und Zufallsstichproben müssen verwendet werden.

Ein vollständiger Binärbaum ist ein gewurzelter Baum, in dem jeder innere Knoten genau zwei Kinder hat (nie eins). Die Anzahl der vollständigen Binärbäume mit n+1 Blättern ist Cₙ. Für n = 3: C₃ = 5 Bäume mit 4 Blättern. Die Bijektion zu Klammerfolgen ordnet jedem Blatt „)“ und jedem inneren Knoten „(“ zu, wobei der Baum von links nach rechts in Präorder gelesen wird. Vollständige Binärbäume sind die Struktur des Ausdrucks-Parsens, der Huffman-Codierung und des Stern–Brocot-Baums für Brüche. Sie zählen auch die Anzahl der Möglichkeiten, ein Produkt aus n+1 Faktoren vollständig zu klammern — Eulers ursprüngliche Formulierung des Problems (1751).

Euler zählte 1751 Polygon-Triangulationen und fand die Folge 1, 2, 5, 14, 42, …, hatte aber keine geschlossene Formel. Segner fand 1758 die Rekursion. Der belgische Mathematiker Eugène Charles Catalan gab 1838 die geschlossene Formel Cₙ = (2n)!/((n+1)!n!) an, und die Folge trägt heute seinen Namen. Die Folge war jedoch bereits früher vom chinesischen Mathematiker Ming Antu um 1730 im Zusammenhang mit trigonometrischen Entwicklungsformeln entdeckt worden. Die Geschichte ihrer gleichzeitigen, unabhängigen Entdeckungen ist ein anschauliches Beispiel für mathematische Universalität.

Catalan-Zahlen treten in der Informatik auf (Anzahl stapel-sortierbarer Permutationen, Anzahl verschiedener binärer Suchbäume mit n Schlüsseln, Anzahl monotoner Boolescher Funktionen mit 2 Variablen), in der Bioinformatik (RNA-Sekundärstrukturen, gezählt durch ihre kreuzungsfreie Klammerstruktur), in der Physik (kreuzungsfreie Feynman-Diagramme in der planaren Quantenfeldtheorie, Momente des Wigner-Halbkreisgesetzes in der Zufallsmatrizentheorie) und in der Linguistik (Anzahl der Parse-Bäume für eine mehrdeutige kontextfreie Grammatik mit einer bestimmten Regelstruktur). Stanleys „Catalan Numbers“ (2015) listet 214 verschiedene kombinatorische Interpretationen auf.