Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Combinations with Replacement Explanation

  1. Dec 28, 2011 #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. Dec 28, 2011 #2

    mathman

    User Avatar
    Science Advisor
    Gold Member

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

Have something to add?
Similar Discussions: Combinations with Replacement Explanation
  1. Replacement set ? (Replies: 4)

  2. Combinations - (Replies: 3)

  3. E, an explanation (Replies: 9)

  4. # of combinations (Replies: 6)

  5. Explanation Needed (Replies: 5)

Loading...