TU Wien:Algebra und Diskrete Mathematik VU (diverse)/Übungen 2025W/Beispiel 210

$C_n$ bezeichne die $n$-te Catalan-Zahl. Zeigen Sie: Es gibt genau $C_{n-2}$ Möglichkeiten, ein konvexes $n$-Eck durch Diagonalen in lauter Dreiecke zu zerlegen, wenn keine zwei Diagonalen einander überschneiden dürfen.

Hinweis: Man zeige, dass die gesuchte Zahlenfolge und die Folge der Catalanzahlen dieselbe Rekursion erfüllen.

Dieses Beispiel ist als partial markiert. Ist dies falsch oder ungenau? Aktualisiere den Lösungsstatus (Details: Vorlage:Beispiel)

Hilfreiches

Catalan Zahlen

Für $n\in \mathbb{N}$ ist die $n$-te $Catalan$ $Zahl$ definiert als
$C_n:=\left(\begin{array}{c}2n\\ n\end{array}\right)-\left(\begin{array}{c}2n\\ n+1\end{array}\right)=\frac{1}{n+1}\left(\begin{array}{c}2n\\ n\end{array}\right)$
Die Folge $(C_n{)}_{n\ge 0}$ der $Catalan$ $Zahlen$ beginnt mit
$(1,1,2,5,14,42,132,429,1430,\mathrm{...})$

Lösung

$f(n)$ Anzahl der Triangulierungen eines $n$-Ecks. Wird das $n$-Eck nun Trianguliert, entstehen 2 neue Vielecke. Ein $k$-Eck und ein $(n-k+1)$-Eck.
Dies ergibt für $n\ge 3$ folgende Rekursion:
$f(n)=\sum _{k=2}^{n-1}f(k)f(n-k+1)$
Nun definieren wir Anfangswerte für die Funktion $f(4)=2,f(2)=f(3)=1$. Durch errechnen der ersten Folgeglieder der Folge $(f(n+2){)}_{n\ge 0}$
$(1,1,2,5,14,42,132,429,1430,\mathrm{...})$
kann man vermuten, dass $f(n+2)=C_n$.

Dies muss man noch beweisen.

Links

• Johannes Kepler Universität Linz - Endliche Kombinatorik - Friedrich Pillichshammer - Vorlesung im WS 2011/12 - Seite 52-55 [1]