Notice: Unexpected clearActionName after getActionName already called in /var/www/html/includes/context/RequestContext.php on line 338 Catalan-Zahl – WikipediaZum Inhalt springen
Datei:Noncrossing partitions 5.svgDie Catalan-Zahlen zählen beispielsweise die nicht überkreuzenden Partitionen einer Menge mit <math>n</math> Elementen, hier <math>C_5 = 42</math> (oberer Bildteil), während die Zahl aller Partitionen durch die Bellschen Zahlen angegeben wird, hier <math>B_5 = 52</math>
wobei <math>\tbinom{2n}{n}</math> der mittlere Binomialkoeffizient ist. Mit <math>\tbinom{2n}{n+1} = \tfrac{n}{n+1} \tbinom{2n}{n}</math> erhält man, dass die Formel äquivalent zu
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).
Euler suchte die Anzahl der Möglichkeiten, ein konvexes <math>n </math>-Eck durch Diagonalen in Dreiecke zu zerteilen (Triangulation). Diese Anzahl ist <math>C_{n-2}</math>. Zum Beispiel gibt es für ein Fünfeck fünf mögliche Triangulationen:
{{#invoke:Vorlage:Anker|f |errCat=Wikipedia:Vorlagenfehler/Vorlage:Anker |errHide=1}} Euler gab in seinem Brief an Goldbach 1751 (siehe Historisches) die explizite Formel
Da alle Primfaktoren von <math>\textstyle C_n = 2^n\,\frac{1 \cdot 3 \cdot 5 \cdots (2n-1)}{2 \cdot 3 \cdot 4 \cdots (n+1)}</math>, siehe Formel, kleiner als <math>2n</math> sind und <math>C_n > 2 n</math> für <math>n > 3</math> gilt, sind <math>C_2 = 2</math> und <math>C_3 = 5</math> als einzige Catalan-Zahlen auch Primzahlen. Die Formel zeigt auch, dass <math>C_n</math> durch jede Primzahl zwischen <math>n+1</math> und <math>2n</math> genau einmal teilbar ist und genau dann ungerade ist, wenn <math>n + 1</math> eine Potenz von 2 ist.
für jede Primzahl <math>p > 3</math>, für Wolstenholme-Primzahlen gilt die Kongruenz <math>\operatorname{mod}\ p^4</math>, für die Primzahlen 2 und 3 gilt sie <math>\operatorname{mod}\ p^2</math>.
Insbesondere ist <math>C_{p^k n} \equiv (n + 1)\,C_n \pmod p</math> und <math>C_{p^k} \equiv 2 \pmod p</math> für jede Primzahl <math>p</math> und ganze Zahl <math>k > 0</math>.
Die Catalan-Zahlen treten bei zahlreichen Abzählungsaufgaben auf, die graphentheoretisch Abzählungen von Bäumen sind. So ist <math>C_n</math> die Anzahl der
Binärbäume mit <math>n</math> Knoten. Dies ist gleich der Anzahl der Klammerungen eines Produktes, in dem <math>n</math> Multiplikationen vorkommen oder, gleichbedeutend, mit <math>n + 1</math> Faktoren, sodass immer nur die Multiplikation von zwei Faktoren durchzuführen ist.<ref name="catalan" /> 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 <math>n = 3</math> eine Zeichenfolge wie <math>X * X * X * X</math> in Klammern setzen, was auf 5 verschiedene Arten möglich ist:
<math>((X * X) * X) * X \qquad (X * (X * X)) * X \qquad (X * X) * (X * X) \qquad X * ((X * X) * X) \qquad X * (X * (X * X))</math>
Daher ist <math>C_3 = 5</math>. 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 <math>i</math> bzw. <math>j</math> Knoten haben, hat der gesamte Baum <math>i + j + 1</math> Knoten. Daher hat die Anzahl <math>C_n</math> von Binärbäumen mit <math>n</math> Knoten die folgende rekursive Beschreibung <math>C_0 = 1</math> und <math>\textstyle C_n = \sum_{i=0}^{n - 1} C_i \cdot C_{n - 1 - i}</math> für jede positive ganze Zahl <math>n</math>. Daraus folgt, dass <math>C_n</math> die Catalan-Zahl mit Index <math>n</math> ist. Diese ist beispielsweise ein Maß für die Anzahl der möglichen Berechnungsreihenfolgen bei der nichtkommutativenMatrix-Kettenmultiplikation, wo durch geschickt optimierte Klammerung der Rechenaufwand minimiert werden kann.
eindimensionalenIrrfahrten von 0 nach <math>2n</math> mit Anfangs- und Endpunkt in 0, sodass sich der Pfad nie unterhalb der <math>x</math>-Achse befindet (sogenannte Dyck-Pfade nach Walther von Dyck). Zum Beispiel ist <math>C_3=5</math>, denn alle möglichen Pfade sind:
monotonen Pfade entlang der Ränder eines Quadratgitters mit <math>n \times n</math> 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 <math>n = 4</math> sind:<ref name="ijpam.eu">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.</ref>
Möglichkeiten, eine Stufenform der Breite <math>n</math> und Höhe <math>n</math> mit <math>n</math> Rechtecken zu kacheln. Die 14 Möglichkeiten für <math>n = 4</math> sind:<ref name="ijpam.eu" />
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 <math>n</math> Stimmen erhalten und die Stimmzettel nacheinander aus der Urne geholt und gezählt werden. Beispielsweise für <math>n = 2</math> wären die möglichen Ziehungsfolgen, die die Voraussetzung erfüllen, ABAB und AABB.<ref name="BuchC++">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.</ref>
Möglichkeiten, wie sich <math>2n</math> Personen, die an einem runden Tisch sitzen, paarweise über den Tisch die Hand geben, ohne dass sich Arme überkreuzen.<ref name="BuchC++" />
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).
|X|x=
|0|-=
|S|s= – Sammlung von Bildern
|1|= – Sammlung von Bildern{{#if:
| {{#switch: {{#invoke:TemplUtl|faculty|1}}/{{#invoke:TemplUtl|faculty|1}}
|1/= und Videos
|1/1=, Videos und Audiodateien
|/1= und Audiodateien}}
| , Videos und Audiodateien
}}
