Lesson Video: Counting Using Permutations Mathematics

In this video, we will learn how to use permutations to solve counting problems.

14:43

Video Transcript

In this video, we’ll learn how to use permutations to solve counting problems.

A permutation is a rearrangement of a collection of items. For instance, let’s say we have the letters A, B, and C. We could rearrange them as ABC or BCA, BAC, and so on. Each different arrangement is an example of a permutation. Notice that for permutations, order matters; BCA is not the same as ABC. We also don’t allow repetition, so AAB is not a valid permutation of our letters. Our job then is to find a way to count these. And to help us find a formula, we’re going to begin by considering an example.

In how many ways can a three-digit number, with no repeated digits, be formed using the numbers two, nine, and eight?

We have three digits that we’re able to use. And we are wanting to count the number of ways we can order these digits, assuming there are no repeated digits. Since order matters, that is, the number 298 is not the same as 928, we’re really looking to find the number of permutations of these digits. One method we have, of course, is just to try listing all the possible options. This is called systematic listing. As the name suggests, we just try to find a technique that will ensure we don’t lose any numbers. We can begin with 298. Then we can swap the eight and the nine, giving us 289. Next, we’ll put eight at the front and will do 829 and will swap the two and the nine to give us 892. Finally, we’ll put the nine at the front. We get 928. And if we swap the eight and the two, we get 982.

And so we see that we have six different permutations. There are six different three-digit numbers that we can form using the numbers two, nine, and eight. However, this isn’t necessarily the most efficient method, and so we’re going to consider an alternative. We’re going to consider each digit of our number in turn. And we know that to choose the first number, we can choose from the number two, the number nine, and the number eight. So there are three different possible options for the first digit in our number. Then when we move on to the second option, we’ve already chosen one of the numbers. And so since we can’t repeat the digits, we have two possible options to choose from for our second digit.

Finally, when we move on to the third digit, we’re left with only one option. The counting principle tells us that we can calculate the total number of permutations by multiplying these numbers. That’s three times two times one, which is equal to six. The total number of permutations or the total number of three-digit numbers that we can form is six. Now, we can generalize this somewhat and say that the number of permutations there are of a set of 𝑛 items is 𝑛 times 𝑛 minus one times 𝑛 minus two and so on all the way down to one. This can be represented more succinctly as 𝑛 factorial. So the number of permutations there are of a set of 𝑛 items is 𝑛 factorial.

This isn’t always sufficient though. For example, what do we do if we just want to find the number of permutations of let’s say 𝑟 items from a set of 𝑛? Well, let’s go back to this example. Let’s ask ourselves, how many two-digit numbers can we make from a set of three numbers? This time, we have three ways of choosing the first digit and two ways of choosing the second. And what about the number of one-digit numbers we can make from a set of three numbers? There are three ways of choosing this one digit, so the answer is three.

Introducing the notation 𝑛 P 𝑟 to represent the number of permutations of 𝑟 items from a set of 𝑛, we get three P three to be three times two times one, three P two to be three times two, and three P one to be equal to three. And we can relate this to the factorial notation we just saw. If we look at three P two, we see that it looks a little bit like we did three factorial, that’s three times two times one, and then divided it by one factorial. And then the ones cancel out, leaving us with three times two. Similarly, three P one could be represented as three factorial divided by two factorial. The twos and the ones cancel, leaving us with three.

If we then notice that the difference between the 𝑛 and 𝑟 is always the value of the factorial on the denominator, we see that we can generalize. The number of ways we can order 𝑟 elements from a set of 𝑛 with no repetition is given by 𝑛 P 𝑟. And that’s defined as 𝑛 factorial over 𝑛 minus 𝑟 factorial. Alternative notation is shown and it’s purely a matter of personal preference and partly where you might live in the world as to which one you’re going to choose. I’m going to use this version here.

So now we have a definition for the number of permutations of 𝑟 items from a set of 𝑛, let’s consider an example of the application of the formula.

Which of the following represents the number of ways a four-digit number can be formed from five digits, given that each digit cannot be used more than once? Is it (A) five P four, (B) six P four, (C) four P four, or (D) nine P four?

We begin by recalling that the number of ways of ordering 𝑟 items from a set of 𝑛 with no repetition and where order matters is 𝑛 P 𝑟. We have various ways of representing this, and in this example, we’re using the first. These are called permutations. In this question, we want to find the number of ways of choosing a four-digit number from five digits. So we let 𝑛 be equal to five, since that’s the total number of digits we have. And we let 𝑟 be equal to four, since that’s how many we’re looking to choose. Using the first notation in this definition, we therefore write five P four. The correct answer is (A). The number of ways of choosing four digits from a set of five given that each digit cannot be used more than once is five P four.

In our next example, we’ll look at how we can evaluate permutations and how we might be able to do so using some shortcuts.

Evaluate 123 P three.

