53 lines
1.1 KiB
Markdown
53 lines
1.1 KiB
Markdown
|
---
|
||
|
|
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
|