Catalan-Zahl

Die Catalan-Zahlen o​der catalanschen Zahlen bilden e​ine Folge natürlicher Zahlen, d​ie in vielen Problemen d​er Kombinatorik auftritt u​nd eine ähnlich wichtige Rolle w​ie die Binomialkoeffizienten o​der die Fibonacci-Zahlen spielt. Sie s​ind nach d​em belgischen Mathematiker Eugène Charles Catalan benannt.

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

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 ${\displaystyle n\geq 0}$ gegeben durch

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

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

${\displaystyle C_{n}={\binom {2n}{n}}-{\binom {2n}{n+1}}}$

ist u​nd somit tatsächlich n​ur ganze Zahlen liefert.

Historisches

Als Erster f​and der Chinese Minggatu Catalan-Zahlen i​n seiner Arbeit z​u unendlichen Reihen für trigonometrische Funktionen (1730er Jahre a​ls Manuskript zirkulierend, a​ber erst 1839 a​ls Buch veröffentlicht).

Die Zahlen dieser Folge wurden bereits 1751 v​on Leonhard Euler i​n einem Brief a​n Christian Goldbach beschrieben.[1] Johann Andreas v​on Segner f​and 1758 e​ine Rekursionsformel,[2] z​u der Euler i​n der Zusammenfassung z​u Segners Artikel d​ie Lösung angab.[3] Eine v​on Johann Friedrich Pfaff gestellte allgemeinere Abzählungsaufgabe löste 1795 Nikolaus Fuss.[4] In d​en Jahren 1838 u​nd 1839 griffen Gabriel Lamé,[5] Olinde Rodrigues,[6] Jacques Binet[7][8] u​nd Eugène Catalan[9][10] d​ie Fragestellung erneut auf. Eugen Netto führte i​n seinem 1901 veröffentlichten Lehrbuch d​er Combinatorik d​ie Zahlen a​uf Catalan zurück.[11]

Eigenschaften

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

Euler g​ab in seinem Brief a​n Goldbach 1751 (siehe Historisches) d​ie 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 d​ie Formel

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

für d​ie erzeugende Funktion an, insbesondere

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

auch a​ls Beschreibung d​es Wachstumsverhaltens.[1]

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

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

Direkt a​us der Formel (*) folgt

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

Es g​ilt außerdem d​ie Rekursionsformel (Segner 1758)[2]

