Disclaimer: Dieser Thread wurde aus dem alten Forum importiert. Daher werden eventuell nicht alle Formatierungen richtig angezeigt. Der ursprüngliche Thread beginnt im zweiten Post dieses Threads.
Binärbaumpermutationen
Aufgabe 15-2) sagt doch, dass die Anzahl der Permutationen für einen Binärbaum n! durch das Multiplikationsprodukt der Anzahl der inneren Knoten der Teilbäume ist (Formel siehe Aufgabe).
Aber bei mir funktioniert das nicht.
Man nehme einen Baum mit 2 inneren Knoten, dafür gibt es doch 2 Permutationen:
O
/ \
O -
/ \
O
/ \
- O
/
- -
Aber die Formel wäre dann doch 2!/(1*2) = 1???
Irgendwas stimmt hier nicht…
Die Formel berechnet dir die Anzahl an Permutationen mit n Elementen die zu dem selben Baum führt. Also bei 2 Elementen zum bsp (1,2) oder (2,1) gibts genau 1 Permutation für jeden Baum. Damit passt doch alles.
1
/ \
3 -
/ \
3
/ \
- 1
/
- -
Das ist dann aber nicht der selbe Baum (keine Permutation), oder?
Das ist nicht der selbe Baum, aber es sind ja auch 2 verschiedene Permutationen. erst ab n=3 gibt es mehrere Permutationen mit dem selben Baum.