TU Wien:Statistik und Wahrscheinlichkeitstheorie UE (Gurker)/Übungen WS11/Beispiel 1.16

[Kombinatorik] Zeigen Sie, dass es ${\binom {n-1}{r-1}}$ verschiedene positive ganzzahlige Lösungsvektoren $(x_{1},x_{2},\cdots ,x_{r})$ der folgenden Gleichung gibt: $x_{1}+x_{2}+\cdots +x_{r}=n,x_{i}>0,i=1,\cdots ,r$

(Hinweis: Betrachten Sie n nichtunterscheidbare Symbole, die Sie in r nichtleere Gruppen aufteilen möchten. Z.B lautet für n = 8 und r = 3 eine mögliche Aufteilung 000|000|00.) Wieviele verschiedene nichtnegative ganzzahlige Lösungsvektoren $(x_{1},x_{2},\cdots ,x_{r})$ hat die obige Gleichung? Illustrieren Sie die Ergebnisse an einem einfachen Beispiel, etwa an den Lösungen von $x_{1}+x_{2}+x_{3}=3.$

Lösungsvorschlag

Mir hat es geholfen die Aufgabe etwas umzuformulieren:

Wieviele Möglichkeiten gibt es n Kugeln auf r Fächer aufzuteilen, wobei in jeder Lade zumindest eine Kugel sein muss.

Jede Kugel steht dabei für einen "Zähler", d.h. wenn in einem Fach drei Kugeln sind würde das 3 entsprechen.

Die Aufteilung 000|00|0|00000 bedeutet also 3 + 2 + 1 + 5 = 11 = n (r = 4)

Jetzt muss man "nur" noch die Anzahl der unterschiedlichen Anordnungen ermitteln. Dabei muss man allerdings die Einschränkung beachten, dass ein Fach nicht leer sein darf.
Dies tut man, indem man die Anzahl der Fächer r von den Kugeln abzieht (man legt die r Kugeln von vorher in die Fächer und machen damit in der weiteren Kombinationsfindung nicht mit)

Die Aufteilung (von oben) sieht nun so aus 00|0||0000 bedeutet also 3 + 2 + 1 + 5 = 11 = n (r = 4)

Wir haben nun also n - r Kugeln und r- 1 "Trennwände", also n- 1 Elemente. Wenn wir alle diese Elemente unterscheiden könnten, wären das (n-1)! Kombinationen. Aber nachdem davon (n-r) Kugeln nicht unterscheidbar sind und (r-1) Trennwände auch nicht, müssen die noch wegdividiert werden:

${\frac {(n-1)!}{(n-r)!\cdot (r-1)!}}={\binom {n-1}{r-1}}$