Die Mathe-Redaktion - 17.10.2019 12:55 - Registrieren/Login
Auswahl
ListenpunktHome
ListenpunktAktuell und Interessant ai
ListenpunktArtikelübersicht/-suche
ListenpunktAlle Links / Mathe-Links
ListenpunktFach- & Sachbücher
ListenpunktMitglieder / Karte / Top 15
ListenpunktRegistrieren/Login
ListenpunktArbeitsgruppen
Listenpunkt? im neuen Schwätz
ListenpunktWerde Mathe-Millionär!
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 699 Gäste und 17 Mitglieder online.

Sie können Mitglied werden:
Klick hier.

Über Matheplanet
 
Zum letzten Themenfilter: Themenfilter:
Matroids Matheplanet Forum Index
Moderiert von matroid
Kombinatorik & Graphentheorie » Graphentheorie » Ebene/markierte Wurzelbäume, Komposition, Operatormethode
Druckversion
Druckversion
Antworten
Antworten
Autor
Universität/Hochschule Ebene/markierte Wurzelbäume, Komposition, Operatormethode
Newmath2012
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 26.09.2013
Mitteilungen: 363
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Themenstart: 2019-09-17


Hallo!
Ich beschäftige mich derzeit wieder mit Kombinatorik und habe drei Beispiele gefunden, bei denen mir der Plan fehlt bzw. ich mir nicht sicher bin, welches Vorgehen richtig ist:

1) Ebene Wurzelbäume der Art wie auf Foto 1.


Meine Idee: \(\mathcal{A}\) lässt sich beschreiben mittels:
\(\mathcal{A} = \{O\} + \{O\}\times \{O\} \times \{O\} \times \mathcal{A}^2\)
Stimmt das? Dann übersetze ich diese Glg in \(A(z) = z + z^3 \cdot A^2(z)\) und erhalte als Lösung für \(a_n\), also die Anzahl solcher ebener Wurzelbäume der Größe n:
\(a_n = \binom{\frac{1}{2}}{\frac{n+3}{4}} \cdot (-4)^{\frac{n+3}{4}} \cdot (-\frac{1}{2})\) für (n+3) mod 4 = 0 und 0 sonst.
Stimmt das so?
Ich hatte dann noch eine andere Idee, nämlich, dass sich diese speziellen Wurzelbäume aus den normalen Binärbäumen, bei denen nicht zwischen int. und ext. Knoten entschieden wird, bilden lässt, indem man jeden Knoten entweder so lässt oder durch eine Kette von 3 Knoten ersetzt. Damit komme ich dann aber auf was anderes:
\(\mathcal{A} = \mathcal{B}(\mathcal{C})\), wobei B für die Menge der Binärbäume steht und C für die Menge aus dem einzelnen Knoten und der Kette von 3 Knoten.
Das ergibt dann aber die Glg. \(A(z) = \frac{1-\sqrt{1-4(z+z^3)^2}}{2(z+z^3)}\)
Welcher der beiden Ansätze stimmt denn nun (wenn überhaupt einer richtig ist) und warum der andere nicht?

2) Gerade markierte Wurzelbäume wie auf Foto 2
.
Gesucht ist wieder die Darstellung von \(\mathcal{T}\) mittels der Operatoren (so wie ich es schon in 1) geschrieben habe) und dann \(T_n\). Ich habe leider keine Idee dazu, weil ich das mit den markierten Objekten überhaupt nicht verstanden haben. (Also auch nicht intutitiv, was das sein soll...)

3) Anzahl der Kompositionen einer nat. Zahl mit ungeraden Summanden.
Meine Idee:
\(\mathcal{K} = \{1,3,5,7,9,...\}^{\ast}\)
Daher: \(P(z) = \frac{1}{1-(z+z^3+z^5+...)} = \sum_{j \geq 0}(\sum_{k=1, k ungerade}^n z^k)^j \)
Da schaffe ich es aber nicht, den Koeffizienten von \(z^n\) abzulesen...???

Wäre echt toll, wenn mir jemande helfen könnte! (Auch, falls nur bei einem der Beispiele.)



  Profil  Quote  Link auf diesen Beitrag Link
Newmath2012
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 26.09.2013
Mitteilungen: 363
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.1, vom Themenstarter, eingetragen 2019-09-18


Weiß hier niemand Rat?



  Profil  Quote  Link auf diesen Beitrag Link
StrgAltEntf
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 19.01.2013
Mitteilungen: 5168
Aus: Milchstraße
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.2, eingetragen 2019-09-18


Hallo Newsmath,

dieses Konzept ist mir völlig unbekannt. Hast du vielleicht einen Link, wo das alles erklärt wird, angefangen bei den Schreibweisen?



  Profil  Quote  Link auf diesen Beitrag Link
Newmath2012
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 26.09.2013
Mitteilungen: 363
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.3, vom Themenstarter, eingetragen 2019-09-19


Hallo StrgAltEntf, vielen Dank für deine Teilnahme an dem Thread! :)
Ich habe hier ein pdf gefunden, wo genau das System von der Idee her erklärt ist, nur die Notation scheint minimal von der abzuweichen, die ich gewohnt bin:
info.tuwien.ac.at/panholzer/DM_Skriptum_V1.pdf
Würde mich wirklich freuen, wenn du mir damit weiterhelfen könntest! :)



  Profil  Quote  Link auf diesen Beitrag Link
Kitaktus
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 11.09.2008
Mitteilungen: 6049
Aus: Niedersachsen
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.4, eingetragen 2019-09-19


Zu 1)

Beim Vergleich mit den Binärbäumen, hast Du da berücksichtigt, dass Du die Blätter eines Binärbaumes nicht durch drei Knoten ersetzen kannst? Das geht nur bei inneren Knoten.



  Profil  Quote  Link auf diesen Beitrag Link
