Easy Permutations and Combinations

I’ve always confused “permutation” and “combination” — which one’s which?

Here’s an easy way to remember: permutation sounds complicated, doesn’t it? And it is. With permutations, every little detail matters. Alice, Bob and Charlie is different from Charlie, Bob and Alice (insert your friends’ names here).

Combinations on the other hand, are pretty easy going. The details don’t matter. Alice, Bob and Charlie is the same as Charlie, Bob and Alice.

Permutations are for lists (order matters) and combinations are for groups (order doesn’t matter).

Permutations: The hairy details

Let’s start with permutations, or all possible ways of doing something. We’re using the fancy-pants term “permutation”, so we’re going to care about every last detail, including the order of items. Let’s say we have 8 people:


1: Alice
2: Bob
3: Charlie
4: David
5: Eve
6: Frank
7: George
8: Horatio

How many ways can we pick a Gold, Silver, and Bronze medal for “Best friend in the world”?

permuation_medals.png

We’re going to use permutations since the order we hand out these medals matter. Here’s how it breaks down:

  • Gold medal: 8 choices: A B C D E F G H (Clever how I made the names match up with letters, eh?). Let’s say A wins the Gold.
  • Silver medal: 7 choices: B C D E F G H. Let’s say B wins the silver.
  • Bronze medal: 6 choices: C D E F G H. Let’s say… C wins the bronze.

We picked certain people to win, but the details don’t matter: we had 8 choices at first, then 7, then 6. The total number of options was 8 * 7 * 6 = 336.

Let’s look at the details. We had to order 3 people out of 8. To do this, we started with all options (8) then took them away one at a time (7, then 6) until we ran out of medals.

We know the factorial is: \displaystyle{8! = 8 \cdot 7 \cdot 6 \cdot 5 \cdot 4 \cdot 3 \cdot 2 \cdot 1 }

Unfortunately, that does too much! We only want 8 * 7 * 6. How can we “stop” the factorial at 5?

This is where permutations get cool: notice how we want to get rid of 5*4*3*2*1. What’s another name for this? 5 factorial!

So, if we do 8!/5! we get:

\displaystyle{\frac{8!}{5!} = \frac{8 \cdot 7 \cdot 6 \cdot 5 \cdot 4 \cdot 3 \cdot 2 \cdot 1}{5 \cdot 4 \cdot 3 \cdot 2 \cdot 1} = 8 \cdot 7 \cdot 6}

And why did we use the number 5? Because it was left over after we picked 3 medals from 8. So, a better way to write this would be:

\displaystyle{\frac{8!}{(8-3)!}}

where 8!/(8-3)! is just a fancy way of saying “Use the first 3 numbers of 8!”. If we have n items total and want to pick k in a certain order, we get:

\displaystyle{\frac{n!}{(n-k)!}} just means “Use the first k numbers of n!”

And this is the fancy permutation formula: You have n items and want to find the number of ways k items can be ordered:

\displaystyle{P(n,k) = \frac{n!}{(n-k)!}}

Combinations, Ho!

Combinations are easy going. Order doesn’t matter. You can mix it up and it looks the same. Let’s say I’m a cheapskate and can’t afford separate Gold, Silver and Bronze medals. In fact, I can only afford empty tin cans.

How many ways can I give 3 tin cans to 8 people?

Well, in this case, the order we pick people doesn’t matter. If I give a can to Alice, Bob and then Charlie, it’s the same as giving to Charlie, Alice and then Bob. Either way, they’re going to be equally disappointed.

This raises and interesting point — we’ve got some redundancies here. Alice Bob Charlie = Charlie Bob Alice. For a moment, let’s just figure out how many ways we can rearrange 3 people.

Well, we have 3 choices for the first person, 2 for the second, and only 1 for the last. So we have 3 * 2 * 1 ways to re-arrange 3 people.

Wait a minute… this is looking a bit like a permutation! You tricked me!

Indeed I did. If you have N people and you want to know how many arrangements there are for all of them, it’s just N factorial or N!

So, if we have 3 tin cans to give away, there are 3! or 6 variations for every choice we pick. If we want to figure out how many combinations we have, we just create all the permutations and divide by all the redundancies. In our case, we get 336 permutations (from above), and we divide by the 6 redundancies for each permutation and get 336/6 = 56.

The general formula is

\displaystyle{C(n,k) = \frac{P(n,k)}{k!}}

which means “Find all the ways to pick k people from n, and divide by the k! variants”. Writing this out, we get our combination formula, or the number of ways to combine k items from a set of n:

\displaystyle{C(n,k) = \frac{n!}{(n-k)!k!}}

A few examples

Here’s a few examples of combinations (order doesn’t matter) from permutations (order matters).

  • Combination: Picking a team of 3 people from a group of 10. C(10,3) = 10!/(7! * 3!) = 10 * 9 * 8 / (3 * 2 * 1) = 120.
    Permutation: Picking a President, VP and Waterboy from a group of 10. P(10,3) = 10!/7! = 10 * 9 * 8 = 720.
  • Combination: Choosing 3 desserts from a menu of 10. C(10,3) = 120.
    Permutation: Listing your 3 favorite desserts, in order, from a menu of 10. P(10,3) = 720.

Don’t memorize the formulas - it’s better to know why they work. Combinations sounds simpler than permutations, and they are. You have fewer combinations than permutations.


