Catalan-Zahl

Die Catalan-Zahlen zählen beispielsweise die nicht überkreuzenden Partitionen einer Menge mit n Elementen, hier {\displaystyle C_{5}=42} (oben), wobei sämtliche Partitionen von den Bellschen Zahlen angegeben werden, hier {\displaystyle B_{5}=52}

Die Catalan-Zahlen oder catalanschen Zahlen bilden eine Folge natürlicher Zahlen, die in vielen Problemen der Kombinatorik auftritt und eine ähnlich wichtige Rolle wie die Binomialkoeffizienten oder die Fibonacci-Zahlen spielt. Sie sind nach dem belgischen Mathematiker Eugène Charles Catalan benannt.

Die Folge der Catalan-Zahlen {\displaystyle C_{0},C_{1},C_{2},C_{3},\dotsc } beginnt mit

1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786, 208012, 742900, … (Folge A000108 in OEIS)

Die Catalan-Zahlen sind für n \ge 0 gegeben durch

{\displaystyle C_{n}={\frac {1}{n+1}}{\binom {2n}{n}}={\frac {(2n)!}{(n+1)!\,n!}},}

wobei \tbinom{2n}{n} der mittlere Binomialkoeffizient ist. Mit \tbinom{2n}{n+1} = \tfrac{n}{n+1} \tbinom{2n}{n} erhält man, dass die Formel äquivalent zu

C_n = \binom{2n}{n} - \binom{2n}{n+1}

ist und somit tatsächlich nur ganze Zahlen liefert.

Historisches

Als Erster fand der Chinese Minggatu Catalan-Zahlen in seiner Arbeit zu unendlichen Reihen für trigonometrische Funktionen (1730er Jahre als Manuskript zirkulierend, aber erst 1839 als Buch veröffentlicht).

Die Zahlen dieser Folge wurden bereits 1751 von Leonhard Euler in einem Brief an Christian Goldbach beschrieben. Johann Andreas von Segner fand 1758 eine Rekursionsformel, zu der Euler in der Zusammenfassung zu Segners Artikel die Lösung angab.> Eine von Johann Friedrich Pfaff gestellte allgemeinere Abzählungsaufgabe löste 1795 Nikolaus Fuss. In den Jahren 1838 und 1839 griffen Gabriel Lamé, Olinde Rodrigues, Jacques Binet und Eugène Catalan die Fragestellung erneut auf. Eugen Netto führte in seinem 1901 veröffentlichten Lehrbuch der Combinatorik die Zahlen auf Catalan zurück.

Eigenschaften

Euler suchte die Anzahl der Möglichkeiten, ein konvexes n-Eck durch Diagonalen in Dreiecke zu zerteilen (Triangulation). Diese Anzahl ist C_{n-2}. Zum Beispiel gibt es für ein Fünfeck fünf mögliche Triangulationen:

Für ein Fünfeck gibt es fünf mögliche Triangulationen

Euler gab in seinem Brief an Goldbach 1751 (siehe Historisches) die explizite Formel

{\displaystyle C_{n}={\frac {2\cdot 6\cdot 10\dotsb (4n-2)}{2\cdot 3\cdot 4\dotsb (n+1)}}=\prod _{k=1}^{n}{\frac {4k-2}{k+1}}} (*)  

und die Formel

\sum_{n=0}^\infty C_n x^n = \frac{1 - \sqrt{1 - 4 x}}{2 x} = \frac{2}{1 + \sqrt{1 - 4 x}}

für die erzeugende Funktion an, insbesondere

\sum_{n=0}^\infty \frac{C_n}{4^n} = 2

auch als Beschreibung des Wachstumsverhaltens.

Mit der Gammafunktion \Gamma gilt:

{\displaystyle C_{n}={\frac {4^{n}\Gamma {\left({\tfrac {1}{2}}+n\right)}}{{\sqrt {\pi }}\,\Gamma {\left(2+n\right)}}}}

Direkt aus der Formel (*) folgt

{\displaystyle C_{n+1}={\frac {4n+2}{n+2}}\,C_{n}.}

Es gilt außerdem die Rekursionsformel (Segner 1758)

{\displaystyle C_{n+1}=\sum _{k=0}^{n}C_{k}\,C_{n-k},}

zum Beispiel ist {\displaystyle C_{3}=C_{0}\,C_{2}+C_{1}\,C_{1}+C_{2}\,C_{0}}.

Eine weitere Rekursionsformel ist

{\displaystyle C_{n+1}=\sum _{k=0}^{\lfloor n/2\rfloor }{\binom {n}{2k}}2^{n-2k}\,C_{k}}

sowie mit den Motzkin-Zahlen M (Folge A001006 in OEIS)

{\displaystyle C_{n+1}=\sum _{k=0}^{n}{\binom {n}{k}}\,M_{k}.}

