Register to reply

Combinations with Replacement Explanation

by chaoseverlasting
Tags: combinations, explanation, replacement
Share this thread:
chaoseverlasting
#1
Dec28-11, 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+k-1)ℂ(k) is the result, could somebody please explain this to me?
Phys.Org News Partner Mathematics news on Phys.org
'Moral victories' might spare you from losing again
Fair cake cutting gets its own algorithm
Effort to model Facebook yields key to famous math problem (and a prize)
mathman
#2
Dec28-11, 03:33 PM
Sci Advisor
P: 6,027
Quote Quote by chaoseverlasting View Post
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?
Could you state fully and precisely what you want to prove?
chaoseverlasting
#3
Dec29-11, 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.

Edgardo
#4
Dec29-11, 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:
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.
Edgardo
#5
Dec29-11, 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)
chaoseverlasting
#6
Jan8-12, 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