Aloha :)
Willkommen in der Mathelounge... \o/
Aus den natürlichen Zahlen von \(1\) bis \(n\) sollen wir \(k\) Werte \(x_1;\ldots;x_k\) auswählen mit$$1\le x_1\le x_2\le\ldots\le x_k\le n$$und diese in einem \(k\)-Tupel anordnen. Dazu führen wir Zählvariablen \(a_i\) ein, wobei \(a_i\) angibt, wie oft die Zahl \(i\) ausgewählt wurde.
Ist also z.B. \(n=5\) und \(k=3\), wäre das \(3\)-Tupel \((3,3,5)\) wie folgt codiert:$$a_1=0\quad;\quad a_2=0\quad;\quad a_3=2\quad;\quad a_4=0\quad;\quad a_5=1$$
Wir abstrahieren, indem wir für jede Auswahl ein Sternchen schreiben:$$a_1=\quad;\quad a_2=\quad;\quad a_3=\ast\ast\quad;\quad a_4=\quad;\quad a_5=\ast$$Die \(a_i\) brauchen auch nicht mehr, da sie ja durch Semikolons voneinander getrennt sind:$$;;\ast\ast;;\ast$$
Die Anzahl der Sterne ist für jedes Tupel gleich \(k\) und die Anzahl der Semikolons ist für jedes Tupel gleich \((n-1)\).
Wir haben in unserer Codierung also insgesamt \((n+k-1)\) Positionen, von denen wir genau \(k\) auswählen müssen, um sie mit einem Sternchen zu besetzen. Die übrigen \((n-1)\) Positionen sind dann automatisch jeweils durch ein Semikolon zu besetzen.
Es gibt genau \(\binom{n+k-1}{k}\) Möglichkeiten zur Auswahl der Sternchen-Positionen.