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

Aus VoWi
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]