TU Wien:Algebra und Diskrete Mathematik UE (diverse)/Übungen SS19/Beispiel 203

Aus VoWi
Wechseln zu: Navigation, Suche

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.

Hilfreiches[Bearbeiten]

Catalan Zahlen[Bearbeiten]

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[Bearbeiten]

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[Bearbeiten]

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