Catalan-Zahl

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.

Eugène Charles Catalan

Die Folge der Catalan-Zahlen C₀, C₁, C₂, C₃, … 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\geq 0$ gegeben durch

$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

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 Fuß. 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:

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

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

und die Formel

$\sum _{n=0}^{\infty }C_{n}x^{n}={\frac {1-{\sqrt {1-4x}}}{2x}}={\frac {2}{1+{\sqrt {1-4x}}}}$

für die erzeugende Funktion an, insbesondere

$\sum _{n=0}^{\infty }{\frac {C_{n}}{4^{n}}}=2$

auch als Beschreibung des Wachstumsverhaltens.

Direkt aus der Formel (*) folgt

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

Es gilt außerdem die Rekursionsformel (Segner 1758)

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

zum Beispiel ist $C_{3}=C_{0}{\text{ }}C_{2}+C_{1}{\text{ }}C_{1}+C_{2}{\text{ }}C_{0}$.

Eine weitere Rekursionsformel ist

$C_{n+1}=\sum _{k=0}^{\lfloor n/2\rfloor }{\binom {n}{2k}}2^{n-2k}\,C_{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}>2n$ für $n>3$, 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, wenn $n=2^{k}-1$ für eine ganze Zahl $k$.

Aus dem Satz von Wolstenholme folgt die Kongruenz

$(p\,n+1)\,C_{p\,n}\equiv (n+1)\,C_{n}\ ({\text{mod }}p^{3})$

für jede Primzahl $p>3$, für Wolstenholme-Primzahlen gilt die Kongruenz (mod p⁴), für die Primzahlen 2 und 3 gilt sie (mod p²).

Insbesondere ist $C_{p^{k}n}\equiv (n+1)\,C_{n}\ ({\text{mod }}p)$ und $C_{p^{k}}\equiv 2\ ({\text{mod }}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

$C_{n}\sim 4^{n}/{\bigl (}(n+1){\sqrt {\pi n}}\,{\bigr )}\,.$

Weitere Interpretationen

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

• Beklammerungen eines Produktes, in dem n Multiplikationen vorkommen, oder, gleichbedeutend, mit n+1 Faktoren, so dass immer nur die Multiplikation von zwei Faktoren durchzuführen ist (Catalan 1838). Beispielsweise ist $C_{3}=5$, denn alle möglichen Beklammerungen von $x_{1}x_{2}x_{3}x_{4}$ sind $(x_{1}x_{2})(x_{3}x_{4}),{\text{ }}(x_{1}(x_{2}x_{3}))x_{4},{\text{ }}x_{1}((x_{2}x_{3})x_{4}),{\text{ }}((x_{1}x_{2})x_{3})x_{4}$ und $x_{1}(x_{2}(x_{3}x_{4}))$.
• eindimensionalen Irrfahrten von 0 nach 2n mit Anfangs- und Endpunkt in 0, so dass sich der Pfad nie unterhalb der x-Achse befindet (sogenannte Dyck-Pfade nach Walther von Dyck). Zum Beispiel ist $C_{3}=5$, denn alle möglichen Pfade sind:

• geordneten vollen Binärbäume mit 2n+1 Knoten oder, gleichbedeutend, mit n+1 Blättern (= Endecken). Folgendes Diagramm zeigt einen von $C_{8}$ = 1430 solchen Binärbäumen für n=8:

• möglichen Verläufe der Auszählung bei einer Wahl, bei denen Kandidat A nach jeder gezählten Stimme nie hinter Kandidat B liegt, wenn beide Kandidaten je n Stimmen erhalten und die Stimmzettel nacheinander aus der Urne geholt und gezählt werden. Beispielsweise für n=2 wären die möglichen Ziehungsfolgen, die die Voraussetzung erfüllen, ABAB und AABB.
• Möglichkeiten, wie sich 2n Personen, die an einem runden Tisch sitzen, paarweise über den Tisch die Hände schütteln, ohne dass sich Arme überkreuzen.

Literatur

• Peter J. Hilton, Jean Pedersen: Catalan-Zahlen und Wege in einem ganzzahligen Gitter, Elemente der Mathematik 48, 1993, S. 45–60
• Jürgen Schmidthammer: Catalan-Zahlen (PDF-Datei, 7,05 MB), Zulassungsarbeit zum Staatsexamen, Erlangen Februar 1996
• Thomas Koshy: Catalan Numbers with Applications. Oxford University Press, New York 2009, ISBN 978-0-19-533454-8.
• Richard P. Stanley: Enumerative combinatorics Band 2, Cambridge University Press, Cambridge 1999, ISBN 0-521-56069-1 (englisch; Stanleys Webseite zum Buch mit laufend aktualisierter Liste zu Interpretationen der Catalan-Zahlen: Information on Enumerative Combinatorics)

Weblinks

Commons: Catalan-Zahlen – Sammlung von Bildern, Videos und Audiodateien

• Eric W. Weisstein: Catalan Number. In: MathWorld (englisch).
• Lattice Paths: Catalan Numbers in der NIST Digital Library of Mathematical Functions (englisch)