 |
 |
 |
 |
 |
 |
Startseite » Forum » Anzahl von Zahlpartitionen
Anzahl von Zahlpartitionen
Universität / Fachhochschule
Binomialkoeffizienten
Erzeugende Funktionen
Rekursives Zählen
Tags: Binomialkoeffizient, Erzeugende Funktionen, Rekursives Zählen
 
|
  |
|---|
|
Eine Zahlpartition sei definiert als eine Zerlegung einer Zahl in ihre natürlichen Summanden, wobei es auf die Reihenfolge nicht ankommt, wie z.B.: 6 = 1 + 2 + 3 Sei N(n,k) die Anzahl aller (Zahl-)Partitionen einer Menge von n Elementen mit genau k Blöcken. (Im obigen Beispiel haben wir N(6,3) betrachtet, was offenbar 1 ist). Man zeige, dass damit gilt: Hinweis: Stellen Sie eine geeignete Rekursion auf und wenden sie die Theorie der Erzeugenden Funktionen auf diese Rekursion an. So, wir haben in der Vorlesung bewiesen, dass die Anzahl der Kompositionen von mit genau Summanden gleich ist (Komposition ist einfach eine Partition, wo aber de Reihenfolge relevant ist). Meiner Ansicht nach, muss ich mir nun „nur mehr noch“ überlegen, wie oft einzelne Teile vorkommen; diese muss ich dann wegdividieren. Kurz dachte ich, es würde genügen einfach a durch k zu dividieren, doch ist mir dann erst eine gewisse Zeit später aufgefallen, dass man im Falle gleicher Teile (wie etwa 15 = 5 + 5 + 5 ) Probleme bekommt. Ich sehe aber momentan nicht, ich dies in den Griff bekommen soll. Ich habe jedoch das Gefühl, dass man hier einen Multinomialkoeffizienten aufsummieren könnte, denn dieser deckt ja die Fälle mehrerer gleicher Teile ab. Mit dem Hinweis komme ich übrigens nicht klar; ich sehe nicht, wie ich hier eine Rekursion aufstellen könnte. Ich sollte dazu doch irgendwie die betroffene Menge in zwei disjunkte Teilmengen zerlegen, dann ist es mit der Rekursion nicht mehr weit. Aber, ich sehe nicht, wie man hier derart abspalten könnte. Einen kleinen Funken einer Idee gibt mir jedoch gerade meine Intuition: Eine disjunkte Menge könnte ich basteln: -Sei k beliebig aber fest; Jene Partion von , wo nur k vorkommt. -Jene Partion, bei der auch andere Zahlen vorkommen. Frage: Komme ich so zu der gewünschten Rekursion? Für alle, die mir helfen möchten (automatisch von OnlineMathe generiert): "Ich bräuchte bitte einen kompletten Lösungsweg." (setzt voraus, dass der Fragesteller alle seine Lösungsversuche zur Frage hinzufügt und sich aktiv an der Problemlösung beteiligt.) |
| Hierzu passend bei OnlineMathe: Online-Übungen (Übungsaufgaben) bei unterricht.de: |
|
 |
|
Müsste nicht sein? Das, was du zeigen sollst, ist in dieser Form gar keine Aussage, sondern ein Wert!? Zur Rekursion schlage ich vor: (Anfang: sonst). Aus einer Partition von mit Summanden geweinnt man eine von mit Summanden, indem man sich Summanden "0" dazu denkt und jeden der Summanden um 1 erhöht. Das lässt sich umkehren (jeden Summanden um 1 erniedrigen und 0en streichen), woraus sich obige Rekursion ergibt. Demnach gilt ebenso also wenn ich nicht irre. Letzteres kann man auch direkt üebrlegen: Eine Partition von mit Summanden hat entweder (mindestens) eine 1 als Summand und liefert nach deren Streichung eine Partition von mit oder alle Summanden sind so dass das Verkleinern aller Summanden eine Partiotion von mi liefert. Der Ansatz liefert dann nicht wahr? |
 |
|
Erstmal, viele Dank, das ist eine große Hilfe. Eine Rückfrage hätte ich noch (nur der Vollständigkeit/Genauigkeit halber): Hast du deine Überlegung so gemeint: "Ich nehme oBdA an, dass ich meine summen der größe nach sortiert aufgeschrieben habe: . " ? Ohne, dass die Summanden der Größe nach geordnet sind, scheint mir die angegebene Rekursion in Einzelfällen (und somit allgemein) nicht zu stimmen. Oder ist das eine Selbstverständlichkeit, die nicht extra angeführt werden muss? |
|
|
|
Ja, kann man so sagen. Da es auf die Reihenfolge nicht ankommen soll, nehme ich mir das Recht heraus, eine besondere Reihenfolge auszuzeichnen. :-) |
|
Diese Frage wurde automatisch geschlossen, da der Fragesteller kein Interesse mehr an der Frage gezeigt hat.
|
1007676
1006683