how many ways to make n by adding k non-negative integers (proof)? Problem : How many ways are there to make $n$ by adding $k$ non-negative integers, where order matters. Suppose $n=4$ and $k=3$. There are 15 solutions using $0, 1, 2, 3, 4$:
$(0,0,4), (0,1,3), (0,2,2), (0, 3, 1), (0, 4, 0), (1, 0, 3), (1, 1, 2), (1, 2, 1), (1, 3, 0), (2, 0, 2), (2, 1, 1), (2, 2, 0), (3, 0, 1), (3, 1, 0), (4, 0, 0)$
I found that the answer of this problem is ${n+k-1}\choose{k-1}$.
I want to know what is the proof? Why ${n+k-1}\choose{k-1}$?
 A: The classical solution goes like this: $n=4$ is made up of four objects, called "stars":
*  *  *  *

Our goal is to group these stars into three summands. We can do so by placing "bars" to separate the stars. For example, the solution "1 0 3" is
*||*  *  *

because the first group has one star, the second group has zero stars, and the third group has 3 stars.
Then, each of the four points are true:


*

*Any solution can be diagrammed as four stars and 2 bars.

*Each solution can be diagrammed in only one way

*Each solution can be recovered from its diagram

*Every diagram corresponds to a solution


So the original problem has now been converted into the new problem

How many ways are there to permute a sequence of 4 stars and two bars

Or equivalently

Given six slots, how many ways are there to select two slots to be bars (and the rest will be filled with stars)

A: You could see Wikipedia on compositiions for a simple proof.  Note that if you allow zeros, you can covert the problem to one that doesn't allow zeros by adding one to each piece.  So your problem of breaking $4$ into $3$ pieces at least $0$ is the same as breaking $7$ into $3$ pieces at least $1$.  Now think of placing $n+k$ items in a row.  You have to put a breakpoint in $k-1$ of the spaces between the items.  There are $(n+k-1)C(k-1)$ ways to choose the breakpoints.
A: Here's the proof. Instead of thinking of this problem as adding together $k$ non-negative integers to make $n$, let us think of the following problem instead. We have $k$ boxes and $n$ coins. How many ways can we distribute the coins? This is in fact the same problem, for if we have $10$ coins and $3$ boxes, we can put $1$ coin in the first box, $3$ in the second, and $6$ in the third, and this corresponds to $10 = 1 + 3 + 6$. Conversely, given $10 = 1 + 3 + 6$, I can reconstruct the above distribution scheme. 
So how to compute the number of ways of distributing $n$ coins in $k$ boxes? By the method of "stars and bars", this is just ${n+k-1 \choose k-1}$.
A: Here's an equivalent formulation of the problem.
Suppose we want to distribute $n$ identical balls into $k$ distinct boxes. How many different ways can we do that?
A good way to think of it is to reduce it to an easier problem. We can represent each ball by a '$\ast$' character and let '$|$' characters represent the distinctions between adjacent boxes. That is, if we want to distribute 2 balls into 2 boxes, we have 2 '$\ast$' characters and $2-1=1$ bar, and so our possibilities are:
$$\ast \ast | \qquad \qquad \ast | \ast \qquad \qquad | \ast \ast$$
So there are three possibilities, each representing a unique permutation of these $n$ '$\ast$' characters and $k-1$ '$|$' characters. The number of unique permutations of these characters is
$$\frac {(n+k-1)!}{n!(k-1)!} = \binom {n+k-1}{n}.$$
A: Do this to see all of the solutions.  Imagine you have $n$ characters that are letter o and $k-1$ characters that are letter x.  Every solution to your problem is can be represented uniquely by an anagram of the word composed of $n$ os and $k - 1$ xs.  
How.  Let me show and example  If $n=5$ and  $k = 3$, then x00x000 represents the solution (0, 2, 3).  The xs separate the summands.  
There are 
$${n+k-1\choose k-1}$$ 
such anagrams.
