Catalan-Zahl

Definition und Grundformeln

Die Catalan-Zahlen bilden eine Folge natürlicher Zahlen, die in vielen Abzählungsproblemen der Kombinatorik vorkommt. Sie spielen dort eine ähnlich wichtige Rolle wie Binomialkoeffizienten oder Fibonacci-Zahlen. Die Folge C₀, C₁, C₂, C₃, … beginnt mit

1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786, 208012, 742900, …

Für n ≥ 0 gilt

Cₙ = 1/(n+1) · (2n über n) = (2n)!/((n+1)!n!).

Dabei ist (2n über n) der mittlere Binomialkoeffizient. Eine gleichwertige Darstellung lautet

Cₙ = (2n über n) − (2n über n+1).

Diese Differenz zweier ganzer Binomialkoeffizienten zeigt unmittelbar, dass jede Catalan-Zahl ganzzahlig ist.

Berechnung und wichtige Eigenschaften

Aufeinanderfolgende Catalan-Zahlen lassen sich mit

Cₙ₊₁ = (4n+2)/(n+2) · Cₙ

berechnen. Besonders wichtig ist außerdem die von Johann Andreas von Segner 1758 gefundene Rekursion

Cₙ₊₁ = Σₖ₌₀ⁿ CₖCₙ₋ₖ.

Zum Beispiel gilt C₃ = C₀C₂ + C₁C₁ + C₂C₀ = 2 + 1 + 2 = 5. Die Rekursion entsteht häufig dadurch, dass ein gezähltes Objekt an einer bestimmten Stelle in zwei unabhängig wählbare Teilobjekte zerfällt.

Die erzeugende Funktion, also eine Potenzreihe, deren Koeffizienten die Catalan-Zahlen sind, lautet

Σₙ₌₀∞ Cₙxⁿ = (1−√(1−4x))/(2x) = 2/(1+√(1−4x)).

Insbesondere gilt Σₙ₌₀∞ Cₙ/4ⁿ = 2. Mit der Gammafunktion Γ kann man die Zahlen auch als

Cₙ = 4ⁿΓ(1/2+n)/(√π · Γ(2+n))

darstellen. Eine weitere Formel ist Eulers Produkt

Cₙ = ∏ₖ₌₁ⁿ (4k−2)/(k+1).

Die Catalan-Zahlen wachsen asymptotisch, also für sehr große n näherungsweise, nach

Cₙ ∼ 4ⁿ/((n+1)√(πn)).

Für die Teilbarkeit gelten mehrere besondere Aussagen: C₂ = 2 und C₃ = 5 sind die einzigen Catalan-Zahlen, die Primzahlen sind. Jede Primzahl zwischen n+1 und 2n teilt Cₙ genau einmal. Cₙ ist genau dann ungerade, wenn n+1 eine Potenz von 2 ist.

Weitere Rekursionen verbinden Catalan-Zahlen untereinander und mit den Motzkin-Zahlen Mₖ:

Cₙ₊₁ = Σₖ₌₀⌊n/2⌋ (n über 2k)2ⁿ⁻²ᵏCₖ,

Cₙ₊₁ = Σₖ₌₀ⁿ (n über k)Mₖ.

Auch bestimmte Reihen besitzen geschlossene Werte. So konvergiert die Summe der Kehrwerte zu

Σₙ₌₀∞ 1/Cₙ = 2 + 4√3π/27.

Daneben bestehen Reihenbeziehungen zu 1/π, 4/π und π/6. Für Primzahlen gelten außerdem Kongruenzen, darunter für jede Primzahl p > 3:

(pn+1)Cₚₙ ≡ (n+1)Cₙ mod p³.

Für Wolstenholme-Primzahlen gilt sie modulo p⁴, für p = 2 und p = 3 modulo p². Insbesondere ist Cₚᵏₙ ≡ (n+1)Cₙ mod p und Cₚᵏ ≡ 2 mod p für k > 0.

Abzählungsmodelle und typische Beispiele

Catalan-Zahlen zählen viele verschieden aussehende, aber strukturell gleichartige Objekte. Häufig beruhen diese Aufgaben auf Binärbäumen, also Bäumen, bei denen sich jeder innere Knoten in einen linken und einen rechten Teil verzweigt. Cₙ zählt unter anderem:

