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

[pablo esqyoobar]

according to this problem, does anybody know why the probabilities are added at the end then divided by 5! ??

 

chidcguy's first solution answers a different question: 'what is the probability that at least one couple is separated'? We need both couples to be separated, of course. As Motherjane and durgesh point out above, we can use chidcguy's result and method to get the answer- it's an interesting solution to the problem, I think.

 

 

Motherjane wrote:TWO couples and a single person are to be seated on 5 chairs such that no couple is seated next to each other. What is the probability of the above??

 

A] 1/5

B] 2/5

C] 3/5

D] 4/5

E] 1/20

 

It's often easiest to break down the problem into cases- it's a technique we use all the time in counting problems. Let's call the single person S. S must be in the 1st, 2nd, 3rd, 4th or 5th seat:

 

-If S is in the first seat - 1 choice

-then anyone else can be in the 2nd seat: 4 choices

-in the 3rd seat, cannot be the partner of the person in the 2nd seat: 2 choices

-in the 4th seat: must be the partner of the person in the 2nd seat- 1 choice

-fifth seat: must be the partner of the person in the 3rd seat- 1 choice.

 

So if S is in the first seat, we have 1*4*2*1*1 = 8 arrangements. Notice we'll get the same answer when S is in the fifth seat.

 

It's just as fast to count the arrangements with S in the second/fourth seat (8 arrangements for each) and third seat (16 arrangements), which gives us 8+8+16+8+8 = 48 arrangements in total. So the answer must be 48/5! = 2/5.

 

There are many other ways to look at the problem, but to be honest, I'd llkely do the above case analysis on a real GMAT- it's sure to work, and it's quick enough. I don't see a "five second solution" to the problem, but there may well be one.

[thizzy]

Hey I need some help, I've read some of how combinations work but I'm still confused because I wasn't taught this before but I'm expected to know it.

 

So I have a couple of questions and I want some help with formulas.

 

A combination menu has 4 choices for the appetizer, 2 for entree and 3 for dessert. How many meals can be chosen?

 

A canadian postal code has 6 characters with the first, third and fifth as letters and the second, fourth and six characters being numbers.

 

a) How many postal codes are possible

b) The first two postal codes locate the regional post office; How many can the last 4 characters pinpoint?