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.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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|cite|improve this question
1  
up vote 8 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|cite|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|cite|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
1  
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

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|cite|improve this answer

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|cite|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

The separating bars are added to the problem even though they are not there; they are imaginary.

This is a little bit thinking outside the box but it could also be confusing when there is no real connection to the problem.

Sometimes it's easier to go by an example first and make an abstraction after that. Let's do the case $n=3,k=3$ with and without the separators and hopefully the imaginary separators will find a real place for themselves after that.

Suppose we have three kinds of fruits available and we are picking three fruits in total where repetition is allowed. Let the fruits be apples, oranges, and bananas. Then the choices (without separators) are :

aaa,aao,aab,aob,aoo,abb,oob,obb,ooo,bbb.

Let's rewrite them with the separators:

aaa//,aa/o/,aa//b,a/o/b,a/oo/,a//bb,/oo/b,/o/bb,/ooo/,//bbb.

In the first line the separators are imaginary, i.e., they are not there; in the second line they are there, i.e., they are real. Then what's the difference? Why is it more helpful to have them? Well, the second line answers a question which happens to be the answer to our question as well. Think of a bit string where the separators are 1's and the fruits are 0's. The question second line answers is "how many ways are there to have exactly two 1's in a bit string of 5?"

So, what is the connection?

Here is the situation. You distributed the fruits (without separators) but you don't know how to count them. Somebody tells you that if you throw in separators then the problem is converted to a bit string question with certain number of 1's in it. Then you agree to imagine them because it solves the problem!

share|cite|improve this answer

Your Answer

 
discard

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