25
$\begingroup$

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.

$\endgroup$
19
$\begingroup$

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

$\endgroup$
  • 3
    $\begingroup$ Hi Michael! Could you please add an explanation why you have (k-1) under (n+k-1) and not (k) as in the formula (and in the question)? Thank you! $\endgroup$ – user2424380 Mar 1 '17 at 10:47
  • $\begingroup$ Note that in other places the categories (or types) to choose from are denoted as n (hence the number of "dividers" is n-1), and the number to choose is k; this answer has these variable names reversed. $\endgroup$ – Klaus Mar 29 at 8:16
14
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ we only need the Xs, why do we count the vertical bars? $\endgroup$ – user31280 Oct 6 '12 at 22:12
  • $\begingroup$ 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. $\endgroup$ – user22805 Oct 6 '12 at 22:15
  • $\begingroup$ Perfect and very informative. $\endgroup$ – Gigili Oct 7 '12 at 9:44
  • $\begingroup$ @user22805 but number of vertical bars is always $n-1$ either, so combinations still indistinguishable. $\endgroup$ – Hi-Angel May 15 '16 at 18:36
5
$\begingroup$

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

$\endgroup$
  • $\begingroup$ $a = k, b= (n-1)$, which is why the two expressions given in the question are equal. $\endgroup$ – Mark Bennet Oct 6 '12 at 21:24
  • $\begingroup$ 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. $\endgroup$ – user31280 Oct 6 '12 at 21:31
  • 1
    $\begingroup$ 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. $\endgroup$ – Mark Bennet Oct 7 '12 at 5:39
3
$\begingroup$

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!

$\endgroup$
0
$\begingroup$

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

$\endgroup$
0
$\begingroup$

To get some intuition for formula $\binom{n+k-1}{k}$ the problem can be viewed in the following way.

Let say from $n$ different objects you first choose $l$ that you want to use (and therefore have $k-l$ repetitions). Now to count how many possibilities there are to have $k - l$ repetitions you divide $k$ elements into $l$ non-empty categories (each category corresponds to different object, while number of elements in categories is equal to number of copies/repetitions of this object and at least one copy of element should be present). So you count $\binom{k - 1}{l - 1}$=$\binom{k - 1}{k - l}$.

Overall it's necessary to count how many ways there are to choose $l$ from $n$ and given $l$ count $k-l$ in $k-1$ or in other words $\binom{n+k-1}{k}$.

$\endgroup$
0
$\begingroup$

Say you need to choose k=5 donuts from n=7 types of donuts. You can assign positions for the 5 donuts plus the 7-1=6 dividers separating the types of donuts you choose:

┌─┬─┬─┬─┬─┬─┬─┬─┬─┬──┬──┐
│1│2│3│4│5│6│7│8│9│10│11│
└─┴─┴─┴─┴─┴─┴─┴─┴─┴──┴──┘

Now, choose 5 of these 11 positions in which to put the donuts (the rest will be dividers):

$$\binom{n + k - 1}{k} = \binom{11}{5} = 462$$

Alternatively, choose n-1=6 positions in which to put the dividers (the rest will be donuts):

$$\binom{n + k - 1}{n-1} = \binom{11}{6} = 462$$

$\endgroup$
-1
$\begingroup$

In distinguishing between combinations allowing repetition and those not, I think it's a question of supply of the objects being selected that's important to consider. Without repetition is appropriate when supply is limited; with repetition when supply is unlimited.

For example, a grocery store sells 5 kinds of fruit, and you're going to purchase 3 individual fruits without restriction. The equation would then be: (n+r-1)! / r!(n-1)! = (5+3-1)! / 3!(5-1)! = 7! / 3!*4! = 35

Contrast this with there are five different fruits in a bowl, and you'll pick 3: n! / r!(n-r)! = 5! / 3!(5-3)! = 5! / 3!*2! = 10

In both equations above, I'm using n = number of choices, r = number of events.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy