Satz - Zahl korrekter Klammerausdrücke

Sei $n \geq 0$ .

Für die Anzahl $C_{n}$ der syntaktisch korrekten Klammerausdrücke mit $n$ Klammerpaaren gilt:

C_{0} = 1

und für $n \geq 1$

C_{n} = \sum_{k = 1}^{n} C_{k - 1} C_{n - k} .

Beweis per Induktion über $n$ .

Für $n = 0$ gilt die Aussage offensichtlich.

Angenommen, die Aussage gilt für alle $i < n$ .

Ein korrekter Klammerausdruck mit $n$ Paaren beginnt mit "(".

Diese wird an einer geraden Position $2 k$ geschlossen.

Der Ausdruck hat also die Form:

(K) S

Dabei ist:

Sei $A_{k}$ die Menge der Klammerausdrücke, deren erste Klammer an Position $2 k$ geschlossen wird.

Dann gilt:

A_{i} \cap A_{j} = \emptyset für i \neq j .

In $A_{k}$ gibt es:

Also:

| A_{k} | = C_{k - 1} C_{n - k} .

Damit:

C_{n} = | ⋃_{k = 1}^{n} A_{k} | = \sum_{k = 1}^{n} | A_{k} | = \sum_{k = 1}^{n} C_{k - 1} C_{n - k} .