Matroids Matheplanet Forum Index
Moderiert von matroid
Kombinatorik & Graphentheorie » Erzeugende Funktionen » gemischte erzeugende Funktionen
Autor
Universität/Hochschule gemischte erzeugende Funktionen
sonny
Aktiv Letzter Besuch: im letzten Monat
Dabei seit: 18.05.2021
Mitteilungen: 29
  Themenstart: 2021-06-16

Hallo zusammen, Ich möchte mich etwas in die erzeugenden Funktionen einarbeiten. Dazu habe ich 2 Beispiele. Es wäre nett, wenn mir jemand bestätigen könnte, ob die Aufgaben richtig gelöst und interpretiert sind. 1)Wieviele Möglichkeiten gibt es 0, 1 oder 3 schwarze Kugeln mit 1 oder 2 weiße Kugeln und mit 1 grünen Kugel und mit 0 oder 4 gelben Kugeln kombiniert (o.B.d.Rf) zu werden? \ A(x)=(1+x+x^3)(x+x^2)x(1+x^4)=x^2+2x^3+x^4+x^5+2x^6+2x^7+x^8+x^9+x^10 Für 7 Kugeln gibt es 2 Möglichkeiten. Für 9 Kugeln gibt es nur 1 Möglichkeit. 2)Die erzeugende Funktion für die Variationen (m.B.d.Rf) im obigen Beispiel ist: \ A(x)=(1/0!+x/1!+x^3/3!)(x/1!+x^2/2!)(x/1!)(1/0!+x^4/4!)=1/288*x^10+1/144*x^9+1/48*x^8+7/48*x^7+5/24*x^6 +1/2*x^5+3/2*x^4+x^3 für 7 Kugeln gibt es dann 7!7/48=735 Variationen und für 9 Kugeln 9!/144=2520 Variationen. Mein Frage ist, wie mache ich den Ansatz für die erzeugende Funktion für folgendes gemischtes Beispiel: 4 Ehepaare sollen sich auf eine Stuhlreihe mit 8 Stühlen setzen, so dass kein einziges Ehepaar nebeneinander sitzt.Wie viele Möglichkeiten gibt es? Mit der Siebformel kann ich das Problem lösen. Mich interessiert aber die Lösung über eine erzeugende Funktion. Vielleicht kann mir jemand noch ein Buch Aufgaben und Lösungen empfehlen? Danke sonny


   Profil
Nuramon
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 23.01.2008
Mitteilungen: 3010
  Beitrag No.1, eingetragen 2021-06-16

\(\begingroup\)\(\renewcommand{\Re}{\operatorname{Re}} \renewcommand{\Im}{\operatorname{Im}} \newcommand{\End}{\operatorname{End}} \newcommand{\id}{\operatorname{id}} \newcommand{\GL}{\operatorname{GL}} \newcommand{\im}{\operatorname{im}} \newcommand{\sgn}{\operatorname{sgn}} \newcommand{\d}{{\rm d}} \newcommand{\rg}{\operatorname{rg}} \newcommand{\spur}{\operatorname{spur}} \newcommand{\Hom}{\operatorname{Hom}} \newcommand{\tr}{\operatorname{tr}} \newcommand{\opn}{\operatorname}\) Hallo, es ist gut möglich, dass es eine viel einfachere Lösung gibt als folgende, aber mir ist noch keine eingefallen. Beschrifte die 8 Stühle mit den Zahlen $5^0, 5^1,\ldots, 5^7$. (Eventuell geht auch eine Basis kleiner als 5, da muss ich noch darüber nachdenken. Mit Basis 5 wird es klappen, weil dann im folgenden beim Ausmultiplizieren bei der Addition von vier Summanden im 5-adischen System keine Überträge stattfinden werden.) Die gesuchte Anzahl entspricht dann dem Koeffizienten von $x^{1+5+\ldots +5^7}$ im Produkt $$ \left(\sum_{0\leq i,j\leq 7 \\ |i-j|\geq 2} x^{5^i+5^j}\right)^4 = \left( \left(\sum_{k=0}^7 x^{5^k}\right)^2 - \sum_{k=0}^7 x^{2\cdot 5^k} - 2\sum_{k=0}^6 x^{5^k+5^{k+1}}\right)^4.$$ Inklusion-Exklusion ist weniger aufwendig. 😛\(\endgroup\)


   Profil
sonny
Aktiv Letzter Besuch: im letzten Monat
Dabei seit: 18.05.2021
Mitteilungen: 29
  Beitrag No.2, vom Themenstarter, eingetragen 2021-06-16

Ich bin überwältigt! So kompliziert hatte ich mir das nicht vorgestellt. Aber Danke für dein Bemühen. Ich werde mir das alles mal ausführlich hinschreiben, um mir einen Überblick zu verschaffen. Sind meine 2 Beispiele richtig? Kannst du mir noch ein Buch empfehlen Aufgaben mit Lösungen? Danke! sonny


   Profil
