# Combinations with Replacement Explanation

by chaoseverlasting
Tags: combinations, explanation, replacement
 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: 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. $$\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.