Zahlenpartitionen für die gilt n = x1+x2+...xn mit xn {1,2,5}

Question

Sei a_n alle Zahlenpartitionen für die gilt   n = x₁+x₂+......+x_n   mit  x_n ∈ {1,2,5}

Zeigen Sie das:

∑^∞_n=0 a_n*xⁿ = (1 / (1-x))  *  (1 / (1-x²))  *  (1 / (1-x⁵))

Kann mir jemand bitte bei dieser Aufgabe helfen? :)

Comments

Die Aufgabe erscheint mir ein wenig unklar formuliert. Könntest du den Text im Original wiedergeben?

---

defined: Arbeite dich schon mal hier durch:

https://de.wikipedia.org/wiki/Partitionsfunktion

Vielleicht hilft das ja.

---

Das ist den Text im Original (b). @Lu Ich hab schon alles versucht, konnte es leider nicht schaffen.

---

Eine Zerlegung der 5 ist z.B. die Summe  1 + 1 + 1 + 2 , die die Eins dreimal, die Zwei einmal und die Fünf keinmal enthält.
Dem entspricht gerade die Potenz  x^1·3 · x^2·1 · x^5·0  =  x⁵  .

Genauso geht es für alle anderen Partitionen.

---

Okay also, wie mache ich  b) dann? Kannst du bitte bisschen umschreiben? Wäre sehr dankbar :)

---

Mein Kommentar bezog sich doch auf Teil b).

Du musst die drei Faktoren ausmultiplizieren.

---

Ja aber das ist auf jeden Fall kein (1 / (1-x) * ...usw.

Trotzdem danke )

---

Weißt du, was mit ausmultiplizieren gemeint ist ?

---

@hj2122: Wird bei  b) " n = x₁+x₂+......+x_n   mit  x_n ∈ {1,2,5} " n auf 2 oder 3 Arten verwendet? 

Answer 1

∑^∞_n=0 a_n*xⁿ = (1 / (1-x))  *  (1 / (1-x²))  *  (1 / (1-x⁵)) 

Das Produkt rechts kann als Resultate von geometrischen Reihen aufgefasst werden.

 (1 / (1-x))   = 1 + x + x^2 + x^3 + x^4 + x^5 +.......  , für |x|<1.

 (1 / (1-x²))  = 1 + x^2 + (x^2)^2 + (x^2)^3 + ....., für |x^2| < 1, also für |x| < 1.

(1 / (1-x⁵)) = 1 + x^5 + (x^5)^2 + (x^5)^3 + .... , für |x^5| < 1, also für |x| < 1. 

Nun "ausmultiplizieren" und nach Partitionen der Zahl n  sortieren:

 ( 1 + x + x^2 + x^3 + x^4 + x^5 +....... )* ( 1 + x^2 + (x^2)^2 + (x^2)^3 + ....) *(1 + x^5 + (x^5)^2 + (x^5)^3 + ...) 

= 1*1*1 + x^1*1*1 + x^2*1*1 + 1*x^2 * 1 + x^3 * 1*1 + x^1 * x^2 * 1 + (x^2)^2 *1*1 + x^2 * (x^2)^2 * 1 + 1*(x^2)^2 * 1 + x^5*1*1 + .....

In dieser Summe stamm der erste Faktor immer aus der ersten, der zweite Faktor aus der zweiten und der dritte Faktor aus der dritten Klammer.

Nun die Interpretation:

= 1*1*1 x^0  Es gibt genau eine Partition der Zahl 0. Nämlich: Man nimmt 0*1 + 0*2 + 0*5. ==> a_(0) = 1

+ x^1*1*1      Es gibt genau eine Partition der Zahl 1. Nämlich: Man nimmt 1*1 + 0*2 + 0*5. ==> a_(1) = 1. 

+ x^2*1*1 + 1*x^2 * 1  Es gibt genau zwei Partitionen der Zahl 2. Nämlich 2*1 + 0*2 + 0*5 und 0*1 + 1*2 + 0*5  . ==> a_(2) = 2

+ x^3 * 1*1 + x^1 * x^2 * 1   Partitionen der Zahl 3. Nämlich 3*1 und 1*1 + 1*2.  ==> a_(3) = 2

+ x^4 *1*1 + x^2 * (x^2)^2 * 1 + 1*(x^2)^2 * 1 + .....Partitionen der Zahl 4. Nämlich 4*1 + 0*2 + 0*5 und 2*1 + 1*2 + 0*5 und 0*1 + 2*2 + 0*5.

==> a_(4) = 3 usw. 

Comments

Ich überschreite angeblich oben gerade 8000 Zeichen. Daher Fortsetzung als Kommentar:

Nun kommt der Koeffizient von x^5 usw.

Das ist dann das, was dir hj2122 zu Beginn versucht hat zu erklären:

  x^3*1 · x^1*2 · x^0*5  =  x⁵  .

Beim Ausmultiplizieren kommt jede Partition genau einmal vor als Summand in der ausgeschriebenen Summe oben.Daher gibt der Koeffizient a_(n) von x^n dann gerade die Anzahl Partitionen der Zahl n an.

---

Vielen Dank für die große Hilfe Lu! :)

PS: Ich hab versucht x⁵ auszurechnen, a5 ist dann gleich 4?

x⁵.1.1+x³.(x²)⁴.1+1.(x²)³.1+1.(x²)².1.. stimmt das?

---

Korrektur

x⁵.1.1+x³.(x²)^1.1+x.(x²)^2.1+1.1.x^5  = 4 x^5. 

Also 1+1+1+1+1 + 0*2 + 0*5, 1+1+1+2 + 0*5 , 1+2+2 + 0*5, 0*1+0*2+ 5.

 ==> a_(5) = 4. 

Aber du brauchst das nicht alles auszuzählen. Wichtig ist, dass du erklärst, dass x^5 genau so oft vorkommt, wie die Anzahl der fraglichen Partitionen der Zahl 5.

Bei b) ist eine Begründung verlangt und nicht die explizite Rechnung. Die kannst du natürlich als Illustration deiner Erklärung anfügen, damit du keinen Roman schreiben musst. 

Answer 2

n steht für irgendeine der unendlich vielen natürlichen Zahlen.

Es wird auf eine einzige Art verwendet (nämlich als Laufindex der Reihe).

Davor hätte es vielleicht deutlicher heißen sollen  "Sei a_n die Anzahl der Zahlpartitionen von n, ... " .

Comments

Es wird auf eine einzige Art verwendet (nämlich als Laufindex der Reihe).

Dieser Satz stimmt nicht.

Es sollte zwar so sein, aber dann muss es tatsächlich  " n = x₁ + x₂ + ... + x_k   mit  x_i ∈ {1 ; 2 ; 5}  für  i = 1 , .. , k " heißen. Die richtige Antwort auf deine Frage lautet also " 3 " .