Lösung.

Wir betrachten $ \mbox{$k+n-1$}$ Felder, auf die wir beliebig $ \mbox{$n-1$}$ Trennklötze $ \mbox{$T$}$ setzen. Vor dem ersten Trennklotz sortieren wir die ausgewählten $ \mbox{$1$}$en ein, zwischen dem ersten und zweiten Trennklotz sortieren wir die ausgewählten $ \mbox{$2$}$en ein, und so fort, bis schließlich nach dem $ \mbox{$(n-1)$}$sten Trennklotz die ausgewählten $ \mbox{$n$}$en einsortiert werden. Zum Beispiel repräsentiert für $ \mbox{$n = 5$}$ und $ \mbox{$k = 4$}$ die Belegung

$ \mbox{$\displaystyle 1\; 1\; T\; T\; 3\; T\; T\; 5 $}$
die Auswahl: $ \mbox{$2$}$mal die $ \mbox{$1$}$, $ \mbox{$0$}$mal die $ \mbox{$2$}$, $ \mbox{$1$}$mal die $ \mbox{$3$}$, $ \mbox{$0$}$mal die $ \mbox{$4$}$, $ \mbox{$1$}$mal die $ \mbox{$5$}$ (oder formal, die Funktion $ \mbox{$f(1) = 2$}$, $ \mbox{$f(2) = 0$}$, $ \mbox{$f(3) = 1$}$, $ \mbox{$f(4) = 0$}$, $ \mbox{$f(5) = 1$}$.)

Für die Verteilung der $ \mbox{$n-1$}$ Trennklötze $ \mbox{$T$}$ in die $ \mbox{$k+n-1$}$ Felder gibt es $ \mbox{${k+n-1\choose n-1} = {k+n-1\choose k}$}$ Möglichkeiten. Dies ist auch die Anzahl der möglichen Auswahlen der angegebenen Art.