Aufgabe zu ungeordneten Zahlpartitionen

Question

Aufgabe:

2.

a) Bestimmen sie alle ungeordneten Zahlpartitionen von 4.

b) Geben sie dazu jeweils die Young-Diagramme an.

c) Beweisen sie dass P(n + 1, m + 1) = P(n − m, m + 1) + P(n, m)

Problem/Ansatz:

Ich hatte diese Aufgabe in einer Klausur und habe sie leider falsch beantwortet. Jetzt würde ich gerne wissen wie es richtig gelöst wird? Es gibt leider keine Musterlösung und mein Tutor kann mir nicht wirklich weiterhelfen, außer mit Tipps, die mich leider nicht weiterbringen.

Vielen Dank im Voraus!

Comments

Hallo,

aber Du weiß, was eine ungeordnete Zahlpartition ist? Dann schreib doch mal die Lösung für a) hierhin, damit wir sehen, dass wir über dasselbe reden.

Gruß

Answer 1

a) Bestimmen sie alle ungeordneten Zahlpartitionen von 4.

1+1+1+1 ; 2+1+1 ; 2+2 ; 3+1 ; 4

Es gibt also 5 ungeordnete Zahlpartitionen

b) Geben sie dazu jeweils die Young-Diagramme an.

Das Diagramm für 1+1+1+1 sieht wie folgt aus

[  ]
[  ]
[  ]
[  ]

Das Diagramm für 3 + 1 sieht wie folgt aus

[  ] [  ] [  ]
[  ]

c) Beweisen sie dass P(n + 1, m + 1) = P(n − m, m + 1) + P(n, m)

Das kann ich etwas später machen wenn ich etwas mehr Zeit habe. Ich würde das wieder durch vollständige Induktion machen.

Comments

ich habe versucht die c) alleine zu machen mit einer Induktion, aber ich bekomme es nicht hin. Bzw. Ich weiß nicht wie ich das bei dieser Aufgabe machen soll.
Wie muss man hier vorgehen?

---

Man beginnt typischerweise mit dem Induktionsanfang.

---

Wäre es dann so richtig?

IA: n=1, m=1

P(n + 1, m + 1) = P(n − m, m + 1) + P(n, m)

P(1 + 1, 1 + 1) = P(1 − 1, 1 + 1) + P(1, 1)

P(2, 2) = P(0, 2) + P(1, 1)

P(2,2) = P(1, 3)

Es wurde also bewiesen, dass P(n + 1, m + 1) ≠ P(n − m, m + 1) + P(n, m)

Oder ist das falsch?

---

P(0, 2) + P(1, 1) = P(1, 3) ?

Was ist das denn für ein genialer Schachzug?

Kannst du das begründen ?

Es wurde also bewiesen, dass P(n + 1, m + 1) ≠ P(n − m, m + 1) + P(n, m)

Und nach der Induktionsannahme braucht man auch keinen Induktionsschritt mehr machen oder wie?

Ich glaube das solltest du nochmal probieren aber vielleicht morgen wenn du ausgeschlafen bist.

---

Ich habe jeweils 0+1 und 2+1 gerechnet.

Der IS wäre dann: n+1, m+1

P(n + 1, m + 1) = P(n − m, m + 1) + P(n, m)

P(1 + 1 + 1, 1 + 1 + 1) = P(1 + 1 − 1 + 1, 1 + 1 + 1) + P(1 + 1, 1 + 1)

P(3,3) = P(0,3) + P(2,2)

Ich habe jetzt n+1 und m+1 angewendet und das sieht nicht richtig aus.. und ich weiß auch nicht wie ich dann weiter machen muss.

---

Hallo,

wie ist denn P(n,m) definiert?

Gruß

---

Hallo, zu der Aufgabe stand sonst nichts weiter. Oder was meinen Sie?

---

Definition und Rekursionsvorschrift findet man z.B. unter Wikipedia.

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

---

Ich weiß dennoch nicht wie man diese Formel mittels Induktion beweisen soll.

---

Ok. Hab mich gerade 10 Minuten damit beschäftigt. Du brauchst beide Formeln.

P(n + k ; k) = ∑ (j = 1 bis k) P(n ; j)

sowie

P(n ; k) = P(n - k ; k) + P(n - 1 ; k - 1)

Zeige das die Rekursive Definition auf der linken Seite die gleiche Summe berechnet wie auf der rechten Seite. Damit brauchst du keine vollständige Induktion.

Damit sollte das eigentlich möglich sein. Ich habe das jetzt zwar noch nicht gemacht aber ich habe es mal an zwei Beispielwerten probiert. Das sollte also klappen.

Achso. Ich habe hier die Rekursive Definition von Wikipedia genommen, die nicht exakt so aussieht wie deine.

Aber wenn man n durch n +1 und k durch m + 1 ersetzt dann hat man das

P((n + 1) ; (m + 1)) = P((n + 1) - (m + 1) ; (m + 1)) + P((n + 1) - 1 ; (m + 1) - 1)

P(n + 1 ; m + 1) = P(n - m ; m + 1) + P(n ; m)

Also genau die gleiche Formel.

---

Danke für die Hilfe und die Mühe!

Wenn ich diese Formel jetzt ohne Induktion beweisen möchte, dann hätte ich dennoch einfach den Wert n=1 und m=1 genommen und berechnet, dann bekomme ich dieses Ergebnis raus: P(2, 2) = P(0, 2) + P(1, 1) und wenn ich das so berechne wie oben, ist es ja nicht richtig, deswegen verstehe ich nicht wie ich das sonst beweisen soll.

Wenn ich jetzt aber n=1 und m=0 wählen würde, dann würde das Ergebnis rauskommen: P(2, 1) = P(1, 1) + P(1, 0). Jetzt würde ich die beiden P´s addieren, also P(1, 1) + P(1, 0) und das ergibt P(2, 1), also somit wäre es dann P(2, 1) = P(2, 1). Aber so kann man das ja nicht lösen?

---

Das ist falsch. zunächst mal sollst du das allgemein zeigen und nicht für spezielle zahlen. wenn du es für P(2, 1) zeigst ist damit ja nicht gesagt das es auch für P(10,5) gilt.

Daher musst du das mit den Platzhaltern machen.

Kleiner Tipp. Gehe auf die Seite

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

Und berechne z.B. P(10,5) einmal mit der Summenformel und einmal mit der rekursiven Formel.

Einen der Summanden kannst du dabei nachher auch wieder als Summe berechnen.

Bekomme dann dein Aha-Erlebnis der Berechnung und stelle den Beweis mit Buchstaben auf.

---

Vielen Dank für die Hilfe und die Mühe mir das zu erklären!