Video Transcript
In this video, we’re going to learn
how to count a number of possible outcomes when given some restrictions. And to do so, we begin by recalling
the fundamental counting principle, sometimes called the product rule for
counting. It says if events 𝐴 and 𝐵 which
are independent events have 𝑚 and 𝑛 possible outcomes, respectively, then the
total number of possible outcomes for the events together is the product of
these. It’s 𝑚 times 𝑛.
For instance, how many ways can a
three-digit pin number be created by using the numbers zero to nine?
There are 10 possible numbers that
we can use for each digit. That means there are 10 ways to
choose the first digit, 10 ways to choose the second digit, and 10 ways to choose
the third digit. The fundamental counting principle
tells us that the total number of possible outcomes then is the product of
these. It’s 10 times 10 times 10 or of
course 10 cubed, which is equal to 1000. Now, in fact we can generalize
this. And we can say that when counting
with replacement, in other words, repetition is allowed, the total number of
outcomes from 𝑛 repeated events of choosing from 𝑚 items is given as 𝑚 to the
power of 𝑛.
Notice, though, that this is
specifically for independent events, those where the outcome of the first event
doesn’t affect the outcome of the second. In other words, in this case, when
we chose that first digit, it didn’t affect the number that we could choose for the
second digit. If this is not the case, for
instance, where there are restrictions on using that number twice, then we can still
use the fundamental counting principle. But we do need to be a little bit
careful. Let’s see what that might look
like.
How many four-digit numbers, with
no repeated digits, can be formed using the elements of the set containing zero,
one, three, and four?
So we’re creating numbers with four
digits in them, and we’re not allowed to repeat those digits. We know that we can count the total
number of possible outcomes by using the fundamental counting principle or the
product rule for counting. This rule says that when combining
more than one event, the total number of outcomes is found by multiplying the number
of outcomes for each event together. And so we need to identify what
each event actually is. The first event is picking the
first digit, the second event is picking the second digit, and so on. There are four elements in our set,
but this doesn’t mean there are four ways of choosing the first digit. In fact, for our number to be a
four-digit number, its first digit cannot be zero. It can only be one, three, or
four. And so there are actually just
three ways of choosing the first digit.
Then we consider the second
digit. We’ve already chosen a number from
the list one, three, and four. And we know we cannot repeat one of
these digits. And so if we take one of the
numbers out of our set, we now have just three left. There are three ways of choosing
the second digit. Now we move on to the third digit
and we say that we’ve already chosen two possible numbers from the set, and that
leaves us with two left. And similarly, when we get to the
fourth digit, we’ve already taken three numbers, and so there’s only one left to
choose from. The counting principle says then
that the total number of outcomes, which is here the total number of four-digit
numbers, is the product of these values. It’s three times three times two
times one, which is equal to 18. We can make 18 four-digit numbers
given that no digits can be repeated using the elements of our set.
Let’s consider a similar example to
see if we can generalize this somehow.
David’s password must be five
characters long. He can use the digits zero to nine
and cannot use the same digit more than once. How many different passwords could
David create?
We’re looking to find the total
number of five-digit passwords, bearing in mind that we cannot use the same digit
more than once. And so we recall the fundamental
counting principle or the product rule for counting. This tells us that we can find the
total number of outcomes for two or more events by multiplying the number of
outcomes for each event together. Now, the events here are choosing
the first character, choosing the second character all the way through to choosing
the fifth character. And since we’re working with the
digits zero to nine inclusive, there are a total of 10 digits to choose from. And there are therefore 10 possible
different outcomes for the first event for choosing that first digit.
Now it’s really important that we
realize we can’t use the same digit more than once when considering the total number
of outcomes for our second event, that is, choosing the second digit. We’ve already chosen one from the
digits zero to nine, and so that leaves us with just nine more to choose from. Similarly, when we get to the third
digit, we know we’ve already taken two possible digits from our list. And so there are eight more to
choose from.
In a similar way, there are seven
ways of choosing the fourth digit and just six ways of choosing the fifth. The counting principle or the
product rule for counting tells us that we now need to multiply these numbers
together. 10 times nine times eight times
seven times six is 30,240. And so we see there are 30,240
different passwords that David could create given that he can only use the digits
zero to nine and cannot use them more than once.
Now we can actually generalize this
result. We call this counting without
replacement. And that is because we take a digit
away, we don’t replace it and use it once again. And we say that when counting
without replacement, the total number of ways of choosing 𝑛 items from a collection
of 𝑚 is 𝑚 times 𝑚 minus one times 𝑚 minus two all the way down to 𝑚 minus 𝑛
minus one.
Let’s now consider another way of
imposing restrictions.
After a recent reorganization,
James is taking over responsibility for the manufacturing of odd numbers on the
house sign number production line. As part of his scientific
investigation into production levels, he wants to know how many three-digit numbers
only contain odd digits. Calculate the answer for him.
We are interested in finding the
total number of three-digit number house signs. However, there’s a pretty hefty
restriction on this. These numbers can only contain odd
digits; that is, they must be made up of the numbers one, three, five, seven, or
nine. And so let’s consider each of the
digits in turn.
The first digit can be any one of
these numbers. It can be one, three, five, seven,
or nine. So there are five possible ways of
choosing the first digit. There are no restrictions on using
the same digit more than once. For example, we could choose the
number one, one, one; that would be fine. And so there are still five ways of
choosing the second digit. The second digit can be any one of
these odd numbers. Then, for the third digit, we have
the exact same situation. We can choose the numbers one,
three, five, seven, or nine. And so there are five ways of
choosing the third digit.
The fundamental counting principle
or the product rule for counting says the total number of ways of choosing these
then is the product of these. It’s five times five times five,
which is 125. There are 125 three-digit numbers
then that only contain odd digits.
Let’s consider a slightly different
context.
A building has five doors which are
numbered as one, two, three, four, five. Determine the number of ways a
person can enter and then leave the building if they cannot use the same door
twice.
Let’s try to visualize this. Our building has five doors, and
let’s label them one, two, three, four, five as it tells us to. Let’s imagine we have someone
looking to enter the building. They have five possible ways to do
so. But let’s imagine for sake of
argument that they’re going to choose door number two. Once inside the building, we’re
told they cannot use the same door twice, and so we cut off door two as an exit. Looking around, we now see that
there are one, two, three, four possible ways for that person to exit the
building. They may, for example, choose door
four. There are therefore five possible
ways to enter the building. But once we are into the building,
there are only four possible ways to get out.
The product rule for counting or
the counting principle tells us that the total number of ways a person can enter and
then leave the building given these restrictions is the product of these. It’s five times four, which is
equal to 20. There are 20 possible ways then
that the person can enter and then leave the building given that they can’t use the
same door twice.
In our very final example, we’re
going to look at working out the number of possibilities for a seating
arrangement.
Mia and Daniel are planning their
wedding. They’re working on the seating plan
for the top table at the reception. Their top table is a straight line
with eight seats down one side. It needs to sit the bride and
groom, the bride’s parents, the groom’s parents, the best man, and the maid of
honor. Given that all couples need to sit
next to each other and that the best man and maid of honor are not a couple, how
many different ways are there for seating everyone on the top table?
We have a few restrictions on how
we seat each couple and the maid of honor and the best man. Let’s begin by considering the
couples who are the bride and groom, the bride’s parents, and the groom’s parents as
three units essentially. And we’re going to begin by working
out the total number of ways of just seating these three couples. There are three ways of choosing
the first couple to seat. There are two ways of choosing the
second couple to seat and one way of choosing the third. And, of course, the product rule
for counting or the counting principle says the total number of options is the
product of these. It’s three times two times one,
which is six.
So we have six ways of seating the
couples. But of course, each couple could
sit in a different order. We could have the bride and groom
or the groom then the bride. And if we think about it, there are
two ways to seat the bride and groom, two ways to seat the bride’s parents, and two
ways to seat the groom’s parents. Two times two times two is equal to
eight, meaning that there are eight ways that each couple could sit next to each
other. Bear in mind that this is for each
of the six original ways of seating the couples. This means that the total number of
possibilities when it comes to seating these is the product of these two sets of
outcomes. It’s six times eight, which is
48. So we have 48 ways in total of
seating those couples.
And so now we move on to seating
the best man and the maid of honor. We consider these individually
because we’re told they’re not a couple, and therefore they don’t necessarily need
to sit next to one another. And so if we think about the top
table with our three couples already seated, he could sit at either end. But also he could sit at any point
between the couples. And so there must be four options
of chairs for him. Then, once the best man is seated,
the maid of honor could sit at either end. But she could also sit between any
of the couples and/or the best man, depending on where he’s located. And this must mean that there are
five different ways of seating the maid of honor.
Now that we’ve considered all the
possible events, that is, seating the couples, seating the best man, and seating the
maid of honor, we know that the fundamental counting principle tells us to find the
product of these. That’s 48 times four times five,
which is equal to 960. There are a total number of 960
different ways for seating everyone on the top table.
Now, in fact, this isn’t the only
method of answering this problem. We can alternatively just consider
that there are five different groups; there are three couples and two
individuals. And so we would say that there are
five ways of choosing the first group to seat, four ways of choosing the second
group, three ways of choosing the third, and so on, giving us a total of 120
different ways to arrange these five places.
Then we go back to considering how
the couples are arranged. We know that each couple could sit
in a slightly different order. And so there are two times two
times two, which is eight arrangements for our couples. Once again, the fundamental
counting principle tells us that the total number of different ways for seating
everyone is the product of these. It’s 120 times eight, which is once
again 960.
We’re now going to consider the key
points from this lesson. In this video, we saw that we can
extend the use of the fundamental counting principle to scenarios where there are
restrictions on the possible outcomes. We saw that when counting with
replacement, the total number of outcomes from 𝑛 repeated events of choosing from
𝑚 items is 𝑚 to the power of 𝑛. When counting without replacement
though, we have 𝑚 times 𝑚 minus one times 𝑚 minus two all the way down to 𝑚
minus 𝑛 minus one.
