Probability and Statistics - Factorials, Permutations, and Combinations

Factorials, Permutations, and Combinations

To find probabilities of more complicated events, we'll need some more powerful ways of counting things. Sit down and buckle up, because stuff's about to get real.

• Factorials and Permutations

  Let's say we have two books: The Odyssey and The Iliad. We should probably have more books, but if we're only going to have two, these are a good two to have. There are two possible ways to order these books on a shelf. We can have either of these orders:

  The Odyssey, The Iliad
  The Iliad, The Odyssey

  Now let's add a third book to the shelf. We consider adding something by John Grisham, but then we decide that now isn't the time to announce that particular guilty pleasure to the world. We go with Beowulf instead. For each of the two orders above, there are three places where we could add Beowulf. We could add it at the beginning of the shelf, in the middle, or at the end:

  Beowulf, The Odyssey, The Iliad
  The Odyssey, Beowulf, The Iliad
  The Odyssey, The Iliad, Beowulf

  Beowulf, The Iliad, The Odyssey
  The Iliad, Beowulf, The Odyssey
  The Iliad, The Odyssey, Beowulf

  The number of ways to order three books is three times the number of ways to order two books: that is, 3 × 2 = 6.

  Now let's add Hamlet to the shelf. Our right brain is loving this, but it's making things awfully tough on our left brain. How many ways are there now to order these four books? Short answer: a lot. If we have three books already on the shelf, there are four places to add Hamlet: at the beginning, between the first and second books, between the second and third books, or at the end.

  Here are all the possible orders:

  Hamlet, Beowulf, The Odyssey, The Iliad
  Beowulf, Hamlet, The Odyssey, The Iliad
  Beowulf, The Odyssey, Hamlet, The Iliad
  Beowulf, The Odyssey, The Iliad, Hamlet

  Hamlet, The Odyssey, Beowulf, The Iliad
  The Odyssey, Hamlet, Beowulf, The Iliad
  The Odyssey, Beowulf, Hamlet, The Iliad
  The Odyssey, Beowulf, The Iliad, Hamlet

  Hamlet, The Odyssey, The Iliad, Beowulf
  The Odyssey, Hamlet, The Iliad, Beowulf
  The Odyssey, The Iliad, Hamlet, Beowulf
  The Odyssey, The Iliad, Beowulf, Hamlet

  Hamlet, Beowulf, The Iliad, The Odyssey
  Beowulf, Hamlet, The Iliad, The Odyssey
  Beowulf, The Iliad, Hamlet, The Odyssey
  Beowulf, The Iliad, The Odyssey, Hamlet

  Hamlet, The Iliad, Beowulf, The Odyssey
  The Iliad, Hamlet, Beowulf, The Odyssey
  The Iliad, Beowulf, Hamlet, The Odyssey
  The Iliad, Beowulf, The Odyssey, Hamlet

  Hamlet, The Iliad, The Odyssey, Beowulf
  The Iliad, Hamlet, The Odyssey, Beowulf
  The Iliad, The Odyssey, Hamlet, Beowulf
  The Iliad, The Odyssey, Beowulf, Hamlet

  The number of ways to order 4 books is

  4 × (number of ways to order 3 books) = 4 × 3 × 2.

  As we add more and more books to the shelf, the number of ways to order the books grows bigger and bigger. Yikes. We wouldn't need to deal with this if we had a Kindle.

  Anyway, if there are 5 books, the number of possible orders is

  5 × 4 × 3 × 2 × 1. (Multiplying by 1 doesn't change anything).

  If there are n books, the number of possible orders is

  n × (n – 1) × ... × 3 × 2 × 1.

  This is the product of all the numbers from n down to 1, or from 1 up to n. The fancy math name for this product is a factorial, and the fancy symbol is an exclamation mark. We like to think the symbol is an exclamation mark because this mathematical operation is so exciting!

  n factorial is defined by

  n! = n × (n – 1) × ... × 3 × 2 × 1.

  For example, 3! = 3 × 2 × 1, and 5! = 5 × 4 × 3 × 2 × 1.

  We say that 0! = 1. This sort of makes sense, because if you have no books, there's only one order in which you can put them on the shelf. True, and also a little depressing.

  As you might imagine, factorials get big really fast. Just like you and your siblings in your parents' eyes. Oy, where have the years gone?

  Before we go any further, here's a neat factorial trick. If we divide one factorial by another, a lot of stuff cancels out. For example,

  

  The fancy math word for order (yes, there's a fancy math word for basically everything) is permutation. If your hairdresser messed up royally, you might go back in to complain about your perm mutation, but we're talking about something else entirely. Sorry about your hair, though. It looks like the 1980s threw up all over you.

  There are two permutations of The Odyssey and The Iliad. One permutation is

  The Odyssey, The Iliad

  and the other permutation is

  The Iliad, The Odyssey.

  Here's another way to think of permutations, which may be helpful very soon. Hint, hint, wink, wink. We want to order 3 books on a shelf, so we must have 3 spaces on the shelf:

  

  There are three choices of book for the first space:

  

  Once we fill the first space, we have two books left to put on the shelf. There are two choices for the middle space:

  

  There's only one choice for the last space, since there's only one book we haven't put on the shelf yet:

  

  If we multiply these numbers together, we find the number of permutations (orders) of the books:

  

  To make things a little more interesting, what if we have too many books for the shelf space? What if we have 4 books, but room for only 3? Aside from changing our carpenter for building us the world's smallest bookcase, what are our options?

  

  Now there are 4 choices for the first space:

  

  Once we fill the first space there are 3 choices left for the second space:

  

  and two choices left for the third space:

  

  We multiply these numbers together for our final answer. There are

  

  ways to order 3 books when we have 4 books to choose from.

  What if we have 8 books, but room for only 5? Clearly, our carpenter is still not getting it, but besides that...what do we know?

  There are

  

  possible permutations. By the handy factorial trick, we know that

  

  If you don't believe us, work out  to see expression on the left-hand side of the equation. If you do blindly believe us no matter what we say, then...don't forget about that $100 you owe us.

  There's a formula for this stuff, of course. If we have n things to choose from and r places to fill, the number of possible permutations is:

  

  If we have 8 books and 5 places, n = 8 and r = 5, so the formula says the number of permutations should be

  

  which agrees with what we found earlier. Just one of the factorials of life.

  The number (n – r) is the number of objects we'll have left over after we fill all available spaces. Also, n! is the number of permutations if we use all n objects; dividing by (n – r)! accounts for the spaces we can't fill because we don't have them to begin with. We should be getting them any day, though. Amazon has them on back-order.

  We abbreviate "the number of permutations possible with n objects and r places" in symbols by

  .

  No, we're not giving National Public Radio a shoutout. Although it might not be so bad if we were, all things considered.

  The n comes first, because we start with n objects. Then we permute (abbreviated by the letter P) using r places. In other words, we can use the formula we had earlier:

  .

  Sample Problem

  What is ₇P₅?

  Translation time: ₇P₅ means "the number of permutations possible with 7 objects and 5 spaces." Here n = 7 and r = 5, so

  

  So far we've been looking at permutations without replacement or without repetition. So far we've been looking at permutations without replacement or without repetition. Wait...did we say that already?

  When we put an object in a space, we have fewer objects left to choose from for the next space. We wouldn't put The Odyssey on the bookshelf twice, because we only have one copy of The Odyssey and we can't repeat it. Nor do we have a copy of the modern adaptation of the masterpiece: Coming Homer.

  There are also permutations with replacement or with repetition. For these permutations, it's more like you look at an object, put it back, and look at an object (that may be the same as the first) again. Rather than choosing a new object, you may be doing a double-take. However, if you double-take a book in a bookstore, you're going to be double-charged.

  We could look at The Odyssey, put it back, and then look at The Odyssey again. If we have The Odyssey and The Iliad, and we want to look at a book, put it back, and look at another book, there are four possibilities:

  The Odyssey, The Odyssey
  The Odyssey, The Iliad
  The Iliad, The Iliad
  The Iliad, The Odyssey

  We had two books to choose from, we chose two, and we got 4 = 2² permutations.

  To summarize, if we have n objects and we choose r of them, with repetition allowed, there are

  n^r possible permutations.

• Combinations

  A combination is a selection of objects where the order doesn't matter. If you order a combination meal from McDonald's, for example, it doesn't matter if you eat the soda, fries, or burger first. One way or another, all of those calories are getting in there.

  If we take a combination of two books from The Iliad, The Odyssey, and Beowulf, the possibilities are:

  The Iliad, The Odyssey
  The Iliad, Beowulf
  The Odyssey, Beowulf

  These are the only possible two-book combinations. When we don't care about order, having The Iliad and The Odyssey is the same as having The Odyssey and The Iliad. However, you should really read them in chronological order, or you'll be totally lost. Sirens-what-now?

  To find the number of combinations, first we find the number of permutations. Then we divide by the number of ways we can rearrange the permutations. Going with the books again, here are the possible permutations of 2 books out of 3:

  The Iliad, The Odyssey
  The Odyssey, The Iliad

  The Iliad, Beowulf
  Beowulf, The Iliad

  The Odyssey, Beowulf
  Beowulf, The Odyssey

  There are 6 permutations, but only half of them count for combinations if we ignore order. Therefore, we have

  

  combinations.

  Generalizing this, if we have n objects, take r of them, and don't care about order, there are

  

  possible combinations. These formulas are looking more and more like a cat sat on our keyboard, but trust us: it works.

  First we find the number of permutations. Since each permutation can be rewritten in r! different ways, we need to divide by r! for combinations rather than permutations.

  Of course, since mathematicians like to abbreviate things, we abbreviate here too. Instead of writing "the number of combinations if we have n objects, take r of them, and don't care about order," we write (C is for combinations). See? Sometimes abbreviations and symbols are our friends. Like when our car conks out on the freeway and they come by to give us a jump.

  Here's the combination formula:

  

  Since we also know , we can do a little rewriting:

  

  The formula

  

  is what's usually given for combinations, but it's nice to know where it comes from so that we don't have more "?"s than "!"s.

  One neat thing about this formula is that, whether you choose r things or n – r things, you get the same number of combinations.

  Sample Problem

  Find  and .

  

  Now for the other one:

  

  This is the same as what we got in the second line above, so the answer is 56 here also. Don't you love being able to skip steps? Except when you get a little too cocky heading upstairs, lose your footing, and end up eating the railing?

  Our conclusion that the two are equal makes sense, because if we have 8 books and space for 5 on the shelf, we can think of the combinations in two ways. We can think that we have 8 books and need to choose 5 to put on the shelf, or we can think that we have 8 books and need to choose 3 to leave off the shelf. Either way, we find the same possibilities for the books on the shelf.

  Remember when we only had two books? It's encouraging to see our library growing. If it gets any larger, people are going to start thinking we actually read these things rather than just put them out for display.

  There are a couple more fun things to go over before we leave combinations behind: since there's only one way to choose n out of n objects if order doesn't matter, you can take all of them, which should come as welcome news to all of you possessive people out there:

  

  Also, there's only one way to choose no objects from n, which is to not take any of them:

  

  Here's a handy calculator for checking your work. Please turn it off when you're done.

  We suggest that you get comfortable doing factorials by hand, though. You never know when the teacher will decide to give a "no calculators allowed" sort of test. However, such practices are considered discriminatory by certain Texas Instruments products. Calculators aren't going to take it anymore. Too many people have been pushing their buttons for too long.

• More Probability

  Now that we can find numbers of permutations and combinations, we can find more complicated probabilities.

  Sample Problem

  A jar contains 5 vanilla candies, 9 spice candies, and 3 shrimp candies. That's what you get when you go junk food shopping in eastern Maine. What is the probability of drawing 2 vanilla candies at random from the jar, without replacement?

  There are 17 total candies. There are  possible ways to choose 2 candies from 17 (order isn't important; we don't care which vanilla candy we draw first, as long as we aren't grabbing anything seafood-flavored). The number of possible outcomes is .

  How about the number of favorable outcomes? In this case, an outcome is favorable if we pick 2 vanilla candies. It doesn't matter which two vanilla candies we pick, and there are 5 to choose from, so the number of favorable outcomes is .

  Simplifying, we see that

  

  and

  

  The final probability is

  .

  The probability that we'll need to dip our candies in cocktail sauce? Let's hope close to zero.

  Sample Problem

  A drawer contains 4 blue socks, 3 red socks, and 5 green socks. The dryer captured a couple victims during its last cycle, hence the odd numbers. Two socks are drawn at random from the drawer (without replacement). Find the probability of getting

  (a) a pair of red socks.

  (b) a pair of blue socks.

  (c) a pair of socks that are the same color.

  Answers:

  (a) 

  (b) 

  (c) A pair of socks that are the same color can be blue, red, or green. These are mutually exclusive (a pair of socks can only be one color at once, even if they're mood socks that change color to show the type of day your feet are having) so the probability of getting a pair of socks of the same color is

  (probability of a red pair) + (probability of a blue pair) + (probability of a green pair).

  The only one of those probabilities we haven't already found is the probability of a green pair, but finding that is exactly like parts (a) and (b) of this problem:

  

  To add up all the probabilities, let's get our kicks using the fractions with denominator 66. The probability of getting a pair of socks of the same color is

  (probability of a red pair) + (probability of a blue pair) + (probability of a green pair)

  or

  .