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
Professor quantifies how 'one thing leads to another'
Team announces construction of a formal computer-verified proof of the Kepler conjecture
Iranian is first woman to win 'Nobel Prize of maths' (Update)
mathman
#2
Dec28-11, 03:33 PM
Sci Advisor
P: 6,057
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