Answer: $\binom{k+n-1}{k}=\binom{k+n-1}{n-1}$ Solution 1: Let $$T=\left\{\left(b_{1}, \ldots, b_{n}\right) \mid 0 \leq b_{1}, \ldots, b_{n} \leq k, b_{1}+\cdots+b_{n}=k\right\}$$ The sum in question counts $|T|$, by letting $a_{i}$ be the number of $b_{j}$ that are at least $i$. By stars and bars, $|T|=\binom{k+n-1}{k}$. One way to think about $T$ is as follows. Suppose we wish to choose $k$ squares in a grid of squares with $k$ rows and $n$ columns, such that each square not in the bottom row has a square below it. If we divide the grid into columns and let $b_{j}$ be the number of chosen squares in the $j$ th column then we get that $T$ is in bijection with valid ways to choose our $k$ squares. On the other hand, if we divide the grid into rows, and let $a_{i}$ be the number of chosen squares in the $i$ th row (counting up from the bottom), then we obtain the sum in the problem. This is because we have $\binom{n}{a_{1}}$ choices for the squares in the first row, and $\binom{a_{i-1}}{a_{i}}$ choices for the squares in the $i$ th row, given the squares in the row below, for each $i=2, \ldots, k$.