# 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}$?

-

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)

-
Just the way i wanted , thanks –  palatok Feb 13 '13 at 6:08

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.

-
thanks for the link :) –  palatok Feb 13 '13 at 6:07

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}$.

-

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.

-

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}.$$

-
thanks a lot for help . –  palatok Feb 13 '13 at 6:07