Zahlenpartition | mögliche Belegungen der Gleichung

Question

Zu zeigen ist, dass es (n+k-1-m über k-1) mögliche Belegungen der ni, in der Gleichung n = n1 + … + nk gibt, wenn 1 ≤ m ≤ n1 und ni ≥ 0 für i ≥ 2 gilt.

Wie zeige ich dies?

Comments

Mit n ist doch vollständige Induktion naheliegend?

lul

---

Wir müssen vollständige Induktion hier verwenden? Wie würde ich vorgehen?

Answer 1

Eine einfache kombinatorische Erklärung ist folgende: Zunächst schreiben wir \(n-m=n_1'+n_2+ \cdots n_k\) mit \(n_1'=n_1-m\). Dann machen wir uns eine Liste mit n-m+k-1 Plätzen. Daraus wählen wir k-1 aus. Das Ergebnis dieser Wahl gibt uns die Zelegung: Jeder freie Platz bedeutet einen Beitrag von 1 für n_i, die ausgewählten Plätze sind die Trenner zwischen den n_i.

Beispiel:

000X00XX00000X.....

n'_1=3, n_2=2, n_3=0,n_4=5.....