Newmath2012
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 26.09.2013
Mitteilungen: 363
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.5, vom Themenstarter, eingetragen 2019-09-19 14:38


Hallo Kitaktus,
du meinst jetzt die Variante mit \(\mathcal{A} = \mathcal{B}(\mathcal{C})\) oder? Da habe ich jene Binärbäume genommen, bei denen nicht zwischen internen und externen Knoten entschieden wird, also auch die "externen" Knoten Gewicht 1 haben. Dann müsste das mit dem Ersetzen doch eigentlich gehen, nicht?



  Profil  Quote  Link auf diesen Beitrag Link
Kitaktus
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 11.09.2008
Mitteilungen: 6049
Aus: Niedersachsen
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.6, eingetragen 2019-09-19 16:39


Was die Schreibweise A=B(C) aussagen soll, weiß ich nicht.

So, wie ich es verstehe, ist es in B(C) zulässig das Blatt eines gewöhnlichen Binärbaums durch drei aneinandergehängte Knoten zu ersetzen.
Solche Bäume kommen in A aber nicht vor.



  Profil  Quote  Link auf diesen Beitrag Link
Newmath2012
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 26.09.2013
Mitteilungen: 363
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.7, vom Themenstarter, eingetragen 2019-09-19 16:57


Hi Kitaktus, das ist richtig.
Wieso kommen solche Bäume aber in A nicht vor? Wir suchen doch genau die Bäume, die entweder ein einzelner Knoten sind oder eine Kette von 3 Knoten mit 2 solchen Bäumen dran?



  Profil  Quote  Link auf diesen Beitrag Link
Kitaktus
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 11.09.2008
Mitteilungen: 6049
Aus: Niedersachsen
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.8, eingetragen 2019-09-19 17:47


Ja genau. dabei können aber drei aufeinanderfolgende Knoten nur _im Inneren_ des Baumes auftreten, aber nicht an den Blättern.



  Profil  Quote  Link auf diesen Beitrag Link
StrgAltEntf
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 19.01.2013
Mitteilungen: 5168
Aus: Milchstraße
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.9, eingetragen 2019-09-19 22:05


Hallo Newmath2012,

vielen Dank für den Link! Nach erster Sichtung sieht das sehr interessant aus. Mal sehen, ob ich dazu komme, mir das intensiver anzuschauen smile

Zu 3: Der Term P(z) lässt sich vereinfachen zu \(P(z)=1+\frac z{1-z-z^2}\). Weitere Tipps habe ich momentan aber nicht.



  Profil  Quote  Link auf diesen Beitrag Link
Newmath2012
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 26.09.2013
Mitteilungen: 363
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.10, vom Themenstarter, eingetragen 2019-09-20 00:53


@Kitaktus: Danke für die Erklärung, aber ich stehe leider immer noch auf dem Schlauch. Könntest du das vielleicht noch näher ausführen? Mir ist nämlich nicht ganz klar, was du meinst, wo genau der Haken ist?

@StrgAltEntf: Sehr gerne! Die Methode findest du übrigens auch in diesem Buch: algo.inria.fr/flajolet/Publications/book.pdf Das ist halt sogar noch viel ausführlicher. ^^
Keinen Stress, ich bleibe auf jeden Fall an der Antwort auf meine Frage interessiert und falls du dazu kommst, dich damit auseinanderzusetzen, würde mich das sehr freuen. :)
Danke auch für den Umformungstipp, ich werde schauen, was ich damit anstellen kann.



  Profil  Quote  Link auf diesen Beitrag Link
Kitaktus
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 11.09.2008
Mitteilungen: 6049
Aus: Niedersachsen
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.11, eingetragen 2019-09-20 08:15


2019-09-20 00:53 - Newmath2012 in Beitrag No. 10 schreibt:
@Kitaktus: Danke für die Erklärung, aber ich stehe leider immer noch auf dem Schlauch. Könntest du das vielleicht noch näher ausführen? Mir ist nämlich nicht ganz klar, was du meinst, wo genau der Haken ist?
Letzter Versuch:
So, wie ich es verstehe, sind solche Graphen sind in B(C) zugelassen, in A aber nicht.
    O
   / \
  O   O
  |   |
  O   O
  |   |
  O   O



  Profil  Quote  Link auf diesen Beitrag Link
Newmath2012
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 26.09.2013
Mitteilungen: 363
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.12, vom Themenstarter, eingetragen 2019-09-20 14:38


Hallo Kitaktus, danke für dein Bemühen! :)
Ja, ich würde auch sagen, dass sie in B(C) zugelassen sind.
Und habe mir nun Gedanken gemacht, warum nicht in A:
Weil die in A alle mit einem Einzelknoten und nicht mit einer Dreierkette von Knoten enden.
Ist das auch dein Eindruck?



  Profil  Quote  Link auf diesen Beitrag Link
StrgAltEntf
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 19.01.2013
Mitteilungen: 5168
Aus: Milchstraße
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.13, eingetragen 2019-09-20 18:49


2019-09-20 14:38 - Newmath2012 in Beitrag No. 12 schreibt:
Weil die in A alle mit einem Einzelknoten und nicht mit einer Dreierkette von Knoten enden.
Ist das auch dein Eindruck?

Ja, so ist es. Die inneren Knoten eines Baums durch andere Bäume zu ersetzen, ergibt ja in den allermeisten Fällen keinen Sinn. (Zumindest ergibt es keinen Baum.)



  Profil  Quote  Link auf diesen Beitrag Link
Newmath2012 hat die Antworten auf ihre/seine Frage gesehen.
Neues Thema [Neues Thema] Antworten [Antworten]    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-2019 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]