Leiten Sie fur n ∈ IN0 formal die Anzahl bn der Binarbäume mit genau n Knoten, wobei unter ”Knoten“ sowohl innere Knoten als auch Blätter zu verstehen sind.
Wie viele binäre Bäume könntest du für 1, 2, 3, 4, 5 Knoten skizzieren. Skizziere dann mal die Bäume für 5 Knoten. Kann man daraus jetzt ein Modell für n Knoten entwickeln?
Hier ein Ansatz für dich:
Es sei t(n) die Anzahl binärer Bäume die n Knoten haben. Dann gilt sicher.t(0) = 1t(1) = 1t(2) = t(0)·t(1) + t(1)·t(0) = ...t(3) = t(0)·t(2) + t(1)·t(1) + t(2)·t(0) = ...t(4) = t(0)·t(3) + t(1)·t(2) + t(2)·t(1) + t(3)·t(0) = ...t(5) = t(0)·t(4) + t(1)·t(3) + t(2)·t(2) + t(3)·t(1) + t(4)·t(0) = ...Daraus lässt sich dann folgende explizite Formel entwickeln.t(n) = (2·n)!/((n + 1)!·n!)
Es sei t(n) die Anzahl binärer Bäume die n Knoten haben. Dann gilt sicher.
t(0) = 1
t(1) = 1
t(2) = t(0)·t(1) + t(1)·t(0) = ...
t(3) = t(0)·t(2) + t(1)·t(1) + t(2)·t(0) = ...
t(4) = t(0)·t(3) + t(1)·t(2) + t(2)·t(1) + t(3)·t(0) = ...
t(5) = t(0)·t(4) + t(1)·t(3) + t(2)·t(2) + t(3)·t(1) + t(4)·t(0) = ...
Daraus lässt sich dann folgende explizite Formel entwickeln.
t(n) = (2·n)!/((n + 1)!·n!)
Ein anderes Problem?
Willkommen bei der Mathelounge! Stell deine Frage einfach und kostenlos
