Combination vs Permutation formula

[davidformba]

Can someone explain to me the key difference as to why the Combination and permutation formulas are different by n!

Combination=
C(n,r)=n!/(n-r)!

Permutation=
P(n,r)=n!/n!(n-r)!

I get that Permutation doesn't care about the order. But I'm looking for a core, simple explanation behind the formulas so that the concept is understood better by me. I have the formulas down, but wonder if I'd do better in knowing the bigger picture rather than taking the formula and looking for the plug in numbers. Any comment would be appreciated.

[rishim]

Well ..
Iw ould say that. permutation is done when things are same.
Suppose you have 3 red balls and you would like to place them in three holes.
Whatever you do they would look like the same. But you can definately place them in 6 ways

In case of combination things that are to be distributed are not the same.
Suppose you have 3 balls blue green and red.
Now you have to place them in 3 different holes.
You can have 6 combinations. Right?
But with 3 same balls you would get only 1 combination.

Combination takes care by dividing the permutation with the number or repetitions that occur.

I would give you another example.
Suppose you have 4 balls. 2red and two blue.
Now you have to place them in 4 positions.
Had there been 4 different balls tha answer would have been 4!=24.
But Two balls are same.
And hence there is repetioin of some sequence.

Therefore we divide the number by the number of repetion that will take plae.
2 For red and 2 for blue.

Answer would be 6.

I hope I have cleared your doubt.

Regards,
Rishi

[shashibg]

hii guys;
rishim you have explained it really well but
repetition is allowed in permutation and not in combination
so you need to swap permutation with combination in
your above explaination

permutation=
P(n,r)=n!/(n-r)!

combination=
C(n,r)=n!/n!(n-r)!

[ursula]

Hi Dave,
First of all, you got the Combination and Permutation mixed up - but I guess that was the whole point of your post

I came up with this mnemonic device to keep these straight:
P=Prizes (permutations)
C=Committee (combinations)
Here's the full story:

[/SIZE]Permutations ("Prizes")[/SIZE]
Let's say you have 5 people who are running a race, and you want to know in how many ways three prizes (gold, silver, and bronze medal) could be awarded.
Any of the 5 could win the gold, any of the remaining 4 could win silver, and any of the other 3 could win bronze.
So you get 5 x 4 x 3 possibilities.
You can get this result using the permutation formula:
P(5,3) = 5! / (5-3)! = (5 x 4 x 3 x 2 x 1) / (2 x 1) = 60

Notice that the effect of the denominator in the formula is just to cancel out the last two terms from the numerator. That's why I prefer to think of it as simply an incomplete factorial where you multiply out only as many terms as you have selections. In this case, instead of the complete factorial of 5 x 4 x 3 x 2 x 1, you only have three prizes to be awarded, so you stop after the third term.

[/SIZE]Combinations ("Committee")[/SIZE]
Now think of the same 5 people, but your task this time is to form a committee of 3 (with no special roles, just equal members). You could do your selection in the same way as above, but you would find that some of these permutations give you the same committee. For example, it doesn't matter whether your selection is person A, then C, then D or whether it is C, then D, then A. So the straightforward selection process we used to award prizes for the race needs to be adapted a bit. We need to divide by the number of possible ways in which a particular committee could have been picked. This is simply the factorial of the number of committee members, in this case 3!
For example, consider these 6 permutations:
ACD
ADC
CAD
CDA
DAC
DCA
These selections all result in the same committee, so they are all equivalent to a single combination.
That's why the combination formula includes the division by n!, so
C(5,3) = P(5,3) / 3! = (5 x 4 x 3) / (3 x 2) = 10

Hope that clears it up. I completely agree with you that understanding the concept behind it is a much more solid approach than just memorizing the formulas. Once you understand the concept, you can reconstruct the formulas very quickly, even if you forget them under pressure. Also, if you can "map" the problem to one of the two scenarios above, you should have no problem picking the correct formula to use.

[ravsav]

Hi all,

I am seeing that twice in the above posts nCr has been equated to n!/n!n-r!.
Actually nCr = n!/r!n-r!

My take on the difference in the formula i.e., r! appearing in the denominator of the Combination formula is that it takes care of the extra arrangements where order is not important. But then Ursula has done a great job with the fitting example.
Thanks,
ravsav.

[n_adroja]

Hi Dave,
First of all, you got the Combination and Permutation mixed up - but I guess that was the whole point of your post

I came up with this mnemonic device to keep these straight:
P=Prizes (permutations)
C=Committee (combinations)
Here's the full story:

[/SIZE]Permutations ("Prizes")[/SIZE]
Let's say you have 5 people who are running a race, and you want to know in how many ways three prizes (gold, silver, and bronze medal) could be awarded.
Any of the 5 could win the gold, any of the remaining 4 could win silver, and any of the other 3 could win bronze.
So you get 5 x 4 x 3 possibilities.
You can get this result using the permutation formula:
P(5,3) = 5! / (5-3)! = (5 x 4 x 3 x 2 x 1) / (2 x 1) = 60

Notice that the effect of the denominator in the formula is just to cancel out the last two terms from the numerator. That's why I prefer to think of it as simply an incomplete factorial where you multiply out only as many terms as you have selections. In this case, instead of the complete factorial of 5 x 4 x 3 x 2 x 1, you only have three prizes to be awarded, so you stop after the third term.

[/SIZE]Combinations ("Committee")[/SIZE]
Now think of the same 5 people, but your task this time is to form a committee of 3 (with no special roles, just equal members). You could do your selection in the same way as above, but you would find that some of these permutations give you the same committee. For example, it doesn't matter whether your selection is person A, then C, then D or whether it is C, then D, then A. So the straightforward selection process we used to award prizes for the race needs to be adapted a bit. We need to divide by the number of possible ways in which a particular committee could have been picked. This is simply the factorial of the number of committee members, in this case 3!
For example, consider these 6 permutations:
ACD
ADC
CAD
CDA
DAC
DCA
These selections all result in the same committee, so they are all equivalent to a single combination.
That's why the combination formula includes the division by n!, so
C(5,3) = P(5,3) / 3! = (5 x 4 x 3) / (3 x 2) = 10

Hope that clears it up. I completely agree with you that understanding the concept behind it is a much more solid approach than just memorizing the formulas. Once you understand the concept, you can reconstruct the formulas very quickly, even if you forget them under pressure. Also, if you can "map" the problem to one of the two scenarios above, you should have no problem picking the correct formula to use.

Hi Ursula,

I need yur help to resolve one basic question that i face in probability.
pls look at the following question

A deck of 9 cards contains 2 red cards, 3 blue cards, and 4 green cards. 3 cards are randomly drawn without replacement from the deck. What is the probability that all 3 cards are a different color?

A. 2/9
B. 3/20
C. 1/5
D. 2/7
E. 8/243

Now one way to solve this is by the following method:-
(2c1*3c1*4c1) / 9c3 = 2/7

however, there is also one more approach.
three ways of choosing RBG is 2/9*3/8*4/7 = 1/21.

why do this ans not ,match the previous one?

I believe this is because I am not considering the other possibilities like rbg, grb,gbr, brg,bgr etc... which in all are 6 possibilitie so 6*1/21 = 2/7.

My question is why do I need to consider these possibilities? in either case I have 1 R 1 G and 1 B. so why should the oder matter?

Pls help .. this is getting on my nerves.
Thanks
adroja

[ursula]

however, there is also one more approach.
three ways of choosing RBG is 2/9*3/8*4/7 = 1/21.

why do this ans not ,match the previous one?

I believe this is because I am not considering the other possibilities like rbg, grb,gbr, brg,bgr etc... which in all are 6 possibilitie so 6*1/21 = 2/7.

My question is why do I need to consider these possibilities? in either case I have 1 R 1 G and 1 B. so why should the oder matter?

You are correct that you need to multiply by 6. The reason for this is that if you use the probabilities approach, you need to take into account all the ways in which a favourable outcome can occur. Notice that the question doesn't say you must choose R first, then G, then B. To be systematic, you would need to list all of the favourable outcomes like this:
p(R G B)=2/9 * 3/8 * 4/7
p(G R B)=3/9 * 2/8 * 4/7
p(G B R)=...
p(B R G)=
p(B G R)=
p(R B G)=
Note that on each line you have the same numerators and denominators, just lined up in different ways. So when you add them all up you end up with just 6 * (2/9*3/8*4/7).

By the way, this is similar to rolling a total of 11 using 2 dice. You need a 5 and a 6. You could get a 5 on the first die and a 6 on the second, or the other way around. Both events are favourable outcomes, so you need to add up their probabilities to arrive at the total probability of rolling 11.

[neokeynesian]

Hi guys,
Please visit this old website for combination & permutation
http://www.TestMagic.com/forum/topic.asp?TOPIC_ID=1699

[diehard800]

i m late

[gmatrookie1]

The link did not work.

The explanation was very helpful - ursula.

Thanks