Nuramon
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 23.01.2008
Mitteilungen: 3010
  Beitrag No.3, eingetragen 2021-06-16

Nachgerechnet habe ich deine Beispiele nicht, aber die Methode ist richtig. Ich habe erzeugende Funktionen zum ersten Mal in diesem Artikel hier kennengelernt (gibt es auch als PDF hier). Da sind sehr spannende Aufgaben (sogar mit Lösungen) dabei, die zeigen, wie mächtig diese Methode ist. Ausgelegt ist der Artikel aber auf Wettbewerbsaufgaben. Ob dir das was taugt, musst du selbst entscheiden. Noch umfassender ist generatingfunctionology.


   Profil
sonny
Aktiv Letzter Besuch: im letzten Monat
Dabei seit: 18.05.2021
Mitteilungen: 29
  Beitrag No.4, vom Themenstarter, eingetragen 2021-06-17

Hallo Nuramon, ich tue mich schwer, die Vorfaktoren der Monome zu interpretieren. z.B. \ x^(5^0+5^7)*x^(5^2+5^4)*x^(5^4+5^7)*x^(5^4+5^7)=x^(5^0+5^2+3*5^4+3*5^7) Heißt das z.B.: Anzahl der Möglichkeiten, dass der Stuhl 5^3 unbesetzt und der Stuhl 5^4 dreifach besetzt ist? Warum kann man nicht einfach z.B. 5^3=3 setzen. Du hast das zwar oben wegen Übertrag erklärt. Ich kann das leider nicht nachvollziehen. Gruß sonny


   Profil
Nuramon
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 23.01.2008
Mitteilungen: 3010
  Beitrag No.5, eingetragen 2021-06-17

\(\begingroup\)\(\renewcommand{\Re}{\operatorname{Re}} \renewcommand{\Im}{\operatorname{Im}} \newcommand{\End}{\operatorname{End}} \newcommand{\id}{\operatorname{id}} \newcommand{\GL}{\operatorname{GL}} \newcommand{\im}{\operatorname{im}} \newcommand{\sgn}{\operatorname{sgn}} \newcommand{\d}{{\rm d}} \newcommand{\rg}{\operatorname{rg}} \newcommand{\spur}{\operatorname{spur}} \newcommand{\Hom}{\operatorname{Hom}} \newcommand{\tr}{\operatorname{tr}} \newcommand{\opn}{\operatorname}\) \quoteon(2021-06-17 10:39 - sonny in Beitrag No. 4) Hallo Nuramon, ich tue mich schwer, die Vorfaktoren der Monome zu interpretieren. z.B. \ x^(5^0+5^7)*x^(5^2+5^4)*x^(5^4+5^7)*x^(5^4+5^7)=x^(5^0+5^2+3*5^4+3*5^7) Heißt das z.B.: Anzahl der Möglichkeiten, dass der Stuhl 5^3 unbesetzt und der Stuhl 5^4 dreifach besetzt ist? \quoteoff Ja, so ist das zu verstehen: Jeweils eine Person auf den Stühlen $5^0,5^2$ und jeweils drei auf $5^4, 5^7$. Die restliche Stühle bleiben unbesetzt. \quoteon Warum kann man nicht einfach z.B. 5^3=3 setzen. Du hast das zwar oben wegen Übertrag erklärt. Ich kann das leider nicht nachvollziehen. \quoteoff Das Problem ist, dass z.B. $1+5 = 2+4$ gilt. Man könnte so also nicht alle Sitzordnungen voneinander unterscheiden. In Beitrag No.1 haben die Exponenten $5^i+5^j$ im $5$-adischen System jeweils 8 Ziffern, nämlich genau zwei Einsen und 6 Nullen. Vier Zahlen mit dieser Eigenschaft kann man in Basis 5 einfach ziffernweise addieren, ohne dass Überträge wie z.B. bei $2_5+ 3_5 = 10_5$ auftreten. Eine Alternative wäre es, eine erzeugende Funktion in acht Variablen $x_1,\ldots x_8$ zu betrachten - für jeden Stuhl eine: Im Polynom $$ \left(\sum_{1\leq i,j\leq 8 \\ |i-j|\geq 2} x_ix_j\right)^4$$ entspricht dann der Koeffizient von $x_1^{a_1}\cdots x_8^{a_8}$ der Anzahl Sitzordnungen, bei denen keine Ehepaare nebeneinander oder auf dem gleichen Stuhl sitzen und bei denen jeweils $a_k$ Personen auf dem $k$-ten Stuhl sitzen (wer auf wessen Schoß sitzt, spielt hier keine Rolle). \(\endgroup\)


   Profil
sonny hat die Antworten auf ihre/seine Frage gesehen.
sonny hatte hier bereits selbst das Ok-Häkchen gesetzt.

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-2021 by Matroids Matheplanet
This web site was originally made with PHP-Nuke, a former web portal system written in PHP that seems no longer to be maintained nor supported. 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]