Sponsored Ad:
Page 1 of 2 12 LastLast
Results 1 to 10 of 12

Thread: Combination vs Permutation formula

  1. #1
    Trying to make mom and pop proud
    Join Date
    Jun 2004
    Location
    USA
    Posts
    24
    Rep Power
    11


    Good post? Yes | No
    Sponsored Ad:
    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.

  2. #2
    Searching for my Univ rishim's Avatar
    Join Date
    Mar 2004
    Location
    India
    Posts
    170
    Rep Power
    11


    Good post? Yes | No
    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

  3. #3
    Trying to make mom and pop proud shashibg's Avatar
    Join Date
    Jun 2004
    Location
    India
    Posts
    13
    Rep Power
    11


    Good post? Yes | No
    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)!


  4. #4
    Late bloomer ursula's Avatar
    Join Date
    Mar 2004
    Location
    Canada
    Posts
    482
    Rep Power
    12


    Good post? Yes | No
    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.

  5. #5
    Trying to make mom and pop proud
    Join Date
    Sep 2004
    Posts
    22
    Rep Power
    11


    Good post? Yes | No

    Re: Combination vs Permutation formula

    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.

  6. #6
    An Urch Guru Pundit Swami Sage
    Join Date
    Aug 2004
    Posts
    516
    Rep Power
    13


    Good post? Yes | No

    Re: Combination vs Permutation formula

    Quote Originally Posted by 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.
    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

  7. #7
    Late bloomer ursula's Avatar
    Join Date
    Mar 2004
    Location
    Canada
    Posts
    482
    Rep Power
    12


    Good post? Yes | No

    Re: Combination vs Permutation formula

    Quote Originally Posted by n_adroja
    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.

  8. #8
    Within my grasp!
    Join Date
    Jul 2004
    Posts
    110
    Rep Power
    11


    Good post? Yes | No

    Re: Combination vs Permutation formula

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

  9. #9
    Never say Die diehard800's Avatar
    Join Date
    Jul 2008
    Location
    New Delhi
    Posts
    300
    Rep Power
    8


    Good post? Yes | No
    i m late

  10. #10
    Within my grasp!
    Join Date
    Jun 2008
    Posts
    155
    Rep Power
    7


    Good post? Yes | No
    The link did not work.

    The explanation was very helpful - ursula.

    Thanks

Page 1 of 2 12 LastLast

LinkBacks (?)

  1. 03-02-2010, 01:12 PM

Thread Information

Users Browsing this Thread

There are currently 1 users browsing this thread. (0 members and 1 guests)

Similar Threads

  1. Replies: 5
    Last Post: 04-22-2010, 07:16 PM
  2. permutation and combination
    By shail4000 in forum GRE Math
    Replies: 4
    Last Post: 03-27-2010, 10:00 PM
  3. about permutation and combination
    By joy_Montreal in forum GRE Math
    Replies: 4
    Last Post: 01-30-2007, 10:34 PM
  4. Permutation Combination
    By kaus in forum GMAT Problem Solving
    Replies: 12
    Last Post: 01-16-2005, 04:01 PM
  5. permutation combination
    By subu in forum GMAT Data Sufficiency
    Replies: 5
    Last Post: 11-21-2003, 11:52 PM

Bookmarks

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •  

SEO by vBSEO ©2010, Crawlability, Inc.