Da alle Primfaktoren von \textstyle C_n = 2^n\,\frac{1 \cdot 3 \cdot 5 \cdots (2n-1)}{2 \cdot 3 \cdot 4 \cdots (n+1)}, siehe Formel (*), kleiner als 2n sind und C_n > 2 n für n > 3 gilt, sind C_2 = 2 und C_3 = 5 als einzige Catalan-Zahlen auch Primzahlen. Die Formel zeigt auch, dass C_{n} durch jede Primzahl zwischen n+1 und 2n genau einmal teilbar ist und genau dann ungerade ist, wenn n+1 eine Potenz von 2 ist.

Aus dem Satz von Wolstenholme folgt die Kongruenz

{\displaystyle (p\,n+1)\,C_{p\,n}\equiv (n+1)\,C_{n}{\pmod {p^{3}}}}

für jede Primzahl p>3, für Wolstenholme-Primzahlen gilt die Kongruenz {\displaystyle {\pmod {p^{4}}}}, für die Primzahlen 2 und 3 gilt sie {\displaystyle {\pmod {p^{2}}}}.

Insbesondere ist {\displaystyle C_{p^{k}n}\equiv (n+1)\,C_{n}{\pmod {p}}} und {\displaystyle C_{p^{k}}\equiv 2{\pmod {p}}} für jede Primzahl p und ganze Zahl k>0.

Durch Einsetzen der Stirling-Formel erhält man für das asymptotische Verhalten der Catalan-Zahlen

{\displaystyle C_{n}\sim {\frac {4^{n}}{(n+1){\sqrt {\pi n}}}}.}

Die Summe der Kehrwerte konvergiert:

{\displaystyle \sum _{n=0}^{\infty }{\frac {1}{C_{n}}}=2+{\frac {4{\sqrt {3}}\pi }{27}}}

Zudem gilt (Folge A013709 in OEIS 2016):

{\displaystyle \sum _{n=0}^{\infty }\left({\frac {C_{n}}{2^{2n+1}}}\right)^{2}(n+1)={\frac {1}{\pi }}} sowie
{\displaystyle \sum _{n=0}^{\infty }\left({\frac {C_{n}}{2^{2n+1}}}\right)^{2}(4n+3)=1}
{\displaystyle \sum _{n=0}^{\infty }\left({\frac {C_{n}}{2^{2n}}}\right)^{2}(n+1)={\frac {4}{\pi }}=\sum _{n=-1}^{\infty }\left({\frac {C_{n}}{2^{2n+1}}}\right)^{2}} (Wallis-Lambert-Reihe) mit {\displaystyle C_{-1}=-{\frac {1}{2}}}

Über die Cauchy-Produktformel mit dem Basler Problem ergibt sich daraus (Folge A281070 in OEIS 2017):

{\displaystyle \sum _{n=0}^{\infty }\sum _{k=0}^{n}\left({\frac {C_{k}}{2^{2k+1}}}\right)^{2}{\frac {k+1}{(n-k+1)^{2}}}={\frac {\pi }{6}}}

Interpretationen und Zusammenhänge

Die Catalan-Zahlen treten bei zahlreichen Abzählungsaufgaben auf, die graphentheoretisch Abzählungen von Bäumen sind. So ist C_{n} die Anzahl der

Zum Beispiel muss man für n=3 eine Zeichenfolge wie {\displaystyle X*X*X*X} in Klammern setzen, was auf 5 verschiedene Arten möglich ist:
{\displaystyle ((X*X)*X)*X\qquad (X*(X*X))*X\qquad (X*X)*(X*X)\qquad X*((X*X)*X)\qquad X*(X*(X*X))}
Ein explizites Beispiel für die Subtraktion ist
{\displaystyle ((10-6)-3)-1\qquad (10-(6-3))-1\qquad (10-6)-(3-1)\qquad 10-((6-3)-1)\qquad 10-(6-(3-1))}
Daher ist C_3 = 5. Das Hinzufügen redundanter Klammern um einen bereits in Klammern gesetzten Ausdruck oder um den vollständigen Ausdruck herum ist nicht zulässig. Es gibt einen Binärbaum mit 0 Knoten und jeder andere Binärbaum ist durch die Kombination aus seinem linken und seinem rechten Teilbaum gekennzeichnet. Wenn diese Teilbäume i bzw. j Knoten haben, hat der gesamte Baum {\displaystyle i+j+1} Knoten. Daher hat die Anzahl C_{n} von Binärbäumen mit n Knoten die folgende rekursive Beschreibung {\displaystyle C_{0}=1} und {\displaystyle \textstyle C_{n}=\sum _{i=0}^{n-1}C_{i}\cdot C_{n-1-i}} für jede positive ganze Zahl n. Daraus folgt, dass C_{n} die Catalan-Zahl mit Index n ist. Diese ist beispielsweise ein Maß für die Anzahl der möglichen Berechnungsreihenfolgen bei der nichtkommutativen Matrix-Kettenmultiplikation, wo durch geschickt optimierte Klammerung der Rechenaufwand minimiert werden kann.
Fünf Irrfahrten der Länge 6
Catalan number 4x4 grid example.svg
Catalan stairsteps 4.svg
Trenner
Basierend auf einem Artikel in: Wikipedia.de
Seitenende
Seite zurück
© biancahoegel.de
Datum der letzten Änderung: Jena, den: 19.10. 2023