Algebra

A Guide to Permutations and Combinations (and practice problems)

At our recent Mathcounts club meeting I decided to practice some permutations and combinations problems with the Mathletes. We were able to get most of the answers after some discussion; but the predominant feeling, I think, was that permutations and combinations involve a good deal of “black magic”—that is, we can get the answer, but we don’t always know when to multiply, divide, or factorial. That’s why I decided I need to write out the steps so that all our Mathletes can refer back to this as a guide for solving permutations and combinations problems.

There’s something you should know, though, before you start reading this expecting a foolproof method that works for every situation. These problems will require you to think, analyze, and check your work. You can’t expect to get these right if you want a formula for them. Instead, each one will ask you to use the formulas you know in new ways that you may never have thought of. And that’s one of the great things about Mathcounts: even during a competition you can still be learning. But for now, I’ll walk you through the basic steps for how to solve a permutations and combinations problem.

In this post, I’ll assume that you know how to calculate factorials and that you know what combinations and permutations are, and especially the difference between them.

Are you in a hurry? If you need to read this really quick before a competition, or you think you know most of it already (which I don’t always recommend, by the way), you at least need to look at the bold and italic headings down the page. If you have some more time, work the example problems! They are very important in understanding this material. If you just need a general practice, the problems for you are at the bottom.

Step 1. Determine what kind of problem it is.

When you’re given a problem that you know has to do with combinations, permutations, or probability, you first need to figure out which of those it is. This guide will cover the first two in detail, meaning we’ll concern ourselves with answering the question “in how many ways?”

Is it related to permutations? If it is a permutations problem, it will often contain words like “arranged,” “in a row,” or “in order.” Basically, if we’re keeping a tally of how many ways we’ve found, ABC would get a tally mark and ACB would also get one.

Example. In how many ways can eight books be arranged on a shelf?

Is it related to combinations? If it is a combinations problem, it will generally not contain the words mentioned above. Instead, these problems have to do with groups of things in ways that the order doesn’t matter. If we keep a tally, ABC, ACB, BCA, BAC, CBA, and CAB would collectively receive one tally.

Example. In how many ways can three books be chosen out of eight?

This should largely be review material so far. In some problems, though, you need to consider other things as well before you start calculating combinations and permutations. One important thing to ask yourself is,

Do I need multiple cases? Remember that permutations and combinations are limited to “x choosing y” type problems. If you need more than one of these choosings (let’s call them “cases”), you need to plan for them. If the problem asks you to combine those cases together to make a single tally, you need to multiply the results of each case. If each case makes tally marks separate from the others, you need to add the results of each case.

Example. How many integers less than 100 can be formed using the digits 1, 2, 3, and 4, with each digit used only once?

Solution. There are two cases: one-digit numbers and two-digit numbers. For one-digit numbers, there are P(4, 1) = 4 possibilities. For two-digit numbers, there are P(4, 2) = 12 possibilities. Since each case makes tally marks individually, there are 4 + 12 = 16 integers total.

Example. How many ways can ten books be arranged on a shelf if the first five must be nonfiction and the last five are fiction?

Solution. There are two cases: the arrangement of the nonfiction books and that of the fiction books. For the nonfiction books, there are P(5, 5) = 120 possibilities. The same goes for the 5 fiction books. Since the two cases must be combined to produce a single tally mark, 120 x 120 = 14400 possible arrangements.

Note that both of the above problems involved permutations. That’s because combinations require other calculations, which we’ll go into below.

Are there repeated elements in the set I have to choose from? If there are multiple items that would be indistinguishable in a solution, you have two possible things to do. If it is a permutations problem, keep it in mind until step 3, when we’ll talk about it in more depth. If it is a combinations problem, you will need to make multiple cases. Make one case where all elements are the same, one where all except one are the same, one where all except two are the same, and so on until none are the same. And watch out for cases that are the same, for example: “one the same, two different” and “all three different.” Confused? Check out this example.

