Video Transcript
In this video, we’ll learn how to
use combinations to solve counting problems. A combination is a rearrangement of
a collection of items. For example, let’s say we have the
letters A, B, C, and D. We can arrange two of them as AB,
BC, CD, and so on. Each arrangement is an example of a
combination. Order doesn’t matter, so AB is the
same as BA. Now, of course, if order does
matter, we’re actually calculating a permutation, and therefore our formula is going
to be different. So it’s really important that we’re
careful to distinguish between these before answering any problems. Our job is to now find a way to
count these. And to find a formula, we’ll begin
by considering an example.
Olivia was asked by her teacher to
choose five from the eight topics given to her. How many different five-topic
groups could she choose?
In this question, we’re looking at
how many ways we can choose five items from a group of eight. And here order doesn’t matter. For example, let’s say that three
of the topics she can choose from are fractions, decimals, and percentages. She could choose fractions first,
then decimals, then percentages. She could alternatively still
choose fractions first but then choose percentages and then decimals. If we list all of these different
ways out, there are six different ways in which she could choose the three
topics. But of course within this context,
choosing fractions, decimals, and percentages is actually the same as choosing them
in any other order. In fact, when we want to choose a
number of items from a larger group, we call this a combination.
To find a formula, we’ll begin then
by thinking about permutations. This is when the order does
matter. In this case, there are six
permutations and just one combination. Now let’s say 𝑛𝑃𝑟 is the number
of ways of choosing 𝑟 items from a selection of 𝑛 when order does matter. We might recall that the formula we
use to calculate 𝑛𝑃𝑟 is 𝑛 factorial over 𝑛 minus 𝑟 factorial. In this case, we’re interested in
the number of ways of choosing five topics from a total of eight. So we’re going to calculate eight
𝑃 five. By letting 𝑛 be equal to eight and
𝑟 be equal to five, the number of permutations here is eight factorial over eight
minus five factorial. That’s eight factorial over three
factorial, which is 6720.
So, if order does matter, there
would be 6720 ways to choose five from the eight topics given. But we know the order doesn’t
matter here. And so we need to find a way to get
rid of the extra permutations. Let’s go back to our earlier
example of choosing just three topics. To choose three topics from a total
of six when order matters, we calculate six 𝑃 three, which gives us the six
permutations we’re expecting.
To get rid of the extra
permutations, we have to divide by three factorial since we’re looking at three
subjects. That’s six divided by three
factorial, or six divided by six, which is equal to one. That gives us the one combination
we know we were expecting. In this case, since there are five
topics, we’re going to divide eight 𝑃 five by five factorial. And that gives us an answer of
56. Olivia can choose 56 different
five-topic groups from the total of eight.
Now, this gives rise to a
formula. When finding numbers of
combinations, we must have less than the total number of permutations. And to take into account the number
of extra times we’ve counted the same set of 𝑟 items, we divide the number of
permutations by 𝑟 factorial. So we get 𝑛 choose 𝑟, the number
of ways of choosing 𝑟 items from 𝑛 when order doesn’t matter, is equal to 𝑛𝑃𝑟
over 𝑟 factorial. Let’s define this a little more
formally. The number of ways to choose 𝑟
items from a collection of 𝑛 items when order doesn’t matter is said to be the
number of combinations. And we define it 𝑛 choose 𝑟, and
it’s equal to 𝑛𝑃𝑟 over 𝑟 factorial, which is equivalently equal to 𝑛 factorial
over 𝑟 factorial times 𝑛 minus 𝑟 factorial.
It’s also worth noting that the
notation 𝑛𝐶𝑟 can be referred to as the binomial coefficient. And depending on where we’re
located in the world might depend on how we represent that notation as shown at the
bottom of the screen. With this in mind, we’ll now
consider an example that demonstrates how to apply this formula.
The names of four students are each
written on a piece of paper, which are then placed in a hat. If two names are randomly selected
from the hat, determine the number of all two-student selections that are
possible.
We’re looking to work out the
number of ways of choosing two names from a total of four. And so we’re going to begin by
deciding whether we’re interested in calculating the number of combinations or the
number of permutations. And this all comes down to whether
order matters. Specifically, if we’re choosing
from a selection of items and we say that order doesn’t matter, then we say that
that is a combination. If, however, order does matter,
then we have a permutation.
Let’s think about what happens when
we choose the two names for a hat. Suppose the two names we pull out
of the hat are Ali and Ben. It does not matter whether we
choose Ali first and then Ben or we choose Ben first and then Ali. This means that we’re interested in
the number of combinations. Order does not matter here. So let’s remind ourselves of the
formula we use. To calculate the number of
combinations of choosing 𝑟 items from a collection of 𝑛, we find 𝑛 choose 𝑟,
which is equal to 𝑛𝑃𝑟 over 𝑟 factorial.
When calculating from the
beginning, it can make sense to use the amended formula 𝑛 factorial over 𝑟
factorial times 𝑛 minus 𝑟 factorial. Now, 𝑛 is the total number of
items within the collection. Well, here this is the names of the
students. So there are four students and 𝑛
is equal to four. We’re choosing two names out of the
hat. So we’re going to let 𝑟 be equal
to two. We can therefore say that the total
number of ways of choosing these names is given by four choose two.
Substituting into the formula, and
we see that that is equal to four factorial over two factorial times four minus two
factorial. That simplifies to four factorial
over two factorial times two factorial. And then since two factorial is two
times one, it’s two, and four factorial can be equivalently written as four times
three times two factorial, we see we can divide through by a common factor of two
factorial and another factor of two. This means four choose two is equal
to two times three over one. And that’s simply six. And so there are a total of six
two-student selections that are possible.
Let’s now apply the same formula
but to a problem involving sets.
Let uppercase 𝑋 be the set
containing 𝑥, where 𝑥 is an integer greater than or equal to 10 and less than or
equal to 16, and 𝑦 is the set containing 𝑎 and 𝑏, where 𝑎 and 𝑏 are elements of
set 𝑋 and 𝑎 is not equal to 𝑏. Determine the value of 𝑛 of 𝑦,
where 𝑛 of 𝑦 is the number of elements in 𝑦.
Since we’re looking to find the
number of elements in set 𝑦, let’s begin by inspecting set 𝑦 in a little more
detail. Firstly, we see we’re interested in
the two elements 𝑎 and 𝑏, which are themselves an element of set 𝑋. Then we also see that set 𝑋
contains only integers which are greater than or equal to 10 and less than or equal
to 16. In other words, set 𝑋 contains the
elements 10, 11, 12, 13, 14, 15, and 16. We see there are a total of seven
elements in set 𝑋. So this is the number of elements
that we’re choosing from.
We also know that 𝑎 is not equal
to 𝑏. So we need to find the number of
ways to choose two different elements from 𝑋 where order doesn’t matter. That is, we’re counting the number
of combinations. This means that 𝑛 of 𝑦, the
number of elements in set 𝑦, must be equal to seven choose two. Now, of course, the formula for 𝑛
choose 𝑟 is 𝑛 factorial over 𝑟 factorial times 𝑛 minus 𝑟 factorial. By letting 𝑛 be equal to seven and
𝑟 be equal to two, we can rewrite seven choose two as follows. It’s seven factorial over two
factorial times seven minus two factorial. The denominator of this expression
simplifies to two factorial times five factorial. We’re then going to rewrite seven
factorial as seven times six times five factorial. And two factorial is simply two
times one, so it’s two.
This then means we can divide by a
constant factor of five factorial, and we can also divide by two. So seven choose two simplifies to
seven times three divided by one, which is equal to 21. So, by establishing 𝑛 of 𝑦 as
being the number of ways of choosing two items from a total of seven where order
doesn’t matter, we have found that the number of elements in set 𝑦 is 21.
It’s worth noting that we can also
apply this formula more than once to a counting problem. Let’s demonstrate this.
A class contains 14 boys and 13
girls. In how many ways can you select a
team of eight people from the class such that every member of the team is of the
same sex?
We’re going to be selecting a team
of eight people, but we’re told that every member of the team is of the same
sex. In other words, we’re either
choosing eight boys from a total of 14 or we’re choosing eight girls from a total of
13. Now, of course, order doesn’t
matter here. We can choose the eight boys or
eight girls in any order. Remember, when order doesn’t
matter, we’re looking at combinations. Specifically, if we look to choose
𝑟 items from a total of 𝑛 and order doesn’t matter, we find 𝑛 choose 𝑟. That’s given by 𝑛 factorial over
𝑟 factorial times 𝑛 minus 𝑟 factorial.
Let’s do this for both groups of
boys and girls. Remember, we are choosing eight
boys from a total of 14. That’s 14 choose eight. Substituting 𝑛 equals 14 and 𝑟
equals eight into the formula, and we get 14 factorial over eight factorial times 14
minus eight factorial. That’s 3003. So there are 3003 ways of choosing
eight boys from a group of 14. Since we’re choosing eight girls
from a total of 13, we’re actually going to be calculating 13 choose eight. This time, that’s 13 factorial over
eight factorial times 13 minus eight factorial, which is 1287.
We now know how many ways there are
to choose eight boys and how many ways there are to choose eight girls. To find the number of ways of
choosing eight boys or eight girls, we find the sum of our two values. In other words, we find 3003 plus
1287, which is 4290. There are 4290 ways of choosing a
team of eight people from this group, given they are of the same sex.
In our final example, we’ll look at
a problem where we need to find a missing value when given the total number of
combinations.
At a college, there were 120 ways
to select 119 students to attend a seminar. Determine the number of students at
the college.
To answer this question, we’ll
begin by letting 𝑛 be the total number of students. We’re told that there are 120 ways
to select 119 students. And presumably, since these
students are all attending the same seminar, order doesn’t matter. Now, we know that when order
doesn’t matter, we’re interested in combinations. The number of ways of choosing 119
students out of 𝑛 when order doesn’t matter is 𝑛 choose 119. But of course, we’re told that’s
equal to 120. Let’s use the formula 𝑛 choose 𝑟
equals 𝑛 factorial over 𝑟 factorial times 𝑛 minus 𝑟 factorial to find a
different expression for 𝑛 choose 119.
Replacing 𝑟 with 119, and it’s
equivalent to 𝑛 factorial over 119 factorial times 𝑛 minus 119 factorial. To establish what’s actually going
on here, we’re going to multiply both sides of this equation by 119 factorial. When we do, we find that the
right-hand side becomes 120 times 119 factorial.
Next, let’s think about how we can
alternatively express the left-hand side. Since we’re dividing 𝑛 factorial,
which is 𝑛 times 𝑛 minus one times 𝑛 minus two and so on, by 𝑛 minus 119
factorial, we cancel out a factor of 𝑛 minus 119. And we see that this is equal to 𝑛
times 𝑛 minus one all the way down to 𝑛 minus 118. On the right-hand side, 120 times
119 factorial is equivalent to 120 factorial. That’s 120 times 119 all the way
down to two times one. So we now have an equation, but we
do need to be a little bit careful. On the left-hand side of our
equation, we have 119 terms, whereas on the right we have 120. But the left-hand side is
equivalent to multiplying 𝑛 by 𝑛 minus one all the way down to 𝑛 minus 118 and
then multiplying that by one.
And so now we have two expressions
equal to one another which have the product of the same number of terms. Let’s equate the largest term in
each expression. When we do, we get 𝑛 equals
120. But of course, we could equate the
second largest term, giving us 𝑛 minus one equals 119. Solving for 𝑛, and we still get 𝑛
equals 120. Repeating this process for the
second-smallest term on each side, and we get 𝑛 minus 118 equals two, which is the
same once again as saying 𝑛 equals 120. We have therefore shown that there
are 120 students at the college.
Let’s now recap the key points from
this lesson. In this lesson, we learned that
combinations are arrangements of 𝑟 items from a collection of 𝑛 when order doesn’t
matter. We saw that the formula used to
find the number of combinations 𝑛 choose 𝑟 is 𝑛 factorial over 𝑟 factorial times
𝑛 minus 𝑟 factorial. And we saw that depending on where
we were in the world, we might represent the notation a little bit differently, as
shown.
