Combinations with Replacement Explanationby chaoseverlasting Tags: combinations, explanation, replacement 

#1
Dec2811, 01:19 PM

P: 1,017

I'm trying to work out the proof of combinations with replacement, but I cant quite understand the result of it.
(n+k1)ℂ(k) is the result, could somebody please explain this to me? 



#2
Dec2811, 03:33 PM

Sci Advisor
P: 5,935





#3
Dec2911, 07:23 AM

P: 1,017

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.




#4
Dec2911, 11:23 AM

P: 685

Combinations with Replacement Explanation
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: AppleBox (Box #1) BananaBox (Box #2) OrangeBox (Box #3) You have k=10 balls and have to throw the balls into the boxes. Suppose you did the following: Applebox: 3 balls Bananabox: 2 balls Orangebox: 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 (n1) dividers, e.g. n=3 requires (n1)=2 dividers. Now, how many "spots" do dividers and balls occupy? We have (n1) dividers and k balls, so in total we have (n1+k) spots. Then, let's analyze how many different positions there are for the balls: Since we have (n1+k) spots and k balls there are (n1+k)Choose(k) different positions. [tex] \binom {n1+k} {k} [/tex] Of course, you could also ask: How many different positions are there for the (n1) dividers? Since we have (n1+k) spots and (n1) dividers there are (n1+k)Choose(n1) different positions. But this is the same as above: [tex]\binom{n1+k}{n1} = \binom {n1+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. 



#5
Dec2911, 12:41 PM

P: 685

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) 



#6
Jan812, 11:48 AM

P: 1,017

Thanks a lot Edgardo! That really helps man!



Register to reply 
Related Discussions  
replacement set ?  General Math  4  
Combinations (How many combinations contain specific numbers)?  Calculus & Beyond Homework  2  
Replacement Bodies?  Biology  10  
DIY IC replacement  help!  Electrical Engineering  15 