Example. A box contains three red balls, two green balls, and one blue ball. In how many ways can two balls be chosen?

Solution. This is a combinations problem, because the order of the balls doesn’t matter. There are repeated elements, so we need to make multiple cases. Case 1 represents how many ways we can pick so that both balls have the same color (2 ways). Case 2 represents how many ways both balls will have different colors (3 ways). Since the cases don’t combine to make one tally mark, we add the two cases together to get 5 possible ways.

So now we’ve figured out what kinds of calculations we need to do! Give yourself a pat on the back and keep reading.

Step 2. Calculate the permutations.

For this step, I suggest that you use the “blanks” method, which is fairly versatile. It’s important that you understand how the method works, because you can modify it to model probability and combinations problems (even though the basic method calculates permutations). There are plenty of problems on this blog whose solutions involve the blanks method; please look in the “Probability” category for practice.

To calculate permutations using the blanks method, first figure out how many items you are choosing. This is the number of blanks you will use. Then for each blank, figure out how many things you have to choose from (whether some are identical or not) and write it in the blank. Finally, multiply the numbers in the blanks.

Example. In how many ways can eight books be arranged on a shelf?

Solution. This problem uses permutations, as indicated by the word “arranged.” There is only one case because each possible arrangement of all eight books is a single tally mark. Using the blanks method, we have eight blanks and eight things to choose from: 8 x 7 x 6 x 5 x 4 x 3 x 2 x 1 = 8! = 40,320 arrangements.

Example. How many 3-digit area codes are possible if the first digit cannot be zero?

Solution. This problem uses permutations, as the order of the numbers matters in an area code. There is only one case. Also, digits can be repeated. The first digit can be nine possible values, while the other two can have ten: 9 x 10 x 10 = 900 area codes.

Again, these problems only involved permutations. The extra steps for combinations will be discussed below, in step 3.

By the way, the blanks method is an easy-to-use version of the permutations formula, which is

_nP_r = \frac{n!}{(n-r)!}

The blanks method goes above and beyond the permutations formula, though. Why? Because the blanks method allows for constraints like the “first digit cannot be zero” above. Also, you can use it for probability; the numerator of the probability would be the number of permutations that satisfy the condition, and the denominator would be the total number of permutations possible.

Example. Given that area codes are three digits and the first digit cannot be zero, what is the probability that an area code will be an even number?

Solution. This problem uses permutations because the order of the number matters. We will consider the number of permutations that satisfy the condition (even) and the total number possible separately. For the first set of permutations, we have three blanks for three digits. Nine values (1-9) can go in the first blank, ten (0-9) in the second blank, and five (0, 2, 4, 6, 8) in the third. 9 x 10 x 5 = 450. The total number of possible values was found above to be 900, so 450/900 = 1/2.

That wasn’t hard, was it? Of course, you probably could have found the answer just by thinking about it. But in competition you will get a problem that you can’t model intuitively, and that’s when you’d need this method.

Still with me? Then keep reading, as we’re almost finished!

Step 3. Modify the results so that they make sense.

This is probably the hardest part of solving permutations and combinations problems (but don’t give up!). Now that you have a number of permutations, you need to transform it into an answer. To do this, we need to take each case separately and verbalize what that case represents, and what answer you have from the number of permutations. Usually, if the problem isn’t asking for straightforward permutations (as in the above examples), you will need to divide by something to eliminate “tallies” that count the same thing twice. For example, if each answer is counted twice, you will need to divide by two.

Does the case represent combinations? If the solutions for the case in question are the same if they are rearranged, you will need to divide the number of permutations by the factorial of the length of each solution. For example, if each solution consists of three elements (like ABC), we would divide by 3! = 6. This makes sense because ACB, BAC, BCA, CAB, CBA are all counted in addition to ABC, and we want to get rid of them.

Example. In how many ways can a set of five books be chosen if the first two are to be chosen from a pile of three nonfiction books, and the other three are to be chosen from a pile of five fiction books?

