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

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}$.)

Dieses Beispiel hat einen unbekannten Lösungsstatus. Bitte editiere diese Seite und schreibe den dir bekannten Status ins Beispiel. Die möglichen Werte sind hier: Vorlage:Beispiel dokumentiert. Führe folgende Änderung durch:

{{Beispiel|1=
Angabetext
}}

oder

{{Beispiel|
Angabetext
}}

zu (im Falle einer korrekten, unverifizierten Lösung "solved". Auch möglich "unsolved", "wrong", "verified_by_tutor". Alle möglichen Werte sind hier: Vorlage:Beispiel dokumentiert.)

{{Beispiel|status=solved|1=
Angabetext
}}

Lösungsvorschlag von Ryus

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.