Combinations with Replacement Explanation

  1. 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?
  2. jcsd
  3. mathman

    mathman 6,435
    Science Advisor
    Gold Member

    Could you state fully and precisely what you want to prove?
  4. 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.
  5. 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.
  6. Last edited: Dec 29, 2011
  7. Thanks a lot Edgardo! That really helps man!
Know someone interested in this topic? Share a link to this question via email, Google+, Twitter, or Facebook

Have something to add?
Similar discussions for: Combinations with Replacement Explanation