Catalan-Zahlen
Voraussetzung:
- n-te Catalan-Zahl
- Größenparameter, z.B. Anzahl der Klammerpaare
- Binomialkoeffizient „2n über n“
Die Catalan-Zahlen zählen korrekte Klammerungen, Triangulierungen von Vielecken, Binärbäume und Gitterwege unter der Diagonale.
Erklärung
Die Catalan-Zahlen sind die Folge
Sie tauchen bei vielen Abzählproblemen auf, die auf den ersten Blick nichts miteinander zu tun haben. ist jeweils die Anzahl der
- korrekten Klammerungen aus öffnenden und schließenden Klammern,
- Gitterwege von nach mit Schritten nach rechts und nach oben, die nie über die Diagonale steigen (Dyck-Wege),
- Triangulierungen eines konvexen -Ecks durch sich nicht kreuzende Diagonalen,
- Binärbäume mit Knoten,
- Möglichkeiten, ein Produkt aus Faktoren vollständig zu klammern.
Neben der geschlossenen Formel erfüllen sie die Rekursion
Sie entsteht, wenn man die erste öffnende Klammer und die zu ihr passende schließende betrachtet: Innen steht eine korrekte Klammerung mit Paaren, dahinter eine mit Paaren.
Herleitung
Über Gitterwege mit dem Spiegelungsprinzip: Von nach gibt es insgesamt Wege. Ein Weg, der die Diagonale überschreitet, berührt irgendwann zum ersten Mal die Gerade . Spiegelt man das Stück davor an dieser Geraden, entsteht umkehrbar eindeutig ein Weg von nach , also mit Rechts- und Hochschritten. Davon gibt es . Also
Beispiele
Drei Klammerpaare: . Die fünf Klammerungen sind
Sechseck triangulieren: Ein Sechseck ist ein -Eck mit . Es gibt Triangulierungen. Mit der Rekursion: .
Gitterwege für : Von den Wegen nach überschreiten die Diagonale, es bleiben .
Größere Werte: und .
Typische Fehler
- Den Index verschieben. Ein -Eck hat Triangulierungen, nicht : Das Sechseck gehört zu .
- Den Faktor vergessen. zählt alle Gitterwege, auch die, die über die Diagonale steigen.
- statt schreiben. Für ergäbe das , keine ganze Zahl.