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?
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.
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.
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)