This notation is essentially asking us to find the number of ways of ordering three items from a set of 123 with no repetition and where order matters. It’s the number of permutations. And the general formula we use to order 𝑟 items from a set of 𝑛 with no repetition is 𝑛 factorial over 𝑛 minus 𝑟 factorial. Comparing what we have in our question with the general formula, and we see that we’re going to let 𝑛 be equal to 123 and we’re going to let 𝑟 be equal to three. And so 123 P three is 123 factorial over 123 minus three factorial, remembering of course that we can’t distribute the factorial over our parentheses and we instead evaluate 123 minus three. And we see that 123 P three is equal to 123 factorial over 120 factorial.

And whilst we could use the buttons on our calculator to evaluate this, it’s worth looking at how we can simplify our expression somewhat. We write 123 factorial as 123 times 122 times 121 and so on. But then, of course, 120 times 119 and so on is actually 120 factorial. So we rewrite 123 P three as 123 times 122 times 121 times 120 factorial over 120 factorial. And this step is important because we can now divide both the numerator and denominator of our fraction by 120 factorial. That leaves us with a denominator of one. And in turn, it means that our fraction simplifies to 123 times 122 times 121. And so 123 P three, which is the number of ways of ordering three items from a set of 123 with no repetition, is 123 times 122 times 121.

Now, this technique can be really helpful as it allows us to simplify quite a nasty calculation which we’re then able to potentially perform by hand. We’ll now consider how to use permutations to solve word problems.

In horse racing, a trifecta occurs when a bettor wins by selecting the first three finishes in their exact order: first place, second place, and third place. How many different trifectas are possible if there are 14 horses in a race?

What this question is really asking us is how many different ways are there to order three horses from a set of 14. We, of course, know that no horse can appear in the top three more than once at any given time. In other words, the same horse cannot be in first and second place at the same time. And, of course, we’re told that order matters. And so we’re looking to find the number of permutations, specifically the number of permutations of three items from a set of 14. And so we recall that the number of permutations of 𝑟 items from a set of 𝑛 is 𝑛 P 𝑟, and it’s given as 𝑛 factorial over 𝑛 minus 𝑟 factorial.

We’re going to let 𝑛 be equal to 14 since that’s the total number of horses and 𝑟 is equal to three. We’re interested in the first three finishes, and so the number of permutations is 14 P three. And that’s 14 factorial over 14 minus three factorial. Of course, 14 minus three is 11, so we get 14 factorial over 11 factorial. But since we can write 14 factorial as 14 times 13 times 12 times 11 times 10 and so on, we know that we can also write it as 14 times 13 times 12 times 11 factorial. And this is really useful because we can now divide through by a common factor of 11 factorial. And we see that 14 P three simplifies to 14 times 13 times 12, which is 2,184. And so we establish that there are a total of 2,184 trifectas possible when there are 14 horses in a race.

In our final example, we’ll consider what happens if we’re trying to count more than one set of permutations.

A company labels their products with codes that start with three English letters followed by eight nonzero digits. Which of the following represents the number of codes that can be created with no repetition of any letter or digit? Is it (A) three P three plus eight P eight? Is it (B) 26 P three plus nine P eight? Is it (C) three P three times eight P eight? Or is it (D) 26 P three times nine P eight?

Let’s begin by considering the two parts of the code. The first part consists of three English letters. Then we have eight nonzero digits. And to work out the number of ways of choosing or ordering the three English letters, we’re going to recall that the number of ways we can order 𝑟 items from a set of 𝑛 with no repetition and where order matters is 𝑛 P 𝑟. And it’s 𝑛 factorial over 𝑛 minus 𝑟 factorial.

We want to choose three letters from a total of 26 in the English alphabet. Order matters; in other words, ABC is not equal to BAC. And so the number of ways to choose these is 26 P three. Then, if we’re interested in choosing eight nonzero digits, we can choose any digit between one and nine inclusive. So we’re choosing eight digits from a total of nine. Once again, order matters and we’re not using any repetition. So to choose eight digits from nine, it’s nine P eight.

If the number of ways of choosing the three English letters is 26 P three and the number of ways of choosing the eight digits is nine P eight, then the counting principle tells us that the total number of possibilities, the total number of codes, is the product of these. It’s 26 P three times nine P eight. And if we compare that to the options given in our question, we see that the answer is (D). The total number of codes that can be created with no repetition of any letter or digit is 26 P three times nine P eight.

In this video, we’ve learned that the number of ways of choosing 𝑟 items from 𝑛 is 𝑛 P 𝑟 or P of 𝑛, 𝑟. Any of these notations is acceptable. But either way, we can evaluate these using the formula 𝑛 factorial over 𝑛 minus 𝑟 factorial or even using the permutations function on a calculator. We saw that when working with permutations, we need to make sure that we have a scenario where order matters and that we’re counting without repetition. And we also considered a number of real-world situations which can be evaluated using permutations.

Nagwa uses cookies to ensure you get the best experience on our website. Learn more about our Privacy Policy.