\(\begingroup\)\(\newcommand{\IX}{\mathbb{X}} \newcommand{\IW}{\mathbb{M}} \newcommand{\politician}[1]{\text{Ich habe die Frage nicht verstanden. #1}} \newcommand{\ba}{\begin{aligned}} \newcommand{\ea}{\end{aligned}} \newcommand{\bpm}{\begin{pmatrix}} \newcommand{\epm}{\end{pmatrix}} \newcommand{\bc}{\begin{cases}} \newcommand{\ec}{\end{cases}} \newcommand{\on}{\operatorname} \newcommand{\ds}{\displaystyle}\)
Die Catalan-Zahlen sind überall in der Kombinatorik anzutreffen.
Jeder Student ist erschlagen von der großen Anzahl Fragestellungen, bei denen als Lösung die Catalan-Zahlen auftauchen, und man fragt sich, ob es Bijektionen zwischen den verschiedenen von diesen Zahlen gezählten Familien von Objekten gibt.

Entdeckt (besser gesagt: erstmals als Lösung eines Problems dokumentiert) wurden die Catalan-Zahlen von Leonhard Euler. Er versuchte eine allgemeine Formel für folgendes Problem zu finden:

Bestimme die Anzahl der Dreieckszerlegungen eines konvexen (n+2)-Ecks durch n-1 sich nicht schneidende Diagonalen.

Ihren Namen haben sie nach Eugene Catalan (1814-1894), einem belgischen Mathematiker, der das Problem löste, auf wie viele Weisen man ein Wort aus n+1 Buchstaben mit n Klammernpaaren klammern kann.
Für n=3 sind dies:

(1 (2 (3 4)))
(1 ((2 3) 4))
((1 2) (3 4))
((1 (2 3)) 4)
(((1 2) 3) 4)

Anzahl der Anordnungen von n+1 Seifenblasen?
Für n=3 zeigt das Bild oben mögliche Anordnungen.

Weitere Beispiele

Gitterwege von (0,0) nach (n,n) mit Schritten in positiver Richtung?

Anders verpackt lautet die Aufgabe: Auf einem nxn Schachbrett soll ein Turm von links unten nach rechts oben bewegt werden, so daß der Weg nicht oberhalb der Hauptdiagonalen des Schachbretts verläuft.

Stapel von Münzen in der Ebene mit n Münzen als Basis?

n-elementige Teilmengen von Z/(n+1)Z, deren Elemente die Summe 0 ergeben?

Für n=3 sind das 000 013 022 112 233

Bezeichnung, Tabelle, Verweise

Einige Werte zeigt die Tabelle:

n	Cn
0	1
1	1
2	2
3	5
4	14
5	42
6	132
7	429
8	1430

66 Beispiele gibt Richard P. Stanley

Einige der gezeigten Beispiele sind dem Buch von Stanley entnommen. Siehe dazu Catalan Numbers. Stanley beweist gelegentlich auch Humor, etwa mit der Frage:

"Explain the following sequence:
    un, dos, tres, quatre, cinc, sis, ..."

Charakteristische Eigenschaft

C_n = Σⁿ_i=1 C_i-1 * C_n-i

So kann man auf dem nxn Schachbrett jeden nicht über der Diagonalen von unten links nach oben rechts verlaufenden Turmweg zerlegen in einen Turmweg von (0,0) nach (i,i) und einen von (i,i) nach (n,n), für ein i > 0. Darum kann man die Turmwege disjunkt aufteilen in solche, die bei (i,i) erstmals die Hauptdiagonale berühren. Für gegebenes i > 0 ist deren Anzahl gleich C_i-1*C_n-i. Die Anzahl aller Turmwege ist dann die Summe über i der Turmwege, die bei (i,i) die Hauptdiagonale erstmals betreten.
[Anm.: Diesen Typ der Rekursion bezeichnet man mit dem Begriff convolution (dt.: Faltung).]

Wenn für ein anderes Problem die gleiche Rekursion gilt und die Anfangswerte übereinstimmen, dann hat man gezeigt, daß auch dieses Problem durch die Catalan-Zahlen gelöst wird.

Matroid 2002