Das Kefk Network Wiki befindet sich im Testbetrieb.

---

Aus Kefk.

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 die Catalan-Zahlen gilt für :

Wobei den Binomialkoeffizienten bezeichnet.

Eine Rekursionsformel lautet

(also z.B. C₃ = C₀C₂ + C₁C₁ + C₂C₀)

und die erzeugende Funktion ist

(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₃ = 5, denn alle möglichen Beklammerungen von x₁x₂x₃x₄ sind die folgenden:
  • (x₁x₂)(x₃x₄)
  • (x₁(x₂x₃))x₄
  • x₁((x₂x₃)x₄)
  • ((x₁x₂)x₃)x₄
  • x₁(x₂(x₃x₄))

• 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₃ = 5, denn alle möglichen Pfade sind:

Bild:5 Irrfahrten der Laenge 4.png

• C_n ist die Anzahl der möglichen Binärbäume, die sich aus n Knoten bilden lassen.

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, ...

Externe Links

Folge A000108 in OEIS