Catalan-Zahl

Die Catalan-Zahlen zählen beispielsweise die nicht überkreuzenden Partitionen einer Menge mit $n$ Elementen, hier $C_5=42$ (oberer Bildteil), während die Zahl aller Partitionen durch die Bellschen Zahlen angegeben wird, hier $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 $C_0,C_1,C_2,C_3,\dots$ beginnt mit

1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786, 208012, 742900, … (Vorlage:OEIS)

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

$C_n=\frac{1}{n+1}(\genfrac{}{}{0ex}{}{2n}{n})=\frac{(2n)!}{(n+1)!n!},$

wobei $(\genfrac{}{}{0ex}{}{2n}{n})$ der mittlere Binomialkoeffizient ist. Mit $(\genfrac{}{}{0ex}{}{2n}{n+1})=\frac{n}{n+1}(\genfrac{}{}{0ex}{}{2n}{n})$ erhält man, dass die Formel äquivalent zu

$C_n=(\genfrac{}{}{0ex}{}{2n}{n})-(\genfrac{}{}{0ex}{}{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

Vorlage:Anker 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}$

und die Formel

$\sum _{n=0}^{\mathrm{\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}^{\mathrm{\infty }}\frac{C_n}{4^n}=2$

auch als Beschreibung des Wachstumsverhaltens.

Mit der Gammafunktion $\mathrm{\Gamma }$ gilt:

$C_n=\frac{4^n\mathrm{\Gamma }(\frac{1}{2}+n)}{\sqrt{\pi }\mathrm{\Gamma }(2+n)}$

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{C}_2+C_1{C}_1+C_2{C}_0$.

Eine weitere Rekursionsformel ist

$C_{n+1}=\sum _{k=0}^{\lfloor n/2\rfloor }(\genfrac{}{}{0ex}{}{n}{2k})2^{n-2k}{C}_k$

sowie mit den Motzkin-Zahlen M (Vorlage:OEIS)

$C_{n+1}=\sum _{k=0}^n(\genfrac{}{}{0ex}{}{n}{k})M_k.$

Da alle Primfaktoren von $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$ 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

$(pn+1)C_{pn}\equiv (n+1)C_n(\mathrm{mod}{p}^3)$

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

Insbesondere ist $C_{p^{k}n}\equiv (n+1)C_n(\mathrm{mod}p)$ und $C_{p^k}\equiv 2(\mathrm{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 \frac{4^n}{(n+1)\sqrt{\pi n}}.$

Die Summe der Kehrwerte konvergiert:

$\sum _{n=0}^{\mathrm{\infty }}\frac{1}{C_n}=2+\frac{4\sqrt{3}\pi }{27}$

Zudem gilt (Vorlage:OEIS 2016):

$\sum _{n=0}^{\mathrm{\infty }}{\left(\frac{C_n}{2^{2n+1}}\right)}^2(n+1)=\frac{1}{\pi }$ sowie

$\sum _{n=0}^{\mathrm{\infty }}{\left(\frac{C_n}{2^{2n+1}}\right)}^2(4n+3)=1$

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

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

$\sum _{n=0}^{\mathrm{\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

• Binärbäume mit $n$ Knoten. Dies ist gleich der Anzahl der Klammerungen eines Produktes, in dem $n$ Multiplikationen vorkommen oder, gleichbedeutend, mit $n+1$ Faktoren, sodass immer nur die Multiplikation von zwei Faktoren durchzuführen ist. Statt der Multiplikationen können es beliebige mathematische Operatoren für eine zweistellige Verknüpfung, zum Beispiel Addition, Subtraktion, Multiplikation oder Division sein. Die Reihenfolge der Zahlen oder Elemente, zum Beispiel Matrizen, ist festgelegt. Die Operation muss weder assoziativ noch kommutativ sein. Dabei entspricht jeder Knoten des Binärbaums einer zweistellige Verknüpfung und für jeden Knoten entspricht der linke Teilbaum dem linken Ausdruck und der rechte Teilbaum dem rechten Ausdruck der Verknüpfung.

Zum Beispiel muss man für $n=3$ eine Zeichenfolge wie $X*X*X*X$ in Klammern setzen, was auf 5 verschiedene Arten möglich ist:

$((X*X)*X)*X(X*(X*X))*X(X*X)*(X*X)X*((X*X)*X)X*(X*(X*X))$

Ein explizites Beispiel für die Subtraktion ist

$((10-6)-3)-1(10-(6-3))-1(10-6)-(3-1)10-((6-3)-1)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 $i+j+1$ Knoten. Daher hat die Anzahl $C_n$ von Binärbäumen mit $n$ Knoten die folgende rekursive Beschreibung $C_0=1$ und $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.

• eindimensionalen Irrfahrten von 0 nach $2n$ mit Anfangs- und Endpunkt in 0, sodass 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:

• monotonen Pfade entlang der Ränder eines Quadratgitters mit $n\times n$ quadratischen Zellen, die keinen Punkt oberhalb der Diagonale enthalten. Ein monotoner Pfad beginnt in der unteren linken Ecke, endet in der oberen rechten Ecke und besteht vollständig aus Kanten, die nach rechts oder oben zeigen. Die 14 monotonen Pfade für $n=4$ sind:

• Möglichkeiten, eine Stufenform der Breite $n$ und Höhe $n$ mit $n$ Rechtecken zu kacheln. Die 14 Möglichkeiten für $n=4$ sind:

• 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 Hand geben, ohne dass sich Arme überkreuzen.

Literatur

• Peter J. Hilton, Jean Pedersen: Catalan-Zahlen und Wege in einem ganzzahligen Gitter. Elemente der Mathematik 48, 1993, doi:10.5169/seals-44624#51, S. 45 ff.
• Jürgen Schmidthammer: Catalan-Zahlen. (PDF; 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

• Vorlage:MathWorld
• Lattice Paths: Catalan Numbers in der NIST Digital Library of Mathematical Functions (englisch)