Catalan-Zahl

Eugène Charles Catalan

Die Catalan-Zahlen, oder Catalansche Zahlen, benannt nach dem belgischen Mathematiker Eugène Charles Catalan (1814–1894), stellen eine Folge natürlicher Zahlen dar, die in vielen Problemen der Kombinatorik auftaucht. Die n-te Catalan-Zahl $C_{n}$ ist z.B. die Anzahl der verschiedenen Möglichkeiten, ein konvexes (n+2)-Eck durch Diagonalen in Dreiecke zu zerteilen (Triangulation). Die ersten Catalan-Zahlen für n = 0, 1, 2, ... sind 1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, ...

Für ein Fünfeck gibt es fünf mögliche Triangulationen.

Für die Catalan-Zahlen gilt für $n\geq 0$:

$C_{n}={\frac {1}{n+1}}{2n \choose n}$

Wobei ${n \choose k}$ den Binomialkoeffizienten bezeichnet.

Eine Rekursionsformel lautet

$C_{n+1}=\sum _{k=0}^{n}C_{k}C_{n-k}$ (also z.B. $C_{3}=C_{0}C_{2}+C_{1}C_{1}+C_{2}C_{0}$)

und die erzeugende Funktion ist

${\frac {1-{\sqrt {1-4z}}}{2z}}=\sum _{n=0}^{\infty }C_{n}z^{n}$ (für |z| < 1/4).

Weitere Interpretation für die Catalan-Zahlen

• $C_{n+1}$ ist die Anzahl der möglichen Beklammerungen eines Produktes, in dem n Multiplikationen vorkommen (also mit n+1 Faktoren), so dass immer nur die Multiplikation von zwei Faktoren durchzuführen ist. Es ist $C_{3}=5$, denn alle möglichen Beklammerungen von $x_{1}x_{2}x_{3}x_{4}$ sind die folgenden:
  • $(x_{1}x_{2})(x_{3}x_{4})$
  • $(x_{1}(x_{2}x_{3}))x_{4}$
  • $x_{1}((x_{2}x_{3})x_{4})$
  • $((x_{1}x_{2})x_{3})x_{4}$
  • $x_{1}(x_{2}(x_{3}x_{4}))$

• $C_{n}$ ist die Anzahl aller eindimensionalen Irrfahrten von 0 nach 2n mit Anfangs- und Endpunkt in 0, so dass sich der Pfad nie unterhalb der x-Achse befindet. Es ist wieder $C_{3}=5$, denn alle möglichen Pfade sind:

• $C_{n}$ ist die Anzahl der möglichen Binärbäume, die sich aus (2n+1) Knoten bilden lassen, das heißt (n+1) Endecken/Blätter haben.

Ein Baum mit neun Endecken

Weitere Folgeglieder

Catalan-Zahlen für n = 0, 1, 2, ... sind 1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786, 208012, 742900, 2674440, 9694845, 35357670, 129644790, 477638700, 1767263190, 6564120420, 24466267020, 91482563640, 343059613650, 1289904147324, 4861946401452, ...

Weblinks

Folge A000108 in OEIS

Catalan-Zahlen Zulassungsarbeit zum Staatsexamen