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.