TU Wien:Algebra und Diskrete Mathematik VU (diverse)/Übungen 2023W/Beispiel 208
Zur Navigation springen
Zur Suche springen
bezeichne die -te Catalan-Zahl. Zeigen Sie: Es gibt genau Möglichkeiten, ein konvexes -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[Bearbeiten | Quelltext bearbeiten]
Catalan Zahlen[Bearbeiten | Quelltext bearbeiten]
Für ist die -te definiert als
Die Folge der beginnt mit
Lösung[Bearbeiten | Quelltext bearbeiten]
Anzahl der Triangulierungen eines -Ecks. Wird das -Eck nun Trianguliert, entstehen 2 neue Vielecke. Ein -Eck und ein -Eck.
Dies ergibt für folgende Rekursion:
Nun definieren wir Anfangswerte für die Funktion . Durch errechnen der ersten Folgeglieder der Folge
kann man vermuten, dass .
Dies muss man noch beweisen.
Links[Bearbeiten | Quelltext bearbeiten]
- Johannes Kepler Universität Linz - Endliche Kombinatorik - Friedrich Pillichshammer - Vorlesung im WS 2011/12 - Seite 52-55 [1]