Combinations with Replacement Explanation

chaoseverlasting

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

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

mathman

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 o


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

[tex] \binom {n-1+k} {k} [/tex]

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:

[tex]\binom{n-1+k}{n-1} = \binom {n-1+k} {k} [/tex]

----

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. Statistical Physics (see page 7)

chaoseverlasting

Thanks a lot Edgardo! That really helps man!