How is the formula for unordered with replacement derived?

[skwey]

Hello, is there any derivation on the net for the unordered with replacement formula?
I've searcced but didnt find any.

Ex: You have 5 different tickets and you shall choose 3 from a bowl. When one is chosen another like the chosen one is put in the bowl. The answer is 35, and the formula is
(n+r-1)!/r!/(n-1)!

The 35 possibilities are:
111 112 113 114 115 122 123 124 125 133 134 135 144 145 155
222 223 224 225 233 234 235 244 245 255 333 334 335 344 345 355
444 445 455 555


So please help me explain the formula (n+r-1)/Cr=(n+r-1)!/r!/(n-1)!

How do we come to this formula?

 

[Simon Bridge]

the answer to what is 35?

You mean the number of different ways to pick 3 objects from a set of 5 is 35 (allowing repititions)?
That's called combinations.
(Start with the derivation without repetition and work you way up.)

But you may find this one easier to understand.

 

[skwey]

the answer to what is 35?

You mean the number of different ways to pick 3 objects from a set of 5 is 35 (allowing repititions)?
That's called combinations.
(Start with the derivation without repetition and work you way up.)

But you may find this one easier to understand.

The answer to your first question is yes. Your second link does not say anything about my problem. I found an explanation in the fist link but it is hard.

There is an easy way to understand the above result. Label the elements of S with numbers 0, 1, ..., n − 1, and choose a k-combination from the set of numbers { 1, 2, ..., n + k − 1 } (so that there are n − 1 unchosen numbers). Now change this k-combination into a k-multicombination of S by replacing every (chosen) number x in the k-combination by the element of S labeled by the number of unchosen numbers less than x. This is always a number in the range of the labels, and it is easy to see that every k-multicombination of S is obtained for one choice of a k-combination.

If I try to use this explanation as a guide I get stuck:

There is an easy way to understand the above result. Label the elements of S with numbers 0, 1, ..., n − 1,

Ok, this is ok, I have 5 elements, A, B, C, D, E, I label them A=0, B=1,C=2, D=3, E=4

and choose a k-combination from the set of numbers { 1, 2, ..., n + k − 1 } (so that there are n − 1 unchosen numbers).

I shall choose 3 numbers from, 1,2,3,4,5,6,7. Let's say I choose 3,5,6. But now comes the hard part:

Now change this k-combination into a k-multicombination of S by replacing every (chosen) number x in the k-combination by the element of S labeled by the number of unchosen numbers less than x.

Do you understand what this means? What is ""element of S labeled by the number of unchosen numbers less than x."" I looked at the example but couldn't get that either.

 

[awkward]

You may find Theorem Two on this page interesting:

http://en.wikipedia.org/wiki/Stars_and_bars_(combinatorics)

 

[Simon Bridge]

In general - these combinations and permutations things are just a way of counting objects when we rearrange them. The second link is good at showing that and also shows a way to build a proof using intuitive concepts ... we all know how to count right?

Right!

You have the right idea - you are using the counting method to build to your example.
Lets recap anyway - the strategy is to build up to the sampling-with-replacement case, using your specific example rather than theirs: choosing 3 out of 5.

You have five contestants (Alice, Bob, Carol, Dave and Ellie) and 3 prizes.
Start with the easiest case to explain: the prizes are for 1st, 2nd, and third best at some task: fastest runner, smallest cell-phone, farthest spit, whatever.

Any one of the 5 can come first, any of the remaining 4 can come second, and any of the remaining 3, third. This gives 5x4x3=60 different ways to award the prizes.

If there are r prizes and n contestants, this generalizes to:
n.(n-1).(n-2)...(n-r-2).(n-r+1) different ways ... which is the same as n!/(n-r)!

note: there are other representations that will occur to you - eg n!/(r-1)! - they are equivalent and this one is useful. All the division is telling you is that you need only do the first r terms in the factorial product.

But what if we don't care who is first, second or third ... maybe I just hand out prizes to the first three to put their hands up? So it makes no difference when Alice sticks her hand up, if she's i the first three, she gets a prize. This becomes clear if the prizes are identical - let's say they all get a candy-bar. (OK, maybe 1st prize has a gold star on it, 2nd has a silver star, and third has a brown star ... who cares: it's all candy!)

There are several different ways to count this, but if you use the above method, you'll have over-counted because ABC has the same result as BCA - they all get one candy bar - but you counted them separately.

The number of times each combination has been over-counted is 3!=6 times... which is the number of ways the 3 winners can be ordered amongst themselves.

For our example - this is 60/6 = 10So far so good. Now for the tricky bit:
What if I give three contests - running, cell-phone comparison, and spitting - and award a prize to the best at each.

Now it is possible for Alice to compete for up to three prizes.
This is the situation for sampling with replacement.

You could start with 5x5x5 ways to award the prizes, then divide out the duplications ... or realize that this is three cases added together.

case 1: one person is best in each category - 1 bar each = 10 (already done)
case 2: one person is best in all categories - gets a single prize of three bars = 5 (count them)
case 3: one person gets 2 bars, and one gets 1 - this is a combination of choosing 2 from 5, which is 20 (check).

Add them together: 10+5+20=35 ways to award the prizes!

The calculation was:

$$35 = \frac{5!}{3!(5-3)!} + \frac{5!}{(3-1)!(5-(3-1))!} + 5 =10+20+5$$... there was a promising series building there.
If we notice that 5 = 5!/4! = 5!/(3-2)!(5-(3-2))! we have it!

$$35 = \sum_{i=0}^{2} \frac{5!}{(3-i)!(5-3+i)!} = \sum_{i=1}^{3} \frac{5!}{i!(5-i)!}$$... you should satisfy yourself that this is correct.

By extrapolation, we pick r out of n, and get something like:

$$N = \sum_{i=1}^{r} \frac{n!}{(i)!(n-i)!}$$... now you just need to do the sum xD

Find the common denominator, and simplify...
You need to realize stuff like that (n-r+1)! = (n-r+1)(n-r)!
... it's not all that easy to do but it is easy(ish) to understand.

One approach is to keep 3 prizes but keep increasing the number of contestants, and spot the pattern. That will simplify the math, and you are after a derivation, not a proof.

Alternatively you can try a shortcut that is harder to understand but the algebra is easier.

The reason I gave you the counting link is that I guessed you did/would not find the wikipedia derivation all that helpful to your understanding. Relating everything back to counting stuff helps your understanding ... but you need to know about the math of factorials to actually do the derivation. I gave you the wikipedia link because (a) it answers the question you posed and, (b) I could have guessed wrong.

Hopefully, now you have deepened your understanding of combinations, you can follow the alternative approach.

Soooo, to hand out the prizes, I line up all five in alphabetical order and move along the line.
(Any method that ends up with the right people getting the right number of prizes is equivalent - so I picked one that makes the math easy.)

If the prize is BEB, I can see I need to move 1 space down the row (to Bob), give Bob 2 bars, then move 3 spaces (to Ellie) and give her one bar.

That would be: >oo>>>o (from the link).

Notice it doesn't matter is the result it BBE or EBB either, the instructions to hand out the prizes is the same.

This method changes the game from picking 3 from 5 with repetitions allowed to an exactly equivalent one where we pick 3 from 7 without repetition.

We know how to do that!