Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
add comment

5 Answers

up vote 1 down vote accepted

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)

share|improve this answer
    
Just the way i wanted , thanks –  palatok Feb 13 '13 at 6:08
add comment

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.

share|improve this answer
    
thanks for the link :) –  palatok Feb 13 '13 at 6:07
add comment

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

share|improve this answer
add comment

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.

share|improve this answer
add comment

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

share|improve this answer
    
thanks a lot for help . –  palatok Feb 13 '13 at 6:07
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.