---
title: Catalanzahlen
date: 2018-10-30
---

Wir wollen 3 scheinbar verschiedene Objekte zählen:

a) Korrekte Klammerung
b) Binäre Wurzelbäume
c) Triangulierungen eines konvexen n-Ecks

## Korrekte Klammerung

Syntaktisch korrekte Klammerung mit $n$ Klammerpaaren. Die Anzahl dieser Klammerungen bezeichnen wir mit $C_n$
(Catalanzahlen).

Syntaktisch korrekt:

i) Alle Klammern müssen geschlossen werden
ii) Keine Klammer darf geschlossen werden, bevor sie geöffnet wurde

**Beispiel**:

`((()()))` ist eine korrekte Klammerung mit $n = 4$ Klammerpaaren

`())(` ist keine korrekte Klammerung


* $n = 0$ leere Klammerung

  $C_0 = 1$

* $n = 1$ `()`

  $C_1 = 1$

* $n = 2$ `()()` oder `(())`

  $C_2 = 2$

* $n = 3$ `()()()`, `()(())`, `(())()`, `((()))`, `(()())`

  $C_3 = 5$


## Binäre Wurzelbäume

Binäre Wurzelbäume mit mindestens einem Konten bestehen aus einem ausgezeichneten Knoten (Wurzel). Jeder Knoten hat
maximal 2 Kindknoten, wobei wir linken und rechten Kindknoten unterscheiden. Wir bezeichnen mit $B_n$ die Anzahl der
binären Wurzelbäume mit $n$ Knoten.

Beispiel