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.

The formula for computing a k-combination with repetitions from n elements is: $$\binom{n + k - 1}{k} = \binom{n + k - 1}{n - 1}$$

I would like if someone can give me a simple basic proof that a beginner can understand easily.

share|improve this question
    

5 Answers 5

up vote 1 down vote accepted

This problem comes by many names - stars and stripes, balls and urns - it's basically a question of how to distribute $n$ objects (call them "balls") into $k$ categories (call them "urns"). We can think of it as follows.

Take $n$ balls and $k-1$ dividers. If a ball falls between two dividers, it goes into the corresponding urn. If there's nothing between two dividers, then there's nothing in the corresponding urn. Let's look at this with a concrete example.

I want to distribute $5$ balls into $3$ urns. As before, take $5$ balls and $2$ dividers. Visually:

|ooo|oo

In this order, we'd have nothing in the first urn, three in the second urn and two balls in the third urn. The question then is how many ways can we arrange these 5 balls and two dividers? Clearly: $\dfrac{(5+3-1)!}{5!(3-1)!} = \displaystyle {7 \choose 2} = {7 \choose 5}$.

We have that there are $\dfrac{(n+(k-1))!}{(k-1)! n!}$ the $n$ balls and $k-1$ dividers (since the balls aren't distinct from each other and the dividers aren't distinct from each other). Notice that this is equal to $\displaystyle {n+k-1 \choose k-1} = {n + k - 1 \choose n}$.

share|improve this answer

Basically $$\binom {a+b}{a} = \binom {a+b}{b} = \frac {(a+b)!}{a!b!}$$

because the number of ways of choosing $a$ items from $a+b$ is the same as the number of ways of choosing the $b$ items to exclude so that $a$ are left over. The formula is symmetric in $a$ and $b$.

share|improve this answer
    
$a = k, b= (n-1)$, which is why the two expressions given in the question are equal. –  Mark Bennet Oct 6 '12 at 21:24
    
I'm not asking why the two expressions are the same, I know that. I just want to know how they came by the expression. –  user31280 Oct 6 '12 at 21:31
    
Well as other answers have made clear, having noticed the structure of the expression you will be looking at $n+k-1$ objects and choosing $n-1$ of them as dividers. –  Mark Bennet Oct 7 '12 at 5:39

OK, suppose I draw (with replacement) $k$ items from the $n$, and mark them down on a scoresheet that looks like this, by putting an X in the appropriate column each time I draw an item.

scoresheet

The result will be $k$ Xs, separated by ($n-1$) vertical bars. Counting the Xs and the vertical bars together is $k+n-1$ items. And what I've drawn is entirely determined by which of those $k+n-1$ items are the Xs.

This is clearly $\binom{k+n-1}{k}$.

scoresheet filled out

share|improve this answer
    
we only need the Xs, why do we count the vertical bars? –  user31280 Oct 6 '12 at 22:12
    
If we don't count the vertical bars, all we have is $k$ indistinguishable Xs, and no way to tell one combination from another - so there's nothing to count. Only by counting the vertical bars do we have a way of telling the combinations apart. –  user22805 Oct 6 '12 at 22:15
    
Perfect and very informative. –  Gigili Oct 7 '12 at 9:44

Suppose you have $n+k-1$ distinct balls and two bags. Now you want to pick $k$ balls and put them in bag $1$ and the rest $n-1$ balls in bag $2$.

If you choose $k$ balls first, there are $\binom{n + k - 1}{k}$ possible ways to do that. On the other hand, you can think you are actually picking $n-1$ balls first and put them in bag $2$ and the rest $k$ balls in bag $1$. These two methods should be equivalent (choosing $k$ balls for bag $1$ is the same as choosing $n-1$ other balls for bag $2$). Therefore, $\binom{n + k - 1}{k}=\binom{n + k - 1}{n-1}$.

share|improve this answer

I really liked this example with the 15 cans of soda: http://www.csee.umbc.edu/~stephens/203/PDF/6-5.pdf

share|improve this answer

Your Answer

 
discard

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