|
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.
|