Direkt zum Inhalt

Lexikon der Mathematik: Catalan-Zahl

die Anzahl Cn aller Möglichkeiten, ein Produkt a1….anan+1 so zu klammern, daß eine sukzessive Auflösung möglich ist. Beispielsweise für a1a2a3a4 gibt es folgende fünf Fälle: (a1a2) ⋅ (a3a4), ((a1a2) ⋅ a3) ⋅ a4, (a1a2a3)) ⋅ a4, a1 ⋅ ((a2a3)a4) und a1 ⋅ (a2 ⋅ (a3a4)), sodaß C3 = 5.

Die ersten zehn Catalan-Zahlen sind 1, 2, 5, 14, 42, 132, 429, 1430, 4862 und 16796. Für n < 215 − 1 gibt es nur zwei Catalan-Zahlen, die Primzahlen sind: C2 = 2 und C3 = 5.

Andere Interpretationen der Catalan Zahlen sind:

  1. Die Anzahl der Aufteilungen eines (n + 2)-seitigen Vieleckes in n Dreiecke.
  2. Die Anzahl der trivalenten Wurzelbäume mit (n + 1) Ecken.
  3. Die Anzahl der Wege der Länge n in einem n × n

Raster, die unter der Hauptdiagonale liegen. Die Catalan-Zahlen können anhand der folgenden expliziten Formeln berechnet werden:

\begin{eqnarray}{C}_{n}=\frac{(2n\\ n)}{(n+1)n}=\frac{(2n)!}{(n+1){(n!)}^{2}}=\frac{(2n)!}{(n+1)!n!},\end{eqnarray}

wobei \((n\\ k)\) die Binomialkoeffizienten sind.

Die Catalan-Zahlen können auch mit der erzeugenden Funktion

\begin{eqnarray}\frac{1-\sqrt{1-4x}}{2x}=\displaystyle \sum _{n=0}^{\infty }{C}_{n}{x}^{n}\end{eqnarray}

definiert werden. Sie erfüllen die Rekursion

\begin{eqnarray}{C}_{n+1}=\frac{2(2n+1)}{n+2}{C}_{n}.\end{eqnarray}

Schreiben Sie uns!

Wenn Sie inhaltliche Anmerkungen zu diesem Artikel haben, können Sie die Redaktion per E-Mail informieren. Wir lesen Ihre Zuschrift, bitten jedoch um Verständnis, dass wir nicht jede beantworten können.

  • Die Autoren
- Prof. Dr. Guido Walz

Partnerinhalte

Bitte erlauben Sie Javascript, um die volle Funktionalität von Spektrum.de zu erhalten.