Catalan-Zahlen

Die Catalan-Zahlen sind eine Folge natürlicher Zahlen, die in vielen Problemen der Kombinatorik auftreten. Sie wurden nach dem belgischen Mathematiker Eugène Catalan (1814 – 1894) benannt,  der sich intensiv mit diesen Zahlen beschäftigte.
Die Catalan-Zahlen werden mit C0, C1, C2, C3, … bezeichnet und lauten:

1 , 1, 2, 5, 14, 42, 132, 429, 1430, 4862, …

Leonhard Euler (1707 – 1783) fand die Anzahl der Möglichkeiten heraus, ein konvexes n-Eck durch Diagonalen in Dreiecke  zu unterteilen (Triangulation). Diese Anzahl ist Cn-2.
Zum Beispiel gibt es für ein Viereck 2, für ein Fünfeck 5 und für ein Sechseck 14 mögliche Triangulationen:

Euler hat dafür folgende allgemeine Formel für n 1 aufgestellt:

Allgemein lässt sich Cn für n 0 auch folgendermaßen darstellen:

z.B.   


TigerJython-Programm
zur Berechnung der Catalan-Zahlen

# catalan-zahl

 

def nfak(n):

  i=1; fak=1

  repeat n:

    fak=fak*i

    i=i+1

  return fak

                

for i in range(10):

  catalan_zahl = nfak(2*i)/(nfak(i)*nfak(i+1))

  print("%2i," % (catalan_zahl)),

print("...")

 

1 , 1, 2, 5, 14, 42, 132, 429, 1430, 4862, …


Weitere Beispiele:

Pfade entlang eines nxn-Gitters, die nicht oberhalb der Diagonale  [AC] verlaufen.

2x2 Gitter: 2 verschiedene Pfade

3x3 Gitter: 5 verschiedene Pfade

4x4 Gitter: 14 verschiedene Pfade


Anzahl der Möglichkeiten eine Stufenform der Breite und Höhe n mit n Rechtecken zu kacheln

Breite und Höhe 2:  2 mal 2 Rechtecke

Breite und Höhe 3:  5 mal 3 Rechtecke

Breite und Höhe 4:  14 mal 4 Rechtecke

Anzahl von Klammerpaaren

2 Klammerpaare: 2 Möglichkeiten

(()), ()()

3 Klammerpaare: 5 Möglichkeiten

((())), (()()), (())(), ()(()), ()()()

4 Klammerpaare: 14 Möglichkeiten

(((()))), (())()(), ()(())(), ()()(()), (())(()), ()((())),((()))(),

(()(())), ((())()), (()())(), ((()())), ()(()()),(()()()), ()()()()

 


Zurück
Zurück zur Startseite