Posted February 12, 2007, under Math
Tags:
Related Posts:
  • How To Understand Combinations Using Multiplication
  • Explanations for everyone.
  • Understanding the Birthday Paradox
  • Marketing Lessons from InstaCalc.com
  • Combining Simplicity and Complexity
    • Like it? Share on:
    • StumbleUpon
    • Digg
    • del.icio.us
    • Reddit
    Tools of the trade:
    Book Cover
    Don't Make Me Think
    (Web Design)
    Book Cover
    On Writing Well
    (Writing Style)
    Book Cover
    MS Office 2007
    (Charts & Diagrams)

    124 Comments »

    Trackbacks & Pingbacks

    1. Pingback by Understanding the Birthday Paradox | BetterExplained — April 26, 2007 @ 12:33 am

    2. Pingback by Another Good article on Permutation and Combination - The TestMagic Forums — April 23, 2008 @ 12:06 pm


    Comments

    1. Thanks alot! This was actally a better explanation then my teacher could give us =]

      PJ — May 3, 2007 @ 7:33 pm

    2. Awesome! Glad you found it useful :)

      Kalid — May 3, 2007 @ 10:14 pm

    3. finally this makes sense

      Anonymous — May 10, 2007 @ 7:13 am

    4. this is an awesome site!

      Kenny — May 22, 2007 @ 4:08 pm

    5. Thanks a million! It makes sense now!

      Sheri — May 25, 2007 @ 10:31 am

    6. Thanks for the comments, glad you found it useful.

      Kalid — May 25, 2007 @ 11:53 am

    7. If my chances are 1 in 13 million of winning the lottery and I buy 10 tickets, do my chances increase?

      D Cooper — June 5, 2007 @ 6:18 am

    8. Hi D, when you buy multiple tickets you would add up the chances. So 10 tickets would be 1/13,000,000 + 1/13,000,000 + 1/13,000,000 … = 10 / 13,000,000

      So buying multiple tickets would increase your chances for that particular lottery. If you somehow bought half of the available tickets, you’d have a 50-50 chance. And if you bought all of the tickets you’d win :) .

      Kalid — June 5, 2007 @ 10:40 am

    9. I’m having a stupid moment. I have a problem: how many combinations exist when one needs to select a team of 22 players from a squad of 40 players?

      IS this 40!/22!(18!) = 113,380,261,800?

      It seems a rediculaously large number! Please help me!

      R David — July 17, 2007 @ 7:03 am

    10. Hi David, yep, you got the formula right. The number of permutations (ways to order 22 people of 40) is:

      40 * 39 * 38 … * 24 * 23 * 22 * 21 * 20 * 19 * 18 = 40! / 18!

      The number of ways to re-arrange 22 people = 22!

      So we divide the first by the second and get

      40!/18!(22!) = 113,380,261,800

      113 billion does seem huge, but there’s a lot of multiplications happening. There’s 56 ways to pick 3 people from 8, which seems pretty large as well.

      It’s one of those things where human beings (all of us!) aren’t great at intuitively estimating the impact of exponential growth. The birthday paradox and the effect of compound interest are other examples of this. I think it’s because we don’t encounter such mind-boggling growth or large numbers in a way we can really experience (at a certain point, millions, billions, and trillions become “a lot”, even though a trillion is a *million* times bigger than a million).

      Kalid — July 19, 2007 @ 2:29 am

    11. Great Stuff! You should write a book!

      Aaron Chaon — July 30, 2007 @ 4:42 pm

    12. Thanks for the encouragement Aaron! Once I have enough posts I would love to turn it into a book :)

      Kalid — July 31, 2007 @ 3:15 pm

    13. it was really useful dude!!!
      thnx a lot!!!

      Dheeraj — August 1, 2007 @ 3:05 am

    14. No problem, glad it helped!

      Kalid — August 2, 2007 @ 2:39 am

    15. I play in a fantasy footfall league. I can select players for my team and they each earn points based on their performance in each weeks actual football game. I compete against other teams owners in my league and the owner with the most points each week wins. Also the points earned each week are totaled at the end of the year and the owner with the most points wins the annual point competition.
      Of course there are limitations and rules to the game. Of all the players listed I may select only 22 players. Of the 22 players the team must be composed of:

      3 quarterbacks (QB)(58 QBs)
      6 running backs (RB)(81 RBs)
      6wide receivers (WR)(125WRs)
      2 tight ends (TE)(56 TEs)
      3 kickers (K)(37Ks)
      2 defenses (D)(32Ds)

      Also each player is assigned a salary and my salary limit for the team is $60,000,000.00 for all 22 players.
      I can trade for additional players each week but I’m limited to 120 trades for the year.

      Here is the question?:

      ??? Of all the players available which ;
      2QB+6RB+6WR+2TE+3K+2D whose total salary does not exceed $60,000,000 will generate the most projected points?????

      The program should list the top 20 combinations in descendinding order of points.

      Attached is a file that lists all players available. Of all the columns available the only ones used will be Name (player), Salary (in thousands) and PNTS ( projected points for the in todays game).

      I think your program PermutCombine will do some of the work but I’

      Thanks again for your interest. Sam Eismont

      sam eismont — August 23, 2007 @ 10:44 am

    16. if a train has 18 cars , and 3types of cargo must be transported, how many ways can the 3 types be transported if one type of cargo can at most occupy only ten cars per train?

      Tom — August 29, 2007 @ 1:49 am

    17. Thanks alot!!!!
      am studying n i have an exam 2mmorow !!
      thnx 4 helpn me

      Besho — September 24, 2007 @ 3:36 pm

    18. Hi Besho, I’m glad I was abble to help!

      Kalid — September 27, 2007 @ 9:23 am

    19. 10 pairs of shoes are well mixed up.4 shoes are randomly picked. What is the probablity of getting at least 1 complete pair

      Sahil — September 30, 2007 @ 12:12 am

    20. This is really an excellent way of explaining the things!!!

      Pras — October 2, 2007 @ 6:03 am

    21. Hi Pras, thanks for the comment!

      @Sahil: It’s a good question, but I want to make sure I’m not doing someone’s homework for them :) .

      In general, it’s easier to find the chance of “zero matches” and subtract this from 1, vs. finding the chance for 1 match.

      So let’s find the chance for zero matches. Imagine picking your first shoe, A: nothing special here, you aren’t going get the match on a single shoe.

      You pick shoe B: You have a 18/19 chance of getting zero matches (only A’s partner would match, of the 19).

      You pick shoe C: You have a 16/18 chance of zero matches (only A and B’s partner would match, of the remaining 18).

      You pick shoe D: You have a 14/17 chance of not getting any matches (only A and B and C’s partner would match, of the remaining 17).

      If you multiply these chances you get the total chance for zero matches. Subtract from zero to get the chance for any match. At least I think that’s how it goes :)

      Kalid — October 2, 2007 @ 7:55 am

    22. hey
      I was about to crazy solving this sum which i now find was actually so simple thanks :)

      safa — October 6, 2007 @ 3:32 am

    23. I feel the answer to this is simple but i am just not able to get it..
      In an examination there are three multiple choice questions and each question has 4 choices. The number of sequences in which a student can fail to get all answers correct is..

      safa — October 6, 2007 @ 3:37 am

    24. Hi Safa, for that question it helps to take it one step at a time.

      In a test with only 1 question, how many ways can you be wrong? 3. (Suppose the right answer is D… you could answer A, B or C).

      Now how about 2 questions? Well, you have 3 ways to get the first question wrong, and another 3 ways to get the second one wrong. So the total is 3 * 3 = 9. (Let’s say the right answer is D and D. Then AA AB AB BA BB BC CA CB CC are all wrong).

      Similarly, if you have 3 questions, then there is 3 * 3 * 3 = 3^3 = 27 ways to get all answers wrong. (You can write it out but will take a while: AAA AAB AAC ABA ABB ABC ACA ACB ACC… you get the idea :) )

      Hope this makes sense,

      -Kalid

      Kalid — October 6, 2007 @ 7:58 am

    25. thanks too much
      i understood it
      thanks again

      Anonymous — October 24, 2007 @ 11:38 am

    26. Nice explanation. I was wandering if you could explan some more about COUNTING….

      Thanks..
      splitline..

      splitline — October 30, 2007 @ 8:00 pm

    27. Hi Splitline, thanks for the suggestion — I may cover counting in the subject of an upcoming article.

      At a high level, to count the number of ways to do something, you multiply all the choices together. So, if you want to count how many ways to get 3 cards in poker, you’d do 52 (first option is to pick any card) times 51 (second option is any of the remaining cards) times 50 (third option is any of the leftover cards).

      This is the general idea — a full article may be needed to make it more clear.

      Kalid — October 30, 2007 @ 11:06 pm

    28. It was a very useful site,indeed!

      Geetha — November 14, 2007 @ 10:25 am

    29. Thanks Geetha!

      Kalid — November 14, 2007 @ 1:02 pm

    30. Hi
      I would appreciate if you answer this:
      A survey question has 6 answers, you can choose a single answer or any combination from the 6. How many possible combinations are there?
      Thanks a lot
      Hany

      Hany — November 15, 2007 @ 7:30 am

    31. Hi Hany, this question is a bit different. In this case you have 2 choices (use or don’t use the question), and you make this decision 6 times. So the number of possibilities is

      2 * 2 * 2 * 2 * 2 * 2 = 2^6 = 64.

      Kalid — November 15, 2007 @ 11:03 am

    32. Thank you very much Kalid, you made my day!
      What is the exact term for this type of calculation?
      Now, I want to put a formula for this in Excel to automatic coding of the 64 possibilities; is there a way to do that?

      Thanks a lot
      Hany

      Hany — November 16, 2007 @ 10:20 am

    33. didn’t help, im more confused

      Anonymous — November 17, 2007 @ 9:58 pm

    34. Sorry it didn’t work for you — try to forget it if you’ve become more confused :) .

      This is more of a refresher for people that learned combinations and permutations but then later forgot the formula [like me]. If you’re learning this in class, try running through a few examples in your textbook.

      Kalid — November 18, 2007 @ 1:26 am

    35. Please help! How many combinations of wins are there in 12 football games?

      Kathleen — November 18, 2007 @ 3:38 pm

    36. Is this part of a field called ‘combinatorics’ or is that something totally different?

      If so, could you do another explanation in that field, I have been reading your posts and this one and the ones on e and ln are terribly interesting.

      Jon — November 19, 2007 @ 2:59 pm

    37. @Kathleen: I’m not sure if I understand the question.

      If counting the number of sequences [Win-win-win-lose-lose…], you can win or lose each game. You have 2 choices at each game, and 12 games, so there are 2^12 = 2048 possibilities total.

      If you’re counting the number of different records (6-6, 12-0, etc.) then there are only 13: 12-0, 11-1, 10-2 … 1-11, 0-12 [it’s 13 because we’re counting down to 0, not 1].

      @Jon: Glad you liked the articles! Combinatorics is about the number of ways to “count” something (from the wikipedia article), so permutations and combinations would fall under that title.

      Permutations/Combinations also occur in statistics, when you try to find the likelihood of a certain event happening out of all possible events [and you need to count the number of possible events].

      Given the counting questions here, I’ll add another combinatorics article to my topic list :)

      Kalid — November 19, 2007 @ 3:09 pm

    38. Thank you very much Kalid.
      I started as a philosophy major, and decided to go into computer science/A.I. for my master’s where I have been discovering an unexpected love for the beauty of mathematics. And it makes me smile to see sites like this one with open forums and quick feedback for interesting topics. Thank you again, and this will definately be a site I check regularly!

      Jon — November 21, 2007 @ 11:57 pm

    39. Hi Jon, thanks for dropping by! You’re more than welcome — there’s so much beauty in math, programming and other topics that is often buried under dense proofs. I’m glad you like the site, I want it to be an open forum for learning :)

      Kalid — November 22, 2007 @ 7:59 am

    40. Great posts… but I have another question:

      How many 4-letter combinations are there of the letters in each word? a) ONOWAY b) OSBORNE c) OUTLOOK

      I’ve been fighting with this for about 3 hours now. The answers in the text are a) 11 b) 25 c)15

      I can’t figure out how to manipulate the formula to account for the duplicate letters. please Heelllllp :)

      Chris — November 24, 2007 @ 11:31 pm

    41. Hi Chris, great question. This is a tricky one that had me thinking for a bit. Consider a) ONOWAY at first. Pretend that the “O”s are different: there’s O1 and O2.

      To find regular 4-letter combinations, do

      C(6,4) = 15. That assumes the “O”s are different. Because they are the same, we need to subtract duplicate items like

      “O1″WAY and “O2″WAY

      How many duplicates do we have? Well, we find the number of ways to have an O and some combination of the remaining letters. We need an O + 3 other letters (chosen from 4):

      C(4,3) = 4

      Once we subtract off the duplicates we get:

      C(6,4) - C(4,3) = 15 - 4 = 11

      For b), we would do

      C(7,4) - C(5,3) = 35 - 10 = 25

      I’ll leave c) up to you :) .

      Kalid — November 26, 2007 @ 4:26 pm

    42. I have stumped by this one! Can anyone help, please?
      Lisa lost the combination to the safe where the
      secret cookie recipe is held. She sent for
      Bill Becker, the most prolific safecracker
      in the prison system, and offered him a
      royal pardon if he succeeded in opening
      the safe.

      After several attempts at bypassing the
      combination, Bill realized that the only
      way to open the safe is to try every possible
      combination by hand. The special lock
      has a four-character code. Two of the
      characters must be letters, and the lock is
      case sensitive (with AB not the same as

      ab). The other two must be digits,
      anything from 0 to 9.

      What is the maximum number of
      combinations that Bill would have to
      try before finding the correct code?

      murali — November 27, 2007 @ 2:14 pm

    43. Thankz kalid, The site is so very cool.I am glad to visit this.

      Giridhar — November 29, 2007 @ 2:06 pm

    44. Thanks Giridhar, glad you found it :)

      Kalid — November 29, 2007 @ 2:27 pm

    45. 1.How many different creations can you create all together using one ice cream flavor and at least one mix-in. (there are 52 flavors and 33 mixins)

      2. How many different combinations of pizzas can you make using at least one topping including crust options. ( 5 crusts, 17 toppings)

      Anonymous — November 29, 2007 @ 6:04 pm

    46. my question is the one above! i need help.. asap thanks

      katie — November 29, 2007 @ 6:19 pm

    47. Thanx a bunch, loved it!

      Naushad Ali — December 1, 2007 @ 5:52 am

    48. @katie: This sounds a bit like a homework problem; I think I’ll have to do a follow-up on counting techniques.

      @Naushad: Awesome, glad it helped :)

      Kalid — December 1, 2007 @ 10:01 am

    49. I have a hw problem that seems to involve both permutation and combination. Can you make any suggestions on how to put it all together? :
      100 people / 4 prizes; two of “this”, and two of “that”. How many ways to award the prizes if a person “x” wins one of “that”.
      So, I see that there are 99 left in the pool, and that two of the prizes of the 3 remaining are the same, so combination is in needed and permutation. But how?

      Dennis — December 1, 2007 @ 1:31 pm

    50. Sorry, THANKS!

      Dennis — December 1, 2007 @ 1:32 pm

    51. Hi Dennis, I’ll take a quick stab. If I understand right, there’s 100 people and two prizes (A and A) and two other prizes (B and B). I assume there’s 1 prize per person.

      First, just think about giving out 4 random prizes (A B C and D). You’d just pick 4 winners from 100: P(100,4)

      This is a permutation because the order matters — prize A is different from prize D.

      However, this doesn’t take the duplicate prizes into account. There’s 2 ways to arrange the Bs. There’s 2 ways to arrange the As. So, we need to divide by 4 to handle these combinations (2 is simple enough no formula is needed, but technically 2 = C(2,1)… how many ways can you pick 1 item (the item to swap) from 2?).

      (Note: if all prizes were the same, we’d divide by 4 * 3 * 2 * 1, instead of 4, and end up turning the permutation formula into a combination).

      Hope this helps. (And hopefully I didn’t mess it up).

      @Katie: I realize I should give you a hint to get started.

      For the ice cream, you’re going to get quite a large number. First, you have 52 choices for ice cream.

      Next, for each mix-in you can decide to leave it in our out. That is two options per mixin, for 2^33 options total. You need to subtract 1 because you can’t leave all the mixins out. So you’d have something like
      52 * (2^33 - 1) which is a pretty large number.

      The pizza question would be similar.

      Kalid — December 2, 2007 @ 1:28 am

    52. Thanks for your time Kalid (on Sunday nonetheless). You know, now with just 3 weeks to go, I can safely say that Discrete Math has presented me with more headache than Linear & DifEq combined….lol.
      OK, I’m still uncertain. 1 of four is accounted for. Thus, I understand that if B,C,D were distinct then it would be as simple as P(99,3). From above, my little mind extracted P(99,3)/2 since two of the prizes are the same. Not quite a straight Permutation or Combination??? AHHHH!

      Dennis — December 2, 2007 @ 4:10 pm

    53. P.S. To what ends does this site address. I just found it yesterday, and I’m quite impressed. I enjoyed the explanation above and the view of previous post. I have many friends coming up behind me that I will inform of this site. And as for myself, just 1 left Probability, Stats, & Modeling.
      Thanks;
      Dennis

      Dennis — December 2, 2007 @ 4:20 pm

    54. Wait a NY minute… if person “x” wins 1 of 4 prizes, and because of duplicates P(4,1)/2 = 2. Do I then get 2*P(99,3)/2 = P(99,3); again dividing by 2 for duplicates?
      Thanks.

      Dennis — December 2, 2007 @ 5:59 pm

    55. Hi Dennis, thanks for the comments. Yep, this site is about any topic that has given me or others grief, though usually on math/programming/business/communication topics (as I’m most interested in those).

      I think I just thought of an easier way. Suppose we pick the “winners” first and then hand out the prizes. There are C(99,3) ways to pick 3 winners from 99.

      Let’s call them 1, 2 and 3. We can distribute the remaining prizes (2As and 1 B) like so:

      123
      _______
      AAB
      ABA
      BAA

      So, we have 3 * C(99,3) possibilities. I think :) .

      Kalid — December 4, 2007 @ 2:15 am

    56. I don’t know what it is, but this subject is not staying in my head. I just don’t get it. I honestly can’t see the difference between the two…….I’m going crazy, but I need to learn this stuff. Help!

      Shakara — December 4, 2007 @ 6:04 pm

    57. Hi Shakara, you might have to read this explanation (and others) a couple of times. To me, I think about whether the order I pick people makes a difference. For some things (picking 1st, 2nd, 3rd) the order matters, for other things (just making a group of 3 people) the order doesn’t matter.

      If the order matters, then there’s “more ways to pick” since you could have done it one of several ways.

      Kalid — December 5, 2007 @ 4:50 pm

    58. I am having a difficult time with this and I have a test tomorrow. I’ve read several examples but my problems confuse me. My HW asks:

      How many ways can a teacher pick four students from a class of 20 to clean up after a party?

      How would I do that problem?

      Also, how do I compute P(6,3) and C(3,3)?

      I’m so lost right now.

      Frank L — December 9, 2007 @ 1:39 am

    59. Sir,

      My question is “if the probability of a company’s pen manufacturing defects were 1/10, and if 12 such pens were manufactured, what would be the probability of the following:

      1.)exactly two would be defective??
      2.)at least two will be defective??
      3.))none will be defective??

      I am not asking you to do my homework for you but i dont want to show you all the solutions i tried and take up space. just to prove i tried working on it i tackled it the following way (i am sure i am wrong).:

      ans 1 => mean = 2*(1/10),variance = 4*.1, and s.d = .2 - .4 = -.2…..now how do i get p(x=2)??/?

      PLS HELP!

      thanks and regards,

      ben

      Benjamin — December 9, 2007 @ 8:36 pm

    60. This is a really cool website and it also addresses permutatons and combinations which is my worst topic ever. Kalid I never seem to understand this topic. no matter what. The best so far has been your small intro to this topic but even after reading your explanations whenever I try new questions on this i get stuck. Can you please give a detailed post on this topic of combinatorics. I will be very very very grateful.

      Mohammad Ali — December 13, 2007 @ 4:27 am

    61. I dont know why but whenever I start doing these questions its like a wall comes up in my mind….do you think i need to think more on these questions? My basics?What could be the problem?

      Mohammad Ali — December 13, 2007 @ 4:28 am

    62. @Frank: Picking 4 from 20 would be a *combination* because you don’t care the order. In this case, you’d plug in k=4 and n=20 into the combination formula above n!/[(n-k)!k!]. k is the number of items you want, and n is the number of total items.

      @Benjamin: This is more of a stats problem, but I’ll give some high-level points. The 3) is easiest: you need to find the chances that all pens worked well. The chance of 1 pen working is 9/10, so the chance of every one working is (9/10)^12.

      For the other questions, it helps to invert. For the chance that at least 2 are defective, you can think about the chance exactly 0 or 1 pens are defective, and take the opposite probability. These can get a little tricky to compute — I’ll probably have to do a post on it.

      @Mohammad: Thanks for the suggestion, it seems people would like a more detailed look at these. I’m not an expert but have found a few techniques that work for me. A lot of familiarity comes with practice — start with easier problems and work your way up. I’ll be sure to do a post on this topic in the future :) .

      Kalid — December 13, 2007 @ 7:04 pm

    63. Here’s one i’ve been pondering since yesterday…

      —-Lining up marbles —-
      Let’s say you have 3 bags of marbles. Bag 1 has m different marbles, bag 2 n different marbles, bag3 l different marbles. You may

      How many different ways to line up the marbles in a row of 3 (you may only use 1 marble from each bag?

      Aztral — December 16, 2007 @ 12:59 pm

    64. Hi Kalid….It’s been a while. I just wanted to say thanks again. With a final on Friday 21st I’m a little nervous. I do plan to read through the site a few more times.
      Kalid, with regards to Aztral’s post (Don’t go by me Aztral)can we say:
      1) There is a total of 3 positions.
      2) Choosing form bag 1, 3 choices to place m marbles i.e. (3m)
      3) Choosing form bag 2, 2 choices to place n marbles i.e. (2n)
      4) Choosing form bag 3, 1 choice to place l marbles i.e. (l)
      Leaving us with (3m)(2n)(l)?

      This sounds like something similar to what I might see………don’t know

      Dennis — December 16, 2007 @ 10:04 pm

    65. Recursive definitions and algorithms. Any suggestions on some links.
      Thanks

      Dennis — December 16, 2007 @ 10:09 pm

    66. @Dennis/Aztral: Yep, you guys are on the right track. There’s a few different ways to think about problems like these, I really need to do a follow-up :)

      I first forget about the order the marbles. If you have 3 bags (M, N, L), then the total choices are

      M * N * L

      Using real numbers: If I have 10 Maroon marbles, 5 Navy Blue, and 3 Lime, there are 10 * 5 * 3 = 150 choices.

      But we didn’t talk about the order. For any 3 marbles, ABC, we can re-arrange them 3 * 2 * 1 = 6 times:

      ABC
      ACB
      BAC
      BCA
      CBA
      CAB

      So, we have to multiply our 150 arrangements (where M was picked first) by 6, to get 900.

      Similarly, you’d have 6 * M * N * L. You got the same result through a different path, which is great. The key is to recognize the impact of the permutation (ordering).

      Kalid — December 16, 2007 @ 10:31 pm

    67. Hi everyone.

      Thanks for the help.

      I’ve been reading up on set theory ever since, and came up with this (I also realized I didn’t state that a) the marbles are unique, b) the selected marble from bag1 always goes in the first position, marble from bag2 in the second…ie. no need to consider arrangement since they’re already arranged)

      Let’s call the bags “sacks” now ;) , so that sack1 is S1, sack2 is S2,….

      Then basically we’re just creating a new set S=S1xS2xS3. |S| = |S1|x|S2|x|S3|

      I appreciated the help :)

      Aztral — December 18, 2007 @ 7:59 am

    68. Great, glad you figured it out :) . Yep, that’s one way to look at it — if the arrangement is already fixed, you have S1 x S2 x S3.

      Kalid — December 18, 2007 @ 11:57 am

    69. I need help with this problem,

      A drawer contains eight red, eight yellow, eight green and eight black socks. What is the probability of getting at least one pair of matching socks when five socks are randomly pulled from the drawer?

      Thanks

      Jonathan — December 23, 2007 @ 6:21 pm

    70. Hi Jonathan, that’s a bit of a trick question — try doing an example where you pull out 5 random socks and see what happens :) .

      Kalid — December 24, 2007 @ 5:31 pm

    71. Great website!
      Following up on your response to #41 above…
      I am looking for a generalized formula for combinations when one has to select r items out of n items, where there can be z items that are similar in the original n items, with frequencies k1, k2, … kz.

      I saw a formula on-line that says the answer is
      n!/(k1! k2! … kz!) but this doesn’t take into account r.
      Please help!

      Also, does this class of “similar items” apply to permutations as well? If so, is there a generalized formula for permutations too, when there are z similar items in n original items, and one is taking them r at a time?

      Thanks!
      Neil.

      Neil — December 30, 2007 @ 1:40 pm

    72. Can anyone give me the answer to this question.

      HOW MANY 7 LETTER GROUPS CAN BE MADE FROM THE WORD”ARRANGEMENTS”

      Tlna — January 1, 2008 @ 10:24 pm

    73. i like it a lot

      Anonymous — January 3, 2008 @ 3:43 pm

    74. i do to

      bob — January 3, 2008 @ 3:43 pm

    75. Here is one that a number of us have been pondering for some time. Suppose I was just dealt two hearts from a standard deck of cards. What are the odds that exactly 3 of the next 5 cards dealt will also be hearts? There are 11 hearts remaining in a deck of 50 cards and I want exactly 3 of them in the next 5 cards, and the ’set’ seems to be boolean, Heart or Not. It seems like quite a different problem from standard combinations. I’ll keep working on it and let you know if I solve it.

      Dave — January 4, 2008 @ 9:49 am

    76. Number of possible hands matching my criteria is 11_C_3 * 39_C_2 = 165 * 741 = 122,265 possible hands with three more of the same suit. Divide that by the number of possible hands 50_C_5 = 2,118,760 and we see that I have 5.77% chance of getting exactly 3 more hearts. Additionally there are 12,870 remaining hands with 4 hearts and 462 remaining hands with all 5 hearts, so starting with two hearts in my hand I seem to have (122,265 + 12,870 + 462) / 2,118,760 = 6.4% chance of making a flush with suited hole cards.

      Dave — January 4, 2008 @ 10:43 am

    77. “I’ve always confused ‘permutation’ and ‘combination’ — which one’s which?”

      I was working at a quick service restaurant (we had combo meals) when I first learned combinations/permutations in school. I found it helped me to think that when a customer ordered a combo meal, just like with combinations it didn’t matter what order they received each item — just that they were all present.

      DiegoAndresJAY — January 4, 2008 @ 1:31 pm

    78. Hi Diego, thanks for the comment — that’s a nice way to visualize it.

      Kalid — January 5, 2008 @ 12:30 am

    79. Kalid,

      As a new math teacher, I’m always looking for new ways to help my students understand tough concepts. It’s nice to find someone else that doesn’t believe in just memorizing formulas. Keep up the good work; I’ll be checking in here often!

      Matt — January 11, 2008 @ 8:14 pm

    80. Hi Matt, that’s great! The world needs more teachers who focus on more than memorization :) . Good luck!

      Kalid — January 11, 2008 @ 8:25 pm

    81. The posts have been extremely useful. But I cant figure out how to work this one. If you have 5 cards and one particular card must not be at either end. I know its apermutation problem but I cant figure out what to permutate.

      Topi — January 16, 2008 @ 9:15 pm

    82. I found out the answer(48) but I still cant figure how it was worked out

      Topi — January 16, 2008 @ 9:26 pm

    83. Actually the answer is 72 and it worked out by per mutating the cards without the special card in all the different possible positions, which in this case is three. that gives 24 3 times which is 72.whew.

      Topi — January 16, 2008 @ 10:00 pm

    84. How many 4-letter combinations are there of the letters in c) OUTLOOK?

      Would you please solve this one? Thx.

      Wyner — January 17, 2008 @ 4:15 am

    85. People could skip classes and learn here instead. It’s the same thing, it not better. Great job!

      Michał Lewtak — January 26, 2008 @ 3:01 pm

    86. if*

      Michał Lewtak — January 26, 2008 @ 3:02 pm

    87. Thanks Michal, glad you liked it!

      Kalid — January 26, 2008 @ 4:46 pm

    88. Great stuff, find in great help!

      Rajesh — January 30, 2008 @ 3:47 am

    89. Thanks Rajesh, happy you found it useful.

      Kalid — January 30, 2008 @ 7:52 pm

    90. its a very helpful site for maths students

      naved — January 31, 2008 @ 12:04 am

    91. Thanks naved!

      Kalid — January 31, 2008 @ 12:07 am

    92. The customer can order pizza from 8 topping. from no topping to 8 topping. How many different kind of pizza can a customer order from no topping to 8 topping

      javad majd — February 27, 2008 @ 2:17 am

    93. thanks for this website. it helped so much. :D
      and i have a test tomorrow on it about this and i was freaking out. now this makes me feel so much confident. thanks a billion. xD

      christine — March 3, 2008 @ 7:26 pm

    94. Hang on, I need some help. it says: Art, Becky, carl, Denise, and Ed all want to go to the concert. However, there are only 3tickets. How many ways can they choose the 3 who get to go to the concert?

      i kinda know how to do it ..i just want to make sure. I wanted to make sure why it’s combination: because the order doesn’t matter right? whatever order the 5 ppl are/ the 3 tickets (since the tickets are all the same) it would be combination right?

      Christine — March 3, 2008 @ 7:32 pm

    95. @Christine: Glad the site was helpful!

      You got it — it’s a combination because the tickets are all the same. Giving tickets to Art, Becky & Carl is the same as giving it to Carl, Becky and Art.

      Now, if the tickets were different (front row, second row, and third row) then it would be a permutation since ABC (Art in the front row) is different from CBA (Carl in the front row).

      Kalid — March 3, 2008 @ 7:47 pm

    96. Hi,
      I have the following problem: Supposing I have 4 horse races and have to select the winner in each race (I can select more than 1 horse in each race) and I have selected 1 winner from race 1, and 2 winners in each of the last 3 races, is there anyway method or nice way to list out all possible permutations between these races? I know there are 8 permutations (1 X 2 X 2 X 2 = 8) but I’m trying to figure how I can write these 8 permutations out without error and without having to go through each possible sequence mentally…I know it’s relatively straightforward for only 8 perms but if there were 16 perms (2 X 2 X 2 X 2) it will be a lot more complicated and so on. Just wondering if you can think of a gerneralised method to write these down accurately.
      Race 1: A
      Race 2: B X
      Race 3: C Y
      Race 4: D Z
      I’d greatly appreciate any help on this, cheers.

      Barry G — March 5, 2008 @ 7:21 am

    97. Hi Barry, great question! I actually just wrote about this very technique:

      http://betterexplained.com/articles/how-to-understand-combinations-using-multiplication/

      One method is to turn it into an equation:

      a * (b + x) * (c + y) * (d + z)

      And that will show you all the possibilities. Calc5 can do symbolic calculations (example here).

      Kalid — March 5, 2008 @ 10:20 am

    98. Kalid, thanks a million for your answer - it’s exactly what I was looking for! Keep up the good work!

      Barry G — March 6, 2008 @ 11:19 am

    99. Hi Barry, you’re more than welcome — happy you found it useful.

      Kalid — March 6, 2008 @ 11:33 am

    100. Can u help me solvong this problem?

      A singer practiced seven different songs. he plans to sing four of them for a television program and other three for a radio special. In how many ways he can sing them? if he does not want to repeat any of the song?

      (I need it now…hope you can help me)

      migz — March 8, 2008 @ 7:21 pm

    101. thanks, I had strep and missed school and this lesson so the site really helped! =^..^=

      Kevin — March 11, 2008 @ 11:48 am

    102. @migz: Sorry, looks like a homework question — try asking your teacher!

      @Kevin: Thanks, glad it was helpful!

      Kalid — March 11, 2008 @ 12:05 pm

    103. really, this is the way one should explain the concepts. thnx a lot, lot, lot……..

      venkatesha prasad — March 22, 2008 @ 2:00 am

    104. You’re welcome Venkatesha, happy you found it useful.

      Kalid — March 22, 2008 @ 7:09 am

    105. i have question on permutation,, please if somebody could help me answer it,,, i am blank on it
      this is the question
      ” how many ways to create a line of 10 women and 6 men, but dont make two man stand each other…??”
      plsss…,, helmi, indonesian

      someone could help me please!! — March 24, 2008 @ 11:03 am

    106. I have 2 scenarios:
      1st:
      I have 99 numbers from 1-99, i have to make groups of 15 numbers, numbers can be repeated but not in same group & all numbers should not be repeated. How many such groups can be made?

      2nd:
      I have 90 numbers from 1-90, I have to make groups of 15 numbers, there should be atleast 1 number from 1-10, 11-20, 21-30, 31-40, 41-50….81-89
      How many such groups can be made?

      Ur help is highly appreciated.

      Tina — March 31, 2008 @ 2:00 am

    107. Thanks but I still don’t get it…

      Dominic — March 31, 2008 @ 8:11 pm

    108. @Tina: Sounds a bit like a homework question :) .

      Hi Dominic, sorry it didn’t help you — if you can be more specific about what parts were confusing I can try to make those sections more clear.

      Kalid — April 1, 2008 @ 12:18 pm

    109. You have a choice of 10 main dishes, 8 side dishes, and 13 desserts. How many combo’s are possible?

      I’m really stuck on this. I /think/ that k is 3, but I can’t find n for the life of me.

      Harley — April 9, 2008 @ 6:39 am

    110. thanks so much for putting this in such a simple manner. I could never make sense out of any of it until I saw ur explanation…thanks!!!

      Neemitha — April 15, 2008 @ 6:08 pm

    111. Awesome Neemitha, I’m glad it worked for you :) .

      Kalid — April 15, 2008 @ 6:37 pm

    112. Heya,
      I’m struggling to understand how combinations work with regards to binomial series and such. In post 41, using C(4,3) to determine there were 4 different ways the O could have been represent still puzzles me. Its easy to see that you could have Oxxx, xOxx, xxOx, xxxO, and so the 4 needed to be subtracted, but i still can’t make sense of the factorial approach. It comes up with coin tosses (binomial), where to choose the number of successes (n) out of ten trials is 10!/(10-n)!n!. I see that as the formula saying there are 10! possible outcomes, but really there are only 2^10? Can you make sense out of this for me please?

      Dylan — April 25, 2008 @ 9:12 pm

    113. Hi Dylan, that’s a really great question. The difference between “counting”, “ordering” and “grouping” can be really subtle and it’s confused me plenty of times.

      I consider “counting” to be finding the number of ways something could happen. Ten coin tosses does have 2^10 = 1024 ways of playing out: you have heads/tails each throw (2 choices) and multiply this 10 times.

      “Ordering” (permuations) is finding the number of ways to pick an ordered subset from a larger set: like picking gold, silver and bronze from 10 people.

      “Grouping” (combinations) finds the number of ways lets you pick an unordered subset from a larger set.

      Let’s take a look at the coin toss example. One question is “how many total possibilities are there?” With 10 throws, you have 1024 possible outcomes.

      But we actually want a different question: How many ways can I get exactly n winners? I don’t care about the *total* possibilities, I just want to count the number of ways to get exactly 3 successes, for example.

      Let’s start off easy: how many ways can we have 0 successes (aka all tails?). There’s only one way to do that: Get all tails.

      Mathematically, this is C(10,0): having 10 items and choosing none of them. In this case, 10! is the number of ways we could order the coins — we have 10 choices for the first coin in line, 9 for the next, 8 for the third, etc. It doesn’t matter if it’s coins or people: there are 10! ways to order 10 items.

      If we want to get exactly 1 winner, we have C(10,1) = 10 choices. If we want exactly 2 winners, we have C(10,2) = 45 choices, and so on. In fact, our pattern looks like this (try it out online):

      1 + 10 + 45 + 120 + 210 + 252 + 210 + 120 + 45 + 10 + 1 = 1024

      Crazy, eh? But it should make sense — the total # of ways to have 0, 1, 2 … 10 successes should be our total number of possibilities.

      Phew. So in summary, counting problems (2^10) lists out the *total* ways of doing something, while combinations/permutations let us count out specific ways of doing something. It can be confusing, so thanks for bringing it up. I think this needs to turn into a post :) .

      Kalid — April 26, 2008 @ 12:48 am

    114. Help! How many ways can you get at least 7 out of 10 answers correct on a test?

      Carolynn — April 26, 2008 @ 11:56 am

    115. Hi Carolynn, for this question you’d think about having 7, 8, 9 or 10 answers correct. So you’d have

      C(10,7) + C(10,8) + C(10,9) + C(10,10)

      Kalid — April 27, 2008 @ 2:27 am

    116. Thanks a lot for that Kalid. It still took me all day to understand and accept the distinction, think i do now.. the factorial 10! is the number of ways you could order 10 successes. if you wanted 3 successes, and you calculated P(10,7) the number would include winning the first second and third, and winning the third second and first (it dosn’t make sense to view it as a sequence of events, although it makes it clear why you would use combinations, because its impossible to have won the third before the second). this is sorted by dividing by 3!. And thats why 10! is such a large number compared to the logical 1024. Does any of that make sense, or is my reasoning flawed?

      Dylan — April 27, 2008 @ 5:13 am

    117. Hi Dylan, that’s exactly it! You explained it in terms that made sense to you, and I think you’ve got it. Permutations are really nitpicking (first, second, third is different from third, second, first) and dividing by 3! helps get rid of these similarities.

      In the case of coin flips, there’s really only 1 order, so combinations make sense. But if you just walked around and saw 10 coins on the ground (that had already been flipped), then permutations may make more sense: you could visit first, second, third or maybe second, first, third and see 3 winners each time.

      Your reasoning is right on. This is a tough distinction and it has confused me plenty of times (For example, I had forgotten that all the combinations add up to 2^10).

      Kalid — April 27, 2008 @ 9:54 am

    118. it is not what i leared!!at school.. change dis !!im just more confused then i was before!!now do something. all my friends and even my teacher said this was a bad exmple!now im sorry to be so harsh be this really sucks…Now try to think like a kid and change it..
      thank you so much my dear i love you!!!

      chole — April 29, 2008 @ 2:21 pm

    119. Hi chole, sorry it didn’t work for you. The examples are more of a review than a start from scratch — you may want to revisit them after studying the lesson in your book :) .

      Kalid — April 29, 2008 @ 2:28 pm

    120. Hi Kalid! Thank you for your awesome post!
      Can you help me with probabilities in poker?. Wikipedia says probability to get three of a kind is C(13,1)*C(4,3)*C(12,2)*C(4,1)^2, but I can’t figure out why they use combinations, and in such way… Thkx

      Enric — May 2, 2008 @ 1:00 pm

    121. YESSS!! thank god there is a website like this. this is exactly EXACTLY what i wanted.

      THANK YOU!!!

      Benjamin — May 14, 2008 @ 5:52 pm

    122. Thanks Benjamin, I’m glad it helped you!

      Kalid — May 14, 2008 @ 7:47 pm

    RSS feed for comments on this post. TrackBack URI

    Leave a comment

    Have a question? Know an explanation that caused your own a-ha moment? Write about it here.



    Subscribe (RSS or Email)
    Get new articles by email:

    Like it? Try All articles, RSS Feed or Email Subscription | Idea or suggestion? Contact me
    copyright © 2007 Kalid Azad