Catalan-Zahlen

Catalan-Zahlen

Studium
Cn=1n+1(2nn)=(2n)!(n+1)! n!C_n = \frac{1}{n+1}\binom{2n}{n} = \frac{(2n)!}{(n+1)!\,n!}

Voraussetzung: n∈N0n \in \mathbb{N}_0

CnC_n
n-te Catalan-Zahl
nn
Größenparameter, z.B. Anzahl der Klammerpaare
(2nn)\binom{2n}{n}
Binomialkoeffizient „2n über n“

Die Catalan-Zahlen zählen korrekte Klammerungen, Triangulierungen von Vielecken, Binärbäume und Gitterwege unter der Diagonale.

Erklärung

Die Catalan-Zahlen sind die Folge

1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, …(n=0,1,2,…)1,\ 1,\ 2,\ 5,\ 14,\ 42,\ 132,\ 429,\ 1430,\ 4862,\ \ldots \qquad (n = 0, 1, 2, \ldots)

Sie tauchen bei vielen Abzählproblemen auf, die auf den ersten Blick nichts miteinander zu tun haben. CnC_n ist jeweils die Anzahl der

  • korrekten Klammerungen aus nn öffnenden und nn schließenden Klammern,
  • Gitterwege von (0,0)(0, 0) nach (n,n)(n, n) mit Schritten nach rechts und nach oben, die nie über die Diagonale y=xy = x steigen (Dyck-Wege),
  • Triangulierungen eines konvexen (n+2)(n+2)-Ecks durch sich nicht kreuzende Diagonalen,
  • Binärbäume mit nn Knoten,
  • Möglichkeiten, ein Produkt aus n+1n + 1 Faktoren vollständig zu klammern.

Neben der geschlossenen Formel erfüllen sie die Rekursion

C0=1,Cn+1=∑k=0nCk Cn−kC_0 = 1, \qquad C_{n+1} = \sum_{k=0}^{n} C_k\, C_{n-k}

Sie entsteht, wenn man die erste öffnende Klammer und die zu ihr passende schließende betrachtet: Innen steht eine korrekte Klammerung mit kk Paaren, dahinter eine mit n−kn - k Paaren.

Herleitung

Über Gitterwege mit dem Spiegelungsprinzip: Von (0,0)(0, 0) nach (n,n)(n, n) gibt es insgesamt (2nn)\binom{2n}{n} Wege. Ein Weg, der die Diagonale überschreitet, berührt irgendwann zum ersten Mal die Gerade y=x+1y = x + 1. Spiegelt man das Stück davor an dieser Geraden, entsteht umkehrbar eindeutig ein Weg von (−1,1)(-1, 1) nach (n,n)(n, n), also mit n+1n + 1 Rechts- und n−1n - 1 Hochschritten. Davon gibt es (2nn+1)\binom{2n}{n+1}. Also

Cn=(2nn)−(2nn+1)=1n+1(2nn)C_n = \binom{2n}{n} - \binom{2n}{n+1} = \frac{1}{n+1}\binom{2n}{n}

Beispiele

Drei Klammerpaare: C3=14(63)=204=5C_3 = \frac{1}{4}\binom{6}{3} = \frac{20}{4} = 5. Die fünf Klammerungen sind

((())),(()()),(())(),()(()),()()()((())),\quad (()()),\quad (())(),\quad ()(()),\quad ()()()

Sechseck triangulieren: Ein Sechseck ist ein (n+2)(n+2)-Eck mit n=4n = 4. Es gibt C4=15(84)=705=14C_4 = \frac{1}{5}\binom{8}{4} = \frac{70}{5} = 14 Triangulierungen. Mit der Rekursion: C4=1⋅5+1⋅2+2⋅1+5⋅1=14C_4 = 1 \cdot 5 + 1 \cdot 2 + 2 \cdot 1 + 5 \cdot 1 = 14.

Gitterwege für n=3n = 3: Von den (63)=20\binom{6}{3} = 20 Wegen nach (3,3)(3, 3) überschreiten (64)=15\binom{6}{4} = 15 die Diagonale, es bleiben 20−15=520 - 15 = 5.

Größere Werte: C5=42C_5 = 42 und C10=111(2010)=16796C_{10} = \frac{1}{11}\binom{20}{10} = 16796.

Typische Fehler

  • Den Index verschieben. Ein mm-Eck hat Cm−2C_{m-2} Triangulierungen, nicht CmC_m: Das Sechseck gehört zu C4C_4.
  • Den Faktor 1n+1\frac{1}{n+1} vergessen. (2nn)\binom{2n}{n} zählt alle Gitterwege, auch die, die über die Diagonale steigen.
  • 1n\frac{1}{n} statt 1n+1\frac{1}{n+1} schreiben. Für n=3n = 3 ergäbe das 203\frac{20}{3}, keine ganze Zahl.

Verwandte Formeln