Catalan-Zahlen Rechner

🌳 Verschiedene Darstellungen

Äquivalente mathematische Formulierungen der Catalan-Zahlen:

\[C_n = \frac{1}{n+1} \binom{2n}{n} \quad \text{(Standard-Form)}\] \[C_n = \frac{(2n)!}{(n+1)! \cdot n!} \quad \text{(Fakultäten-Form)}\] \[C_n = \binom{2n}{n} - \binom{2n}{n+1} \quad \text{(Differenz-Form)}\] \[C_n = \frac{1}{2\pi} \int_0^4 x^n \sqrt{\frac{4-x}{x}} \, dx \quad \text{(Integral-Form)}\]

🔄 Rekursionsformeln

Verschiedene rekursive Beziehungen:

\[\text{Hauptrekursion: } C_n = \sum_{i=0}^{n-1} C_i \cdot C_{n-1-i}\] \[\text{Einfache Rekursion: } C_n = \frac{2(2n-1)}{n+1} C_{n-1}\] \[\text{Startwert: } C_0 = 1\] \[\text{Explizit: } C_{n+1} = \frac{4n+2}{n+2} C_n\]

📊 Asymptotisches Verhalten

Wachstumsverhalten für große n:

\[C_n \sim \frac{4^n}{n^{3/2}\sqrt{\pi}} \quad \text{für } n \to \infty\] \[\frac{C_{n+1}}{C_n} \to 4 \quad \text{(Wachstumsfaktor)}\] \[\log_4(C_n) \approx n - \frac{3}{2}\log_4(n) \quad \text{(Logarithmisches Wachstum)}\]

📝 Beispiel 1: Binärbäume zählen

Aufgabe: Wie viele vollständige Binärbäume gibt es mit 4 Blättern?
Lösung: Suche C₃ (n = Anzahl Blätter - 1)
Berechnung:

\[C_3 = \frac{1}{3+1} \binom{2 \cdot 3}{3} = \frac{1}{4} \binom{6}{3}\] \[\binom{6}{3} = \frac{6!}{3! \cdot 3!} = \frac{720}{6 \cdot 6} = 20\] \[C_3 = \frac{20}{4} = 5\]

Antwort: Es gibt 5 verschiedene vollständige Binärbäume mit 4 Blättern

📝 Beispiel 2: Klammerungen berechnen

Aufgabe: Auf wie viele Arten kann man "(((())))" korrekt klammern?
Gegeben: 3 Klammerpaare
Berechnung:

\[C_3 = \frac{1}{4} \binom{6}{3} = \frac{1}{4} \cdot 20 = 5\] \[\text{Die 5 Möglichkeiten sind:}\] \[\text{1. } ((()))\] \[\text{2. } (()())\] \[\text{3. } (())()\] \[\text{4. } ()(())\] \[\text{5. } ()()()\]

Interpretation: 5 verschiedene korrekte Klammerstrukturen mit 3 Paaren

📝 Beispiel 3: Gitterpfade

Aufgabe: Monotone Pfade von (0,0) nach (4,4), die nicht über die Diagonale gehen
Bedingung: Pfad bleibt immer unterhalb oder auf y = x
Berechnung:

\[\text{Gesucht: } C_4 = \frac{1}{5} \binom{8}{4}\] \[\binom{8}{4} = \frac{8!}{4! \cdot 4!} = \frac{40320}{24 \cdot 24} = 70\] \[C_4 = \frac{70}{5} = 14\]

Interpretation: 14 verschiedene erlaubte Pfade im 4×4-Gitter

📊 Catalan-Zahlen C₀ bis C₁₀

💻 Code-Implementierungen

Effiziente Berechnung der Catalan-Zahlen:

Python - Rekursive Methode:
def catalan_recursive(n):
  if n <= 1:
    return 1
  result = 0
  for i in range(n):
    result += catalan_recursive(i) * catalan_recursive(n-1-i)
  return result

Python - Dynamische Programmierung:
def catalan_dp(n):
  if n <= 1: return 1
  dp = [0] * (n + 1)
  dp[0], dp[1] = 1, 1
  for i in range(2, n + 1):
    for j in range(i):
      dp[i] += dp[j] * dp[i-1-j]
  return dp[n]

Python - Formel-basiert:
from math import comb
def catalan_formula(n):
  return comb(2*n, n) // (n + 1)

📊 JavaScript-Implementierung

Web-freundliche Implementierung:

JavaScript:
function catalan(n) {
  if (n <= 1) return 1;
  
  // Berechnung mit Formel
  let numerator = 1;
  let denominator = 1;
  
  for (let i = 0; i < n; i++) {
    numerator *= (2 * n - i);
    denominator *= (i + 1);
  }
  
  return Math.floor(numerator / denominator / (n + 1));
}

// Beispiel:
console.log(catalan(4)); // Ausgabe: 14

⚡ Komplexitätsanalyse

Effizienz verschiedener Ansätze:

\[\text{Naive Rekursion: } O(4^n) \text{ - exponentiell schlecht}\] \[\text{Dynamische Programmierung: } O(n^2) \text{ - quadratisch}\] \[\text{Formel-basiert: } O(n) \text{ - linear optimal}\] \[\text{Speicher: } O(1) \text{ für Formel, } O(n) \text{ für DP}\]

📚 Geschichte der Catalan-Zahlen

Wichtige Meilensteine in der Entwicklung:

• 1751: Leonhard Euler - Erste Erwähnung im Kontext von Polygon-Triangulierung
• 1838: Eugène Charles Catalan - Systematische Untersuchung und Namensgebung
• 1887: Désiré André - Ballot-Problem und Reflektion-Prinzip
• 1946: Théodore Motzkin - Verallgemeinerung zu Motzkin-Zahlen
• 1970er: Computer-Ära - Algorithmische Implementierungen
• Heute: Anwendungen in Informatik, Physik und Bioinformatik