Ferienakademie 1999
Kurs 2: Bäume - Algorithmik und Kombinatorik

Frank Strüber
Frank Strüber
Algebraischer Beweis der Cayley-Formel

Die Cayleyformel zählt die Anzahl der ungewurzelten Bäume auf einer Menge von n unterscheidbaren Elementen. Mein erstes Kurzreferat stellt zwei Zugänge zu dieser Formel vor. Es wird mit algebraischen Hilfsmitteln ein Beweis derselben erbracht und das Matrix-Tree-Theorem an einem Beispiel veranschaulicht sowie ausgehend von ihm die Cayleyformel bewiesen.

Frank Strüber
Frank Strüber
Dyckwörter und Bäume Dyckwörter und Bäume

Mein zweites Kurzreferat beschäftigt sich mit drei Familien von Objekten (Dyckwörter der Länge 2n, ebene Bäume mit n+1 Knoten, Objekten (Dyckwörter der Länge 2n, ebene Bäume mit n+1 Knoten, vollständige binäre Bäume mit n inneren Knoten) , die von den Catalanzahlen (die Folge 1, 1, 2, 5, 14, ...) gezählt werden. Für alle Catalanzahlen (die Folge 1, 1, 2, 5, 14, ...) gezählt werden. Für alle drei Objektfamilien wird aus der jeweiligen rekursiven Definition analytisch eine Funktionalgleichung ihrer erzeugenden Funktion hergeleitet, aus deren Gleichheit anschließend auf die Gleichmächtigkeit der entsprechenden Mengen geschlossen wird. Ebenso werden an Beispielen durch geeignete Codierungen Bijektionen zwischen je zwei der drei Objektfamilien erläutert, die gleichfalls die Gleichmächtigkeit der Mengen der Dyckwörter der Länge 2n, der ebenen Gleichmächtigkeit der Mengen der Dyckwörter der Länge 2n, der ebenen Bäume mit n+1 Knoten und der vollständigen binären Bäume mit n Knoten belegen.