Die Mathe-Redaktion - 24.05.2018 19:17 - Registrieren/Login
Auswahl
ListenpunktHome
ListenpunktAktuell und Interessant ai
ListenpunktArtikelübersicht/-suche
ListenpunktAlle Links / Mathe-Links
ListenpunktFach- & Sachbücher
ListenpunktMitglieder / Karte
ListenpunktRegistrieren/Login
ListenpunktArbeitsgruppen
ListenpunktSchwätz / Top 15
ListenpunktWerde Mathe-Millionär!
ListenpunktAnmeldung MPCT Juli
ListenpunktFormeleditor fedgeo
Schwarzes Brett
Aktion im Forum
Suche
Stichwortsuche in Artikeln und Links von Matheplanet
Suchen im Forum
Suchtipps

Bücher
Englische Bücher
Software
Suchbegriffe:
Mathematik bei amazon
Naturwissenschaft & Technik
In Partnerschaft mit Amazon.de
Kontakt
Mail an Matroid
[Keine Übungsaufgaben!]
Impressum

Bitte beachten Sie unsere Nutzungsbedingungen, die Distanzierung, unsere Datenschutzerklärung und
die Forumregeln.

Sie können Mitglied werden. Mitglieder können den Matheplanet-Newsletter bestellen, der etwa alle 2 Monate erscheint.

Der Newsletter Okt. 2017

Für Mitglieder
Mathematisch für Anfänger
Wer ist Online
Aktuell sind 575 Gäste und 21 Mitglieder online.

Sie können Mitglied werden:
Klick hier.

Über Matheplanet
 
Zum letzten Themenfilter: Themenfilter:
Matroids Matheplanet Forum Index
Moderiert von viertel
Matroids Matheplanet Forum Index » Rätsel und Knobeleien (Knobelecke) » */2 Wie viele Knoten hat der Baum?
Druckversion
Druckversion
Autor
Schule J */2 Wie viele Knoten hat der Baum?
salomeMe
Senior Letzter Besuch: im letzten Monat
Dabei seit: 06.10.2015
Mitteilungen: 438
Aus: Deutschland
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Themenstart: 2018-04-26


Gegeben ist ein Baum folgender Form:

"Die Wurzel hat m Nachfolger und auf jeder Ebene sinkt die Anzahl der Nachfolger um 1. Ein Nachfolgeknoten der Wurzel hat also nur noch m-1 Nachfolger usw." (Kopiert aus dem Informatik Forum (Beitrag von 2004) in dem keine entsprechende Lösung angegeben wurde.)

Finde eine möglichst genaue Abschätzung der Anzahl der Knoten solcher Bäume für alle m > 1.

Gruß
salomeMe



  Profil  Quote  Link auf diesen Beitrag Link
Dies ist eine Knobelaufgabe!
Der Themensteller hat bestimmt, dass Du Lösungen oder Beiträge zur Lösung direkt im Forum posten darfst.
Bei dieser Aufgabe kann ein öffentlicher Austausch über Lösungen, Lösungswege und Ansätze erfolgen. Hier musst Du keine private Nachricht schreiben!
tactac
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 15.10.2014
Mitteilungen: 1205
Aus:
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.1, eingetragen 2018-04-26


Ich gehe mal davon aus, dass mit "Knoten" wirklich alle gemeint sind, also auch die Wurzel und die Blätter, sodass für m=0 der Baum einen Knoten hat, für m=1 zwei Knoten, und für m=2 fünf Knoten. Richtig?

Aber wenn das so ist: Was gibt's da abzuschätzen? Die Anzahlen sind leicht zu finden, und eine kurze exakte Formel findet sich auch.



  Profil  Quote  Link auf diesen Beitrag Link
salomeMe
Senior Letzter Besuch: im letzten Monat
Dabei seit: 06.10.2015
Mitteilungen: 438
Aus: Deutschland
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.2, vom Themenstarter, eingetragen 2018-04-26


Hallo tactac,

ja Deine Knoten-Anzahlen sind richtig. Die Aufgabe hat ja auch nur einen halben *. Die Abschätzung deshalb, weil ich Keinem zumuten möchte die Anzahl a(m) der Knoten für jedes m auszurechnen. Falls Du eine allgemeine Formel für die korrekte Anzahl für jedes m hast, wäre das natürlich noch besser und bestimmt einen ganzen Stern wert. Es gibt aber für große m eine recht genaue leicht zu findende Abschätzung, die nur aus 4 Zeichen besteht.

beste Grüße
salomeMe



  Profil  Quote  Link auf diesen Beitrag Link
Nuramon
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 23.01.2008
Mitteilungen: 279
Aus:
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.3, eingetragen 2018-04-26


Ich komme mit drei Zeichen für die Näherung aus. Wenn man dazu noch zwei Zeichen hinzufügt, bekommt man eine exakte Formel (wenn man vom Sonderfall m =0 absieht) und darauf spielt tactac vermutlich an.



  Profil  Quote  Link auf diesen Beitrag Link
MartinN
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 05.08.2016
Mitteilungen: 876
Aus: Bayern
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.4, eingetragen 2018-04-26

\(\begingroup\)
Nette Aufgabe ^^


Rekursiv:
\(a(m) = m \cdot a(m-1) + 1\)

