Combinations with Replacement Explanation

[chaoseverlasting]

I'm trying to work out the proof of combinations with replacement, but I can't quite understand the result of it.

(n+k-1)ℂ(k) is the result, could somebody please explain this to me?

 

[mathman]

I'm trying to work out the proof of combinations with replacement, but I can't quite understand the result of it.

(n+k-1)ℂ(k) is the result, could somebody please explain this to me?

Could you state fully and precisely what you want to prove?

 

[chaoseverlasting]

It is the formula for selection of k items with replacement from a set of n items. I understand the result now, but how do I prove it? Apparently its to be done by induction, but I'm not quite sure of how to approach it.

 

[Edgardo]

If I understood you correctly your problem is the following:
Given n items choose k from them. And replacement means you are allowed to choose an item more than once.

-------------------------

You can interpret the problem in the following way:
Imagine you have n=3 boxes. Each box stands for a fruit:
Apple-Box (Box #1)
Banana-Box (Box #2)
Orange-Box (Box #3)

You have k=10 balls and have to throw the balls into the boxes. Suppose you did the following:
Apple-box: 3 balls
Banana-box: 2 balls
Orange-box: 5 balls
This means you get 3 apples, 2 bananas and 5 oranges.

So, one combination is:
In box 1 we have 3 balls
In box 2 we have 2 balls
In box 3 we have 5 balls

---

We can model this by dividing the 10 balls into 3 blocks:
o o o | o o | o o o o o
The blue bars are the dividers.

Other combinations are:

All balls in box 1 (only apples):
o o o o o o o o o o | |

0 balls in box 1,
3 balls in box 2,
7 balls in box 3
| o o o | o o o o o o o

1 ball in box 1,
4 balls in box 2,
5 balls in box 3
o | o o o o | o o o o oFor n blocks (boxes) we need (n-1) dividers, e.g. n=3 requires (n-1)=2 dividers.
Now, how many "spots" do dividers and balls occupy? We have (n-1) dividers and
k balls, so in total we have (n-1+k) spots.

Then, let's analyze how many different positions there are for the balls:
Since we have (n-1+k) spots and k balls there are (n-1+k)Choose(k) different positions.

\binom {n-1+k} {k}

Of course, you could also ask:
How many different positions are there for the (n-1) dividers?
Since we have (n-1+k) spots and (n-1) dividers there are (n-1+k)Choose(n-1) different positions. But this is the same as above:

\binom{n-1+k}{n-1} = \binom {n-1+k} {k}

----

Further readings:
1. Counting selections with replacement
The derivation is given in the end.

2. Combinations - order doesn't matter, repetitions allowed
This is a PF thread.

 

[Edgardo]

Another way to think of it are k Bosons occupying n energy levels, see:
1. A derivation of the Bose–Einstein distribution (wikipedia article), Notes
2. http://hep.ph.liv.ac.uk/~hock/Teaching/StatisticalPhysics-Part5-Handout.pdf (see page 7)

 

[chaoseverlasting]

Thanks a lot Edgardo! That really helps man!