Bäume mit Blätter berechnen < Kombinatorik < Stochastik < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 01:21 Di 06.05.2014 | | Autor: | Max80 |
| Aufgabe | <br>
Ein Baum heißt q-exakt, wenn jeder innere Knoten genau q Söhne hat. Zweige, dass es genau dann einen q-exakten Baum mit b Blättern gibt, wenn q-1 ein Teiler von b-1 ist. |
<br>
Hallo zusammen,
ich habe das also mal ausprobiert. Im Prinzip stimmt das ja: Habe ich z.B. immer 2 Söhne, dann ist die Anzahl der Blätter 2^Anzahl der Ebenen unter der Wurzel. Also bei drei ebenen (Wurzel, 2 Söhne und dann diese wieder jeweils 2 Söhne und diese jeweils wieder 2 Söhne) wäre das [mm] 2^3 [/mm] = 8 Blätter. Nun sage ich q-1 = 1 und b-1 = 7 => geht. Keine Kunst bei 1 einen Teiler zu finden. Anderes Beispiel:
Immer 4 Söhne: Bei zwei Ebenen unter der Wurzel [mm] 4^2 [/mm] = 16. q-1 = 3 und b-1 = 15 => geht wieder, weil 15/3 geht.
Also es funktioniert. Aber ich frage mich wie ich das beweisen kann. Das einzige was mir jetzt spontan einfällt ist vollständige Induktion. Aber da weiß ich leider keinen Ansatz. Wäre das denn der richtige Weg und wenn ja hätte jemand vielleicht eine Idee für einen Ansatz? :)
Danke!!
Gruß
Max
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 03:14 Di 06.05.2014 | | Autor: | Teufel |
Hi!
Es gilt: Ein $q$-exakter Baum mit $n$ Knoten hat $(n-1)(q-1)+1$ Blätter. Das kannst du mit Induktion nach $n$ beweisen.
Die andere Richtung: Es gelte q-1|b-1, also b=(q-1)k+1 für irgendein [mm] $k\in\IZ$. [/mm] Kannst du einen Baum hinschreiben, der $q$-exakt ist und $(q-1)k+1$ Blätter hat?
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 18:17 Di 06.05.2014 | | Autor: | Max80 |
<br>
Also ich war mir auch schon relativ sicher, dass es ein vollständiges Induktion Problem ist. Leider hab ich keine Ahnung wie da jetzt die Voraussetzung aussehen soll. Man braucht ja immer eine Voraussetzung.
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 22:35 Di 06.05.2014 | | Autor: | Teufel |
Hi!
Sorry, was ich letztens geschrieben habe, ist so nicht richtig. Meine Aussage bezieht sich auf innere Knoten und sollte so lauten:
Ein Baum mit $n$ inneren Knoten hat $n(q-1)+1$ Blätter.
Fall n=0 (nur Wurzel ist vorhanden, die dann aber ein Blatt ist): Klar, 0(q-1)+1=1 Blatt. Passt.
Jetzt nimm dir einen Baum mit $n+1$ inneren Knoten. Entfernst du die Wurzel, dann bekommst du $q$ $q$-exakte Bäume! Der erste habe [mm] n_1 [/mm] innere Knoten, der zweite [mm] n_2, [/mm] ..., der $q$-te [mm] $n_q$. [/mm] Dann gilt [mm] $n_1+\ldots+n_q=n$.
[/mm]
Nun wende die Induktionsvoraussetzung auf die $q$ kleineren Bäume an und nutze aus, dass die Anzahl der Blätter des großen Baumes die SUmme der Anzahl der Blätter der kleinen $q$ Bäumen ist.
|
|
|
|