${\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 m​it den Motzkin-Zahlen M (Folge A001006 i​n OEIS)

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

Da alle Primfaktoren von ${\displaystyle \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 ${\displaystyle 2n}$ sind und ${\displaystyle C_{n}>2n}$ für ${\displaystyle n>3}$ gilt, sind ${\displaystyle C_{2}=2}$ und ${\displaystyle C_{3}=5}$ als einzige Catalan-Zahlen auch Primzahlen. Die Formel zeigt auch, dass ${\displaystyle C_{n}}$ durch jede Primzahl zwischen ${\displaystyle n+1}$ und ${\displaystyle 2n}$ genau einmal teilbar ist und genau dann ungerade ist, wenn ${\displaystyle n+1}$ eine Potenz von 2 ist.

Aus d​em Satz v​on Wolstenholme f​olgt die Kongruenz

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

für jede Primzahl ${\displaystyle 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 ${\displaystyle p}$ und ganze Zahl ${\displaystyle k>0}$.

Durch Einsetzen d​er Stirling-Formel erhält m​an für d​as asymptotische Verhalten d​er Catalan-Zahlen

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

Die Summe d​er Kehrwerte konvergiert:[12]

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

Zudem g​ilt (Folge A013709 i​n 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 d​ie Cauchy-Produktformel m​it dem Basler Problem ergibt s​ich daraus (Folge A281070 i​n 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 ${\displaystyle C_{n}}$ die Anzahl der

• Binärbäume mit ${\displaystyle n}$ Knoten. Dies ist gleich der Anzahl der Klammerungen eines Produktes, in dem ${\displaystyle n}$ Multiplikationen vorkommen oder, gleichbedeutend, mit ${\displaystyle n+1}$ Faktoren, sodass immer nur die Multiplikation von zwei Faktoren durchzuführen ist.[9] 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 ${\displaystyle 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 ${\displaystyle 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 ${\displaystyle i}$ bzw. ${\displaystyle j}$ Knoten haben, hat der gesamte Baum ${\displaystyle i+j+1}$ Knoten. Daher hat die Anzahl ${\displaystyle C_{n}}$ von Binärbäumen mit ${\displaystyle 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 ${\displaystyle n}$. Daraus folgt, dass ${\displaystyle C_{n}}$ die Catalan-Zahl mit Index ${\displaystyle 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 ${\displaystyle 2n}$ mit Anfangs- und Endpunkt in 0, sodass sich der Pfad nie unterhalb der ${\displaystyle x}$-Achse befindet (sogenannte Dyck-Pfade nach Walther von Dyck). Zum Beispiel ist ${\displaystyle C_{3}=5}$, denn alle möglichen Pfade sind:

• monotonen Pfade entlang der Ränder eines Quadratgitters mit ${\displaystyle n\times n}$ quadratischen Zellen, die nicht oberhalb der Diagonale verlaufen. 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 ${\displaystyle n=4}$ sind:[13]

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

• 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 ${\displaystyle n}$ Stimmen erhalten und die Stimmzettel nacheinander aus der Urne geholt und gezählt werden. Beispielsweise für ${\displaystyle n=2}$ wären die möglichen Ziehungsfolgen, die die Voraussetzung erfüllen, ABAB und AABB.[14]
• Möglichkeiten, wie sich ${\displaystyle 2n}$ Personen, die an einem runden Tisch sitzen, paarweise über den Tisch die Hand geben, ohne dass sich Arme überkreuzen.[14]

Literatur

• Peter J. Hilton, Jean Pedersen: Catalan-Zahlen und Wege in einem ganzzahligen Gitter. Elemente der Mathematik 48, 1993, S. 45 ff.
• 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

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

Einzelnachweise

1. Brief (PDF-Datei; 137 kB) von Euler an Goldbach vom 4. September 1751, abgedruckt in Paul Heinrich Fuss (Hrsg.): Correspondance mathématique et physique de quelques célèbres géomètres du XVIIIème siècle. (Band 1), St.-Pétersbourg 1843, S. 549–552.
2. Ioh. Andr. de Segner: Enumeratio modorum quibus figurae planae rectilineae per diagonales dividuntur in triangula. Novi commentarii academiae scientiarum imperialis petropolitanae 7 pro annis 1758 et 1759, 1761, S. 203–210 (lateinisch).
3. Leonhard Euler: Summarium dissertationum. Novi commentarii academiae scientiarum imperialis petropolitanae 7 pro annis 1758 et 1759, 1761, S. 13–15 (lateinisch).
4. Nicolao Fuss: Solutio quaestionis, quot modis polygonum n laterum in polygona m laterum, per diagonales resolvi queat. Nova acta academiae scientiarum imperialis petropolitanae 9, 1795, S. 243–251 (lateinisch).
5. Gabriel Lamé: Extrait d’une lettre de M. Lamé à M. Liouville sur cette question: Un polygone convexe étant donné, de combien de manières peut-on le partager en triangles au moyen de diagonales? Journal de mathématiques pures et appliquées 3, 1838, S. 505–507 (französisch).
6. Olinde Rodrigues: Sur le nombre de manières de décomposer un polygone en triangles au moyen de diagonales und Sur le nombre de manières d’effectuer un produit de n facteurs. Journal de mathématiques pures et appliquées 3, 1838, S. 547–549 (französisch).
7. J. Binet: Problèmes sur les polygones. Société philomathique de Paris – Séances de 1838 – Extraits des procès-verbaux, S. 127–129 (französisch).
8. J. Binet: Réflexions sur le problème de déterminer le nombre de manières dont une figure rectiligne peut être partagée en triangles au moyen de ses diagonales. Journal de mathématiques pures et appliquées 4, 1839, S. 79–90 (französisch).
9. E. Catalan: Note sur une équation aux différences finies. Journal de mathématiques pures et appliquées 3, 1838, S. 508–516, und 4, 1838, S. 95–99 (französisch).
10. E. Catalan: Solution nouvelle de cette question: Un polygone étant donné, de combien de manières peut-on le partager en triangles au moyen de diagonales? Journal de mathématiques pures et appliquées 4, 1839, S. 91–94 (französisch).
11. Eugen Netto: Lehrbuch der Combinatorik. B. G. Teubner, Leipzig 1901 (Zurückführung der Zahlen auf Catalan in § 122, S. 192–194 und § 124, S. 195).
12. whole sum of the reciprocal Catalan numbers. Bei: juanmarqz.wordpress.com. 29. Juli 2009, abgerufen am 11. Januar 2021.
13. Matej Crepinsek, Luka Mernik: An efficient representation for solving Catalan number related problems. (PDF; 253 kB). In: ijpam.eu. International Journal of Pure and Applied Mathematics, abgerufen am 11. Januar 2021.
14. Doina Logofătu: Algorithmen und Problemlösungen mit C++. Kapitel 8 Catalan-Zahlen. Vieweg-Verlag, 1. Auflage 2006, ISBN 978-3-8348-0126-5, S. 189–206.