- Catalanzahl
-
Die Catalan-Zahlen oder catalanschen Zahlen, benannt nach dem belgischen Mathematiker Eugène Charles Catalan (1814–1894), sind eine Folge natürlicher Zahlen, die in vielen Problemen der Kombinatorik auftaucht. Die n-te Catalan-Zahl Cn 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 beginnend mit C0 sind
Für die Catalan-Zahlen gilt für :
wobei den Binomialkoeffizienten bezeichnet.
Eine Rekursionsformel lautet(also z. B. C3 = C0C2 + C1C1 + C2C0)
und die erzeugende Funktion ist.
Weitere Interpretation für die Catalan-Zahlen
- Cn + 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 C3 = 5, denn alle möglichen Beklammerungen von x1x2x3x4 sind die folgenden:
- (x1x2)(x3x4)
- (x1(x2x3))x4
- x1((x2x3)x4)
- ((x1x2)x3)x4
- x1(x2(x3x4))
- Cn 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 C3 = 5, denn alle möglichen Pfade sind:
- Cn 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.
Weblinks
- Cn + 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 C3 = 5, denn alle möglichen Beklammerungen von x1x2x3x4 sind die folgenden:
Wikimedia Foundation.