• Binärbäume mit n Knoten.

• Vollständige Klammerungen eines Ausdrucks mit n zweistelligen Verknüpfungen beziehungsweise n+1 Faktoren, deren Reihenfolge feststeht.

• Dyck-Pfade der Länge 2n: Wege, die bei Höhe 0 beginnen und enden, aus Aufwärts- und Abwärtsschritten bestehen und niemals unter die x-Achse fallen.

• Monotone Wege durch ein n×n-Quadratgitter von der unteren linken zur oberen rechten Ecke, die nur nach rechts oder oben führen und niemals oberhalb der Diagonale liegen.

• Kachelungen einer Stufenform der Breite und Höhe n mit n Rechtecken.

• mögliche Auszählungsverläufe einer Wahl, bei denen zwei Kandidaten A und B jeweils n Stimmen erhalten und A während der gesamten Auszählung nie hinter B liegt.

• Möglichkeiten, wie sich 2n Personen an einem runden Tisch paarweise über den Tisch die Hand geben können, ohne dass sich Arme überkreuzen.

• nicht überkreuzende Partitionen einer Menge mit n Elementen. Beispielsweise gibt es für n = 5 genau C₅ = 42 solche Partitionen, während die Gesamtzahl aller Partitionen B₅ = 52 beträgt; B₅ ist eine Bellsche Zahl.

Ein zentrales Beispiel sind Klammerungen. Für drei Verknüpfungen in XXX*X gibt es genau fünf Möglichkeiten:

((XX)X)X, (X(XX))X, (XX)(XX), X((XX)X), X(X(X*X)).

Somit ist C₃ = 5. Zusätzliche, inhaltlich überflüssige Klammern um einen schon geklammerten oder den gesamten Ausdruck werden nicht mitgezählt. Die Verknüpfung muss weder assoziativ noch kommutativ sein; deshalb ist die Klammerung etwa bei Subtraktionen oder bei einer Matrix-Kettenmultiplikation wichtig. Bei Letzterer kann eine günstige Klammerung den Rechenaufwand verringern.

Die Rekursion lässt sich an Binärbäumen erklären: Es gibt genau einen Binärbaum mit 0 Knoten. Hat der linke Teilbaum i und der rechte Teilbaum n−1−i Knoten, so besitzt der gesamte Baum n Knoten. Daher gilt C₀ = 1 und für n > 0

Cₙ = Σᵢ₌₀ⁿ⁻¹ CᵢCₙ₋₁₋ᵢ.

Auch die geometrische Ausgangsfrage liefert ein typisches Beispiel: Cₙ₋₂ ist die Anzahl der Möglichkeiten, ein konvexes n-Eck durch sich nicht kreuzende Diagonalen vollständig in Dreiecke zu zerlegen. Ein Fünfeck besitzt daher C₃ = 5 Triangulationen. Bei einer Wahl mit n = 2 erfüllen genau die Folgen ABAB und AABB die Bedingung, dass A nie zurückliegt; entsprechend ist C₂ = 2.

Historische Entwicklung

Als Erster fand der chinesische Mathematiker Minggatu Catalan-Zahlen bei seiner Arbeit über unendliche Reihen für trigonometrische Funktionen. Das Manuskript zirkulierte in den 1730er Jahren, wurde aber erst 1839 als Buch veröffentlicht.

Leonhard Euler beschrieb die Zahlen 1751 in einem Brief an Christian Goldbach, als er die Zahl der Triangulationen eines konvexen Vielecks untersuchte. Johann Andreas von Segner fand 1758 eine Rekursionsformel; Euler gab in der Zusammenfassung zu Segners Artikel deren Lösung an. Nikolaus Fuss löste 1795 eine allgemeinere Abzählungsaufgabe von Johann Friedrich Pfaff. Gabriel Lamé, Olinde Rodrigues, Jacques Binet und Eugène Catalan griffen die Fragestellung 1838 und 1839 erneut auf. Eugen Netto führte die Folge in seinem 1901 veröffentlichten Lehrbuch der Combinatorik auf den belgischen Mathematiker Eugène Charles Catalan zurück, nach dem sie heute benannt ist.