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

$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{matrix}2n\\n\end{matrix}}\right)-\left({\begin{matrix}2n\\n+1\end{matrix}}\right)={\frac {1}{n+1}}\left({\begin{matrix}2n\\n\end{matrix}}\right)$
Die Folge $(C_{n})_{n\geq 0}$ der $Catalan$ $Zahlen$ beginnt mit
$(1,1,2,5,14,42,132,429,1430,...)$

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\geq 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\geq 0}$
$(1,1,2,5,14,42,132,429,1430,...)$
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]