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