Ergibt explizit:
\(a(m) = m! \cdot \sum_{i=0}^m \frac{1}{i!} < m! \cdot \sum_{i=0}^{\infty} \frac{1}{i!} = m! \cdot e\)

Daher schlage ich für \(m \geq 1\) vor:
\(a(m) = \lfloor m! \cdot e \rfloor\)

\(\endgroup\)


  Profil  Quote  Link auf diesen Beitrag Link
Nuramon
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 23.01.2008
Mitteilungen: 279
Aus:
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.5, eingetragen 2018-04-26 19:33

\(\begingroup\)
Ein kombinatorischer Ansatz:

Sei $M := \{1,2,\ldots, m\}$. Wir beschriften die Knoten mit endlichen Folgen aus $M$ wie folgt: Die Wurzel beschriften wir mit der leeren Folge. Ist der Knoten $K$ in der $k$-ten Generation mit der Folge $a_1,...,a_k$ beschriftet, so beschriften wir die $m-k$ Nachfolger von $K$ mit den Folgen $a_1,\ldots, a_k,x$, wobei $x\in M\setminus \{a_1,\ldots, a_k\}$.
Insgesamt entsprechen die Beschriftungen in der $k$-ten Generation damit gerade allen Folgen aus $M$ der Länge $k$ bei denen sich kein Folgenglied wiederholt. Davon gibt es bekanntlich genau $\frac{m!}{k!}$. Also hat der Baum $\sum_{k=0}^m\frac{m!}{k!} =\lfloor m! e \rfloor$ Knoten.

\(\endgroup\)


  Profil  Quote  Link auf diesen Beitrag Link
salomeMe
Senior Letzter Besuch: im letzten Monat
Dabei seit: 06.10.2015
Mitteilungen: 438
Aus: Deutschland
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.6, vom Themenstarter, eingetragen 2018-04-26 21:42

\(\begingroup\)
Die Aufgabe war wohl doch eher etwas für jüngere Schüler, wie die Einstufung unter S andeuten sollte. Trotzdem herzlichen Glückwünsche an tactac, Nuramon und MartinN sowie meinen Dank für's Miträtseln. Es müssen ja nicht immer harte Nüsse sein, die hier zum Knacken abgelegt werden. Ihr habt offensichtlich weiter gerechnet als ich - war mit dem Ergebnis der Abschätzung zufrieden, da ich ungerne rechne.

Hier mal meine "Grundschul"-Herleitung:

Die Wurzel besteht aus  \(\frac{m!}{m!}\)  Knoten.
Die i-te Ebene des Baumes besteht aus   \(\frac{m!}{(m-i)!}\)  Knoten.

Ergibt \(a(m)=\sum \limits_{i=0}^m \frac{m!}{i!} = m!\sum \limits_{i=0}^m \frac{1}{i!} < m! \cdot \sum \limits_{i=0}^\infty \frac{1}{i!} = m! \cdot e \)

Dass diese Abschätzung um weniger als 1 für alle m von den exakten Anzahlen a(m) abweichen soll, hat mich etwas überrascht:
\[\sum \limits_{i=m+1}^\infty \frac{1}{i!}< \frac{1}{m!}\]  muss dann wohl ab  \(m > 0\)  gelten.


beste Grüße
salomeMe
\(\endgroup\)


  Profil  Quote  Link auf diesen Beitrag Link
MartinN
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 05.08.2016
Mitteilungen: 876
Aus: Bayern
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.7, eingetragen 2018-04-26 22:38

\(\begingroup\)
Ich finde ja auch folgende Schlussfolgerung interessant...

\(\sum_{i=0}^{m} \frac{1}{i!} = \frac{a(m)}{m!} = \frac{\lfloor m! \cdot e \rfloor}{m!}\)

Oder auch:
\(\sum_{i=m}^{\infty} \frac{1}{i!} = e - \frac{\lfloor (m-1)! \cdot e \rfloor}{(m-1)!}\)

\(\endgroup\)


  Profil  Quote  Link auf diesen Beitrag Link
salomeMe hat die Antworten auf ihre/seine Frage gesehen.
salomeMe hat selbst das Ok-Häkchen gesetzt.
Dies ist eine Knobelaufgabe!
Der Themensteller hat bestimmt, dass Du Lösungen oder Beiträge zur Lösung direkt im Forum posten darfst.
Bei dieser Aufgabe kann ein öffentlicher Austausch über Lösungen, Lösungswege und Ansätze erfolgen. Hier musst Du keine private Nachricht schreiben!
Neues Thema [Neues Thema]  Druckversion [Druckversion]

 


Wechsel in ein anderes Forum:
 Suchen    
 
All logos and trademarks in this site are property of their respective owner. The comments are property of their posters, all the rest © 2001-2018 by Matroids Matheplanet
This web site was made with PHP-Nuke, a web portal system written in PHP. PHP-Nuke is Free Software released under the GNU/GPL license.
Ich distanziere mich von rechtswidrigen oder anstößigen Inhalten, die sich trotz aufmerksamer Prüfung hinter hier verwendeten Links verbergen mögen.
Lesen Sie die Nutzungsbedingungen, die Distanzierung, die Datenschutzerklärung und das Impressum.
[Seitenanfang]