Catalan-Zahlen Rechner
Berechnen Sie Catalan-Zahlen mit Anwendungen in Kombinatorik und Binärbäumen
Geben Sie eine nicht-negative ganze Zahl ein (0 bis 30)
Ergebnisse
Geben Sie Werte ein und klicken Sie auf Berechnen, um das Ergebnis zu sehen.
Theorie & Formel
Catalan-Zahlen
Catalan-Zahlen bilden eine Folge natürlicher Zahlen, die in verschiedenen Zählproblemen auftreten, oft mit rekursiv definierten Objekten. Die n-te Catalan-Zahl zählt die Anzahl der Ausdrücke mit n Klammerpaaren, die korrekt zugeordnet sind.
Formeln
\(C_n = \frac{1}{n+1}\binom{2n}{n} = \frac{(2n)!}{(n+1)!n!}\)
\(C_n = \sum_{i=0}^{n-1} C_i \cdot C_{n-1-i}\)
Die erste Formel verwendet Binomialkoeffizienten, die zweite ist eine rekursive Definition
Anwendungen
- Anzahl der Möglichkeiten, n Klammerpaare korrekt zuzuordnen
- Anzahl verschiedener Binärbäume mit n+1 Blättern
- Number of paths from (0,0) to (n,n) that do not cross the diagonal
- Number of ways to triangulate a convex polygon with n+2 sides
- Number of ways to connect 2n points on a circle with n non-crossing chords
First Catalan numbers
The first Catalan numbers are: 1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796...
Example
Calculate C₃ (number of ways to match 3 pairs of parentheses):
\(C_3 = \frac{1}{4}\binom{6}{3} = \frac{1}{4} \cdot 20 = 5\)