Anzahl geordneter Bäume < Diskrete Mathematik < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 13:49 Mo 03.12.2007 | | Autor: | Norman |
| Aufgabe | Wieviele geordnete Bäume mit 6 Knoten gibt es?
Hinweis: Bestimmen Sie zunächst nacheinander die Anzahlen n1, ..., n5 geordneter
Bäume mit 1 bis 5 Knoten und berechnen Sie daraus n6.
|
Ich habe Progleme die Anzahl geordneter Bäume zu bestimmen.
Für die ersten 4 ist es ja nicht so schwer.
Bei 1 = 1
Bei 2 = 1
Bei 3 = 2
Bei 4 = 6
nach lagen hin und her bin ich dann auf so eine Formel gekommen, diese gilt aber nur für Binärbäume welche wir ja nicht haben: [mm] C_{n} [/mm] = [mm] \bruch{1}{1+n}* \vektor{2n \\ n} [/mm]
Damit komme ich auf 42 Bäume bei 6. Ich habe mal versucht die Bäume zu zeichnen. Das Problem ist das es bei einem Bam natürlich einen Unterschied macht ob er z.B. links 2 unterknoten hat oder rechts. Ich muss also solche fälle doppelt zählen. Ich habe mal bis 30 gezeichnet , aber das wird dann soviel das man sich sehr leicht verhasbellt.
Hat jemand eine Idee wie man die Anzahl der Bäume für 6 Knoten bestimmen könnte?
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 14:53 Mo 03.12.2007 | | Autor: | Bastiane |
Hallo Norman!
> Wieviele geordnete Bäume mit 6 Knoten gibt es?
> Hinweis: Bestimmen Sie zunächst nacheinander die Anzahlen
> n1, ..., n5 geordneter
> Bäume mit 1 bis 5 Knoten und berechnen Sie daraus n6.
Bäume kenne ich ja, aber was ist ein geordneter Baum?
Falls es dir hilft, der [mm] K_n [/mm] hat [mm] n^{n-2} [/mm] Spannbäume.
Viele Grüße
Bastiane
![[cap]](/images/smileys/cap.gif "[cap]")
|
|
|
| |
|
Hallo,
da sich deine ersten vier Werte mit meinen Überlegungen decken, nehme ich an, dass es sich nicht um sortierte Bäume wie ![[]](/images/popup.gif) hier, Seite 3 handelt, sondern um solche, die nur in den Blättern Knoten haben. Falls ja, dann kann man das Problem auch so formulieren:
Wieviele Möglichkeiten gibt es, eine Addition/Mutliplikation/was-auch-immer vollständig zu klammern?
Der Lösungsansatz wird schnell klar. Nehmen wir z.B. n=6. Dann haben wir folgende Möglichkeiten für die erste Klammer:
(1 + 2) + 3 + 4 + 5 + 6
1 + (2 + 3) + 4 + 5 + 6
1 + 2 + (3 + 4) + 5 + 6
1 + 2 + 3 + (4 + 5) + 6
1 + 2 + 3 + 4 + (5 + 6)
Leicht einzusehen, dass es genau n-1 Möglichkeiten für die erste Klammer gibt. Damit haben wir das Problem aber auch schon auf die suche nach den Klammermöglichkeiten von 5 (also n-1) Zahlen zurückgeführt, wenn wir aus die Klammer (mit den zwei Zahlen) durch eine neue Zahl ersetzen.
Also lässt sich eine rekursive Formel angeben, deren explizite Form dir auch bekannt sein wird.
Mehr sage ich nicht ;)
Gruß
Martin
|
|
|
|
