Moin.. ich habe ein kombinatorisches Problem:
Die Zahlen 1 bis 15 sollen in einen Suchbaum einsortiert werden, sodass er perfekt balanciert ist. Am Ende wird dann das rauskommen, was ich hier grafisch angehängt habe. Das schwierige ist aber, dass ich bestimmen soll, wie viele Möglichkeiten es gibt, diesen Baum zu befüllen.
Mein erster Ansatz war, dass ich den Baum einfach mal befülle, und mir nach jedem Element notiere, wie viele Möglichkeiten ich genau jetzt hätte. Das Problem dabei ist, dass wenn ich dann den Baum anders befülle, auch andere Werte rauskommen.
Füllt man ihn streng von links nach rechts (also 8 - 4 - 2 - 1 - 3 - 6 - 5 - 7 - 12 - 10 - 9 - 11 - 14 - 13 - 15) kommt man so auf ca 20.000 Möglichkeiten, füllt man ihn von oben nach unten (also 8 - 4 - 12 - 2 - 6 - 10 - 14 - 1 - 3 - 5 - 9 - 11 - 13 - 15) sind es ca 600 Millionen.
Also habe ich einen anderen Ansatz verfolgt, und zwar für jeden Wert zu schauen, wie viele Möglichkeiten es insgesamt gibt, diesen Wert zu setzen.. die 8 muss z.B. am Anfang gesetzt werden, also dafür nur 1 möglichkeit. Die 4 muss nach der 8 und vor der (2,1,3,6,5,7) gesetzt werden, also 8 Möglichkeiten usw.. da kommt aber insgesamt ca 4 * 10^14 raus.. und ich glaube auch das scheint falsch, denn es müsste ja eigentlich von der Idee her Ziehen ohne zurücklegen mit Reihenfolge sein, also irgendwas mit Fakultät, aber ich sehe nicht, wie ich das hier einbauen könnte.. weiß jemand Rat?
Danke für den Tipp, ich hab mal alle Möglichkeiten für 7 Einträge ausprobiert (es sind 80), finde dafür aber keine direkte Formel.. jedenfalls noch nicht, ich werd weiter rumprobieren ;)
so, dank deinem tipp habe ich mal für alle 0 bis 10 elementigen bäume die werte durch ein skript berechnen lassen.. und die zahlenfolge die da rauskam hab ich dann gegooglet^^
raus kam das hier: http://mathworld.wolfram.com/Heap.html
jetzt muss ich nur noch schauen, wieso die formel auch bei meinem problem anwendbar ist, aber.. es macht zumindest sinn :)