Die Catalan-Zahlen sind nach dem belgischen Mathematiker Eugène Charles Catalan benannt, welcher diese 1855 entdeckte. Sie geben das Verhältnis aus dem Zentralbinomialkoeffizienten und seiner fortlaufenden Nummer plus eins an. Der Zentralbinomialkoeffizient für n=1 wird also durch zwei geteilt, der für n=2 durch drei und so weiter, um die entsprechende Catalan-Zahl zu erhalten. Catalan-Zahlen treten bei vielen Berechnungen in der Kombinatorik auf, beispielsweise bei Abzählungsaufgaben in der Graphentheorie.
Die Zählung der Catalan-Zahlen beginnt bei Null, also ist die erste Catalan-Zahl C0 mit dem Wert 1. C1=1, C2=2, die Folge geht dann weiter mit 5, 14, 42, 132, 429, 1430, ...
| Cn = | 1 | ( | 2n | ) |
| n + 1 | n |
Geben Sie für n eine natürliche Zahl (positive ganze Zahl) ein und klicken Sie dann auf Berechnen, um die Catalan-Zahl zu errechnen.
Ein Beispiel für ein Problem, welches sich mit der Berechnung von Catalan-Zahlen lösen lässt: man hat x verschiedene Variablen. Hier sei x=4 mit den Variablen a, b, c und d. Wie viele Möglichkeiten gibt es, mit diesen mit einer bestimmten Verknüpfung und mit Klammern zu rechnen. Es geht also um die korrekten Klammerkombinationen. Diese Anzahl ist die vierte Catalan-Zahl C3, also jene für n=3. Es gibt also fünf Möglichkeiten, diese sind:
• ((a ∘ b) ∘ c) ∘ d
• (a ∘ (b ∘ c)) ∘ d
• (a ∘ b) ∘ (c ∘ d)
• a ∘ ((b ∘ c) ∘ d)
• a ∘ (b ∘ (c ∘ d))
Ob diese fünf verschiedenen Rechnungen gleiche oder unterschiedliche Ergebnisse bringen hängt von der Assoziativität der Verknüpfung ab. Bei Plus und Mal sind die Ergebnisse gleich, bei Minus und Geteilt sind sie verschieden, ebenso bei Hoch.
Weitere Beispiele, bei denen die Lösungen jeweils Cn sind, wären:
Binäre Bäume: wie viele verschiedene Strukturen kann ein binärer Entscheidungsbaum mit n Knoten haben?
Pfadplanung: wie viele Wege führen in einem Gitter diagonal von (0,0) nach (n,n), ohne je über die Diagonale hinauszugehen?
Triangulierung eines Polygons: wie viele Möglichkeiten gibt es, ein n+2-Eck in Dreiecke zu zerlegen, ohne dass sich Diagonalen schneiden?
Kombinatorik und Statistik Rechner © Jumk.de Webprojekte | Rechneronline | Impressum & Datenschutz
Alle Angaben ohne Gewähr | English: Combinatorics and Statistics Functions
Siehe auch Statistik-Rechner, Wahrscheinlichkeiten: Ziehen mit/ohne Zurücklegen
big.js Script Copyright (c) 2022 Michael Mclaughlin, MIT Expat Licence.