How many ways are there to fill $k$ slots with numbers ranging from $1$ to $n$, if the numbers are in nondecreasing order? How many ways are there to fill $k$ slots with numbers ranging from $1$ to $n$, if the numbers are in nondecreasing order?  I heard the answer was ${n + k - 1 \choose k}$ but I can't work out how to get to that answer.
Thanks
 A: Hint:
It is equivalent to choose $k$ numbers from $\{1,2,\dots,n\}$, and each choice has only one non-decreasing order.
Then, it becomes a stars and bars problem, whose solution is $n+k-1 \choose k$.
A: Make a diagram with $k$ columns each with a number of squares determined by the corresponding slot. Starting at point $(0,1)$, the top left corner of the bottom square of the first column (which must be present because you do not allow $0$ in a slot), trace a path along the tops of the columns, and ending at $(k,n)$ (so after having crossed the last column rise to level $n$ if the last column did not already reach that level). Then by the weak increasing condition, the path has only rightward and upward steps, and any path from $(0,1)$ to $(k,n)$ with only rightward and upward steps will determine a filling of the slots.
There are always $k$ rightward and $n-1$ upward steps. Out of the total of $k+n-1$ steps you may choose the $k$ rightward steps in $\binom{k+n-1}k$ possible ways.
A: Let the numbers, in non-decreasing order, be $x_1,\dots,x_k$. Now define new quantities $y_1,\dots,y_{k+1}$ as follows: $y_1=x_1-1$, $y_i=x_i-x_{i-1}$ for $i=2,\dots,k$, and $y_{k+1}=n-x_k$. Clearly the numbers $y_i$ are all non-negative. Moreover,
$$\begin{align*}
\sum_{i=1}^{k+1}y_i&=(x_1-1)+\sum_{i=2}^k(x_i-x_{i-1})+(n-x_k)\\
&=(x_1-1)+\sum_{i=2}^kx_i-\sum_{i=2}^kx_{i-1}+(n-x_k)\\
&=(x_1-1)+\sum_{i=2}^kx_i-\sum_{i=1}^{k-1}x_i+(n-x_k)\\
&=\sum_{i=1}^kx_i-\sum_{i=1}^{k-1}x_i+n-x_k-1\\
&=x_k+n-x_k-1\\
&=n-1\;.
\end{align*}$$
Thus, each solution to your problem gives rise to a solution in non-negative integers to the equation
$$y_1+y_2+\ldots+y_k+y_{k+1}=n-1\;.\tag{1}$$
It’s not hard to see that this correspondence is reversible: given the non-negative $y_i$’s, it’s easy to reconstruct the $x_i$’s. But counting the solutions in non-negative integers to $(1)$ is a standard stars-and-bars problem whose solution is 
$$\binom{n-1+(k+1)-1}{(k+1)-1}=\binom{n+k-1}k\;.$$
It can also be converted into a stars-and-bars problem by lining up the numbers $1,2,\dots,n$ as the stars and imagining inserting a bar immediately in front of each number in your set. (If a number appears more than once, you’ll insert more than one bar immediately before it.) There are $n$ places to insert the bars, and you’ll insert $k$ bars, so you’ll end up with a string of $n+k$ stars and bars that has to end with a star. Thus, you have to decide which $k$ of the first $n+k-1$ positions get bars, and you can do that in $$\binom{n+k-1}k$$ ways.