Solution. This problem will require combinations, as the order of the books does not matter. There are two cases: one concerning the first two books, and one concerning the other three. For the first case, the blanks method gives 3 x 2 = 6; for the second, the blanks method gives 5 x 4 x 3 = 60. Now we need to take each case separately and make sure it represents the right value. For the first case, we need to divide by 2 because we’re asked for combinations and there were two blanks: there are 6/2 = 3 combinations. For the second case, we need to divide by 3! = 6 because there were three blanks, giving 60/6 = 10 combinations. We then need to multiply 3 and 10 because those two cases combine to make one tally mark (see step 1 for more about this), giving an answer of 30 possible ways.

Additional note. So as I was solving this example problem, a question occurred to me: do we need to divide anything at the end, after we combine the two cases? The answer to the question is no. To explain why, let’s say the three nonfiction books are labeled A, B, and C, and the five fiction books V, W, X, Y, Z. A solution that earns a tally mark might look like ACVWX, BCVWX, or ACWXZ, to name a few. We don’t have to eliminate any more permutations because we have not made tallies for the permutations that mix the two types of books up, like WVAXC. You’ll need to be thinking about nuances like this as you solve problems, because a single slip-up can change your answer by hundreds or thousands!

If it’s a permutations problem, are there repeated elements in the set to choose from? Back in step 1, I told you to stick around until we got here to take care of the repeats in a permutation problem. Well, here we are! Luckily, it’s easier than dealing with repeats in a combinations problem. All you have to do is divide the number of permutations by the factorial of the number of repeats. For instance, if there were four A’s in the set, you would divide by 4! = 24. You divide for each different element that is repeated. Study the example to see this in action.

Example. How many permutations of four letters can be made from the word MISSPELLED?

Solution. There is only one case, as we are directly asked for a number of permutations. Using the blanks method, we have 10 things to choose from and 4 blanks: 10 x 9 x 8 x 7. Since I don’t have a calculator, let’s go on to step 3 and see if we can divide some things out. There are 2 S’s, 2 E’s, and 2 L’s in the word, which means we need to divide by 2 three times. \frac{10\times9\times8\times7}{2\times2\times2}=5\times9\times2\times7=630. So the answer is 630, providing the word isn’t misspelled… wait, what?

Step 4. Check your work and verify that the answer makes sense.

Finally, you have an answer. Take a deep breath and enjoy the victory of having conquered a tough math problem. But before you move on, double check to make sure your answer is logical. Make a few sample solutions to see if they really satisfy the conditions in the problem. Most importantly, make sure you haven’t left out any solutions, because these errors are the hardest to catch. I won’t give you any examples for this specifically, but I hope you’ll take my advice and check your work on the problems at the end of this post.

And finally… Practice!

  1. Mrs. Anderson has to choose a group of two boys and two girls to represent her class. If there are six boys and eight girls in the class, how many groups are possible?
  2. In the imaginary country of Mathematica, a ZIP code is five digits long. The first digit must be a prime number, the third digit must not be 0, and the last digit must be even or zero. How many ZIP codes are possible for this country?
  3. A hand of four cards is dealt from a standard 52-card deck. What is the probability that it contains at least one ace? (Hint: Find the probability of it containing no aces first.)
  4. How many positive integers less than 700 can be made using only digits that are prime numbers? (Hint: Make a case for each possible number of digits.)
  5. How many even positive integers can be made using the digits 1, 2, and 4, using each digit only once?
  6. There are 7 red marbles, 2 blue marbles, and 1 green marble in a jar. In how many ways can three marbles be selected from the jar, if two marbles of the same color are identical?

Answers. To check your answers for these problems, decode the letters using the alphabet code A=0, B=1, etc.

  1. ECA
  2. BIAA
  3. A.CIB
  4. GI
  5. I
  6. G

If you didn’t get all those problems right, then you need to check out the other problems on this website. But the most important thing is to treat these problems like a good challenge. Each problem asks you to think, even if it boils down to counting on your fingers. So have fun!