Matroids Matheplanet Forum Index
Moderiert von matroid
Kombinatorik & Graphentheorie » Erzeugende Funktionen » gemischte erzeugende Funktionen
Druckversion
Druckversion
Antworten
Antworten
Autor
Universität/Hochschule gemischte erzeugende Funktionen
sonny
Junior Letzter Besuch: in der letzten Woche
Dabei seit: 18.05.2021
Mitteilungen: 16
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  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?

fed-Code einblenden
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:
fed-Code einblenden

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



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Nuramon
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 23.01.2008
Mitteilungen: 2984
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  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\)


Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
sonny
Junior Letzter Besuch: in der letzten Woche
Dabei seit: 18.05.2021
Mitteilungen: 16
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  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



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Nuramon
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 23.01.2008
Mitteilungen: 2984
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  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.



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
sonny
Junior Letzter Besuch: in der letzten Woche
Dabei seit: 18.05.2021
Mitteilungen: 16
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.4, vom Themenstarter, eingetragen 2021-06-17


Hallo Nuramon,
ich tue mich schwer, die Vorfaktoren der Monome zu interpretieren. z.B.
fed-Code einblenden

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



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Nuramon
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 23.01.2008
Mitteilungen: 2984
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  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}\)
2021-06-17 10:39 - sonny in Beitrag No. 4 schreibt:
Hallo Nuramon,
ich tue mich schwer, die Vorfaktoren der Monome zu interpretieren. z.B.
fed-Code einblenden

Heißt das z.B.: Anzahl der Möglichkeiten, dass der Stuhl 5^3 unbesetzt und der Stuhl 5^4 dreifach besetzt ist?
\(\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}\)
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.

\(\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}\)
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.
\(\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}\)
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\)


Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
sonny hat die Antworten auf ihre/seine Frage gesehen.
sonny hatte hier bereits selbst das Ok-Häkchen gesetzt.
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-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]