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

From VoWi
< TU Wien:Algebra und Diskrete Mathematik UE (diverse)‎ | Übungen SS19
Revision as of 16:58, 7 March 2019 by Gittenborg (talk | contribs) (Gittenborg verschob die Seite TU Wien:Algebra und Diskrete Mathematik UE (diverse)/Übungen WS18/Beispiel 313 nach TU Wien:Algebra und Diskrete Mathematik UE (diverse)/Übungen SS19/Beispiel 313 und überschrieb dabei eine Weiterleitung: versch…)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to navigation Jump to search

Man zeige, dass für n \geq 1 die Anzahl aller (geordneten) vollen Binärbaume mit n+1 Blättern gleich der n-ten Catalan-Zahl C_{n} ist. (Hinweis: Man verwende die Rekursionsformel ("divide and conquer") für C_{n}.)

Lösungsvorschlag von Ryus[edit]

Die Rekursionsformel der Catalan-Zahlen lautet:

C_{n} = \sum_{k=0}^{n} C_{k}C_{n-k} \quad (C_{0}=1)

Zu zeigen ist, dass

I_{n+1} = C_{n} \quad (n \geq 1)

Wobei I_{n+1} die Anzahl aller Binärbaume mit n+1 Blättern ist. Ein Binärbaum ist ein Baum, bei dem jeder Knoten entweder 0 Nachfolger oder 2 Nachfolger besitzt. Blätter sind die Endknoten, also jene, die keinen Nachfolger haben.

Um die Gültigkeit zu zeigen, wird folgender Induktionsbeweis benutzt. Zunächst betrachten wir n=0: In diesem Fall hat unser Binärbaum 1 Blatt. Dies kann nur der Fall sein, wenn die Wurzel der einzige Knoten und damit auch das Blatt ist. In diesem Fall ist die Anzahl der möglichen Bäume genau 1, was der 0ten Catalan-Zahl entspricht.

Man kann sich das Ganze auch noch für n=1 anschauen. In diesem Fall hat der Baum 2 Blätter. Dies ist auch nur in einem Fall möglich (Von der Wurzel gehen die beiden Blätter weg) und entspricht somit auch der 1. Catalan-Zahl.

Nun müssen wir zeigen, dass wenn es für alle Vorgänger von n+1 gilt, dass es dann auch für n+1 selbst gilt. Dazu betrachtet man die Wurzel, von welcher sicher zwei Kanten weggehen. Links und rechts entspringt nun jeweils wieder ein neuer Teilbaum. Wir teilen nun unsere n+1 Blätter auf diese beiden Teilbäume auf. Beispielsweise könnte der linke Baum n Blätter und der rechte 1 Blatt haben, oder der linke n-1 Blätter und der rechte 2, ..., oder der linke 1 Blatt und der rechte n. Es kann nicht sein, dass einer der Teilbäume keine Blätter enthält (sonst wärs ja kein Baum). Für alle Bäume mit n oder weniger Blättern wissen wir aber bereits, dass die Anzahl ihrer Möglichkeiten der jeweiligen Catalan-Zahl entspricht.

Wir können also folgende Formel für die Anzahl der Binärbaume mit n+1 Blättern I_{n+1} aufstellen:

I_{n+1} = \sum_{k=0}^{n} C_{k}C_{n-k} = C_{n}

Und damit ist die Aussage bewiesen.