Aloha :)
Willkommen in der Mathelounge... \o/
Aus den natürlichen Zahlen von 1 bis n sollen wir k Werte x1;…;xk auswählen mit1≤x1≤x2≤…≤xk≤nund diese in einem k-Tupel anordnen. Dazu führen wir Zählvariablen ai ein, wobei ai 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:a1=0;a2=0;a3=2;a4=0;a5=1
Wir abstrahieren, indem wir für jede Auswahl ein Sternchen schreiben:a1=;a2=;a3=∗∗;a4=;a5=∗Die ai brauchen auch nicht mehr, da sie ja durch Semikolons voneinander getrennt sind:;;∗∗;;∗
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 (kn+k−1) Möglichkeiten zur Auswahl der Sternchen-Positionen.