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, imagine we have the
letters 𝐴, 𝐵, 𝐶, and 𝐷. We could arrange two of them as
𝐴𝐵, 𝐵𝐶, 𝐶𝐷, and so on. Each arrangement is an example of a
combination. But for combinations, we say order
doesn’t matter. And so 𝐴𝐵 would be considered the
same arrangement as 𝐵𝐴. Remember, of course, that if order
does matter, we’re actually thinking about permutations. And therefore, our formula is going
to be different. It’s really important that we’re
careful to distinguish between these. Our job is now to find a way to
count them. And to help us find a formula,
we’re going to 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. Now we should see quite quickly
that the order here doesn’t matter. For example, let’s say three of her
topics are fractions, decimals, percentages. She could choose them in that
order: fractions, decimals, percentages. She could alternatively say
fractions first and then choose percentages and then decimals. There are in fact six different
ways that she could choose these topics. But we see that choosing fractions,
decimals, percentages would be exactly the same as selecting decimals, then
percentages, then fractions. When we want to choose a number of
items from a larger group and order doesn’t matter, these are called
combinations.
Now, in order to find the number of
combinations, we’re going to begin by thinking about permutations. Now, permutations occur when order
does matter. So if we think about our earlier
example, where we ordered the three topics, there was only one combination but six
different permutations. We might recall that 𝑛P𝑟 is the
number of ways of choosing 𝑟 items from a selection of 𝑛 when order does
matter. It’s the number of
permutations. And we calculate this by working
out 𝑛 factorial divided by 𝑛 minus 𝑟 factorial. So let’s begin by working out the
number of permutations of five topics from a total of eight. That’s eight P five. That’s eight factorial over eight
minus three factorial, which is 6720. There are 6720 permutations.
But we know that order doesn’t
matter. And so we need to find a way to get
rid of the extra permutations. If we go back to our earlier set of
three topics, we saw that that was six P three. There were six permutations. To get rid of the extra
permutations, we would divide by three factorial. Three factorial is six, so we get
six divided by six, which is equal to one. In the case where we choose five
topics from eight, we need to divide by five factorial. And so the calculation that we can
perform to find the number of combinations is eight factorial divided by five
factorial times eight minus three factorial. And that’s equal to 56. This gives rise to a formula.
When finding combinations, we
notice that we have less than the number of permutations. To take into account the number of
extra times we’ve counted the same set of our items, we need to divide the number of
permutations by 𝑟 factorial. The number of combinations of size
𝑟 taken from a collection of 𝑛 items is given by 𝑛C𝑟. And that’s 𝑛P𝑟 divided by 𝑟
factorial, which can be written as 𝑛 factorial divided by 𝑟 factorial times 𝑛
minus 𝑟 factorial.
𝑛C𝑟 is sometimes read as 𝑛
choose 𝑟, and it’s also referred to as the binomial coefficient. You might see it written in any of
these formats. The one you choose will be partly
personal preference and partly where you’re located in the world. In this video, we’ll primarily use
these two forms. Let’s now consider an example that
demonstrates how we can 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.
In this question, we’re looking to
choose two names from a selection of four. And so we should be beginning to
think about combinations and permutations. Combinations are a way of choosing
rearrangements where order doesn’t matter. So, for example, if we were
choosing out of the letters 𝐴, 𝐵, 𝐶, and 𝐷, the arrangement 𝐴 and 𝐵 would be
the same as the arrangement 𝐵 and 𝐴. With permutations, order does
matter. So 𝐴 and 𝐵 would be a different
arrangement to 𝐵 and 𝐴. Let’s think about choosing the two
names from a hat. If we choose Ali and Ben, for
example, that is exactly the same as choosing Ben and Ali. Order doesn’t matter. And so we can see that we are
thinking about the number of combinations.
The number of combinations of size
𝑟 taken from a collection of 𝑛 items is given by 𝑛C𝑟. And the formula is 𝑛 factorial
divided by 𝑟 factorial times 𝑛 minus 𝑟 factorial. We’re choosing two names from a
selection of four. So the number of combinations is
four C two. And that’s four factorial over two
factorial times four minus two factorial. Now, note that we could use the
𝑛C𝑟 button on our calculator. But actually, there’s a little
shortcut that can help us to calculate these by hand. We begin by rewriting four minus
two factorial as two factorial. But of course, four factorial is
four times three times two times one, which can further be rewritten as four times
three times two factorial.
And now we see we can divide
through by a common factor of two factorial. In fact, two factorial is simply
two, so we can divide once again by two. And we see four choose two is two
times three divided by one, which is simply six. There are six ways to choose two
names from the four given.
We’re now going to consider how we
can apply this formula to a problem involving sets.
Let 𝑋 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 the elements 𝑎 and 𝑏, where 𝑎 and 𝑏 are elements of the
set 𝑥 and 𝑎 is not equal to 𝑏. Determine the value of 𝑛 of 𝑌,
where 𝑛 of 𝑌 is the number of elements in 𝑌.
Let’s just begin by looking at what
this set notation is actually telling us. Set 𝑋 contains the number 𝑥,
which is an integer greater than or equal to 10 and less than or equal to 16. And so 𝑋 could be rewritten as the
set containing the elements 10, 11, 12, 13, 14, 15, and 16. Then, we have set 𝑌, and set 𝑌
contains all pairs of integer combinations 𝑎 and 𝑏 such that 𝑎 is not equal to
𝑏. But both 𝑎 and 𝑏 are elements of
set 𝑋. So it’s like a list of pairs of
numbers, and we need to work out how many pairs are in that list. And so 𝑛 of 𝑌 is the number of
ways of choosing two elements from a total of seven. And that’s because there are seven
elements in set 𝑋. Since 𝑎 cannot be equal to 𝑏,
there’s no repetition.
But of course, choosing 10 and 11
would be the same as choosing 11 and then 10. And so we’re interested in
combinations. And 𝑛 of 𝑌 is seven choose
two. The formula of 𝑛 choose 𝑟, the
number of ways of choosing 𝑟 items, from a set of 𝑛 is 𝑛 factorial over 𝑟
factorial times 𝑛 minus 𝑟 factorial. And so seven choose two is seven
factorial divided by two factorial times seven minus two factorial. Now, we can write seven minus two
factorial as five factorial. And then we can also write the
numerator seven factorial as seven times six times five factorial. Then we divide through by five
factorial.
And since two factorial is two, we
can also divide through by two. And seven choose two simplifies to
seven times three over one, which is simply 21. And so 𝑛 of 𝑌, which was the
number of ways of choosing two unique elements from a set of seven where order
doesn’t matter, is 21. We can also apply this formula more
than once to help us answer counting problems.
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 told to choose a team of
eight people. But every single member of that
team must be of the same sex. So we’re either going to choose
eight out of the 14 boys or eight out of the 13 girls. And so we next ask ourselves, does
order matter? Well, no choosing, say, boy 𝑎 and
boy 𝑏 would be the same as choosing boy 𝑏 and then boy 𝑎. When order doesn’t matter, we’re
looking at counting combinations. And we say that the number of ways
of choosing 𝑟 items from a set of 𝑛 is 𝑛 choose 𝑟. And it’s 𝑛 factorial over 𝑟
factorial times 𝑛 minus 𝑟 factorial.
And so we’re going to begin by
performing two different calculations. We want to work out the number of
ways of choosing eight boys from a total of 14. So that’s 14 choose eight. And then we’re separately going to
work out the number of ways of choosing eight girls from the group of 13. That’s 13 choose eight. 14 choose eight is 14 factorial
over eight factorial times 14 minus eight factorial. And if we type that into our
calculator or use the combinations button, we see that 14 choose eight is equal to
3003. Then 13 choose eight is 13
factorial over eight factorial times 13 minus eight factorial, which is 1287.
What we’re trying to count is the
number of ways of choosing eight boys or choosing eight girls. And so that’s the sum of our
individual calculations. It’s 3003 plus 1287, and that’s
4290. There are 4290 ways to select a
team of eight people from the class so that every member of the team is of the same
sex.
In our final example, we’ll
consider a problem where we need to work out the value of 𝑛 when given the total
number of combinations and the value of 𝑟.
At a college, there were 120 ways
to select 119 students to attend a seminar. Determine the number of students at
the college.
Let’s begin by letting 𝑛 be equal
to the total number of students at the college. 𝑟 is 119; we’re looking to select
119 students from a total of 𝑛. And we’re told there are 120 ways
to do so. Now, in this case, order doesn’t
matter. And so these are combinations. There are 120 combinations of
students. The formula we use for counting
combinations is 𝑛C𝑟 equals 𝑛 factorial over 𝑟 factorial times 𝑛 minus 𝑟
factorial, where 𝑟 is the number of items we’re looking to choose and 𝑛 is the
total number of items we can choose from. In this question, we’re looking to
find the number of combinations of 119 students from a set of 𝑛. So that’s 𝑛 choose 119. According to our formula, that’s 𝑛
factorial over 119 factorial times 𝑛 minus 119 factorial.
But of course, we were actually
told that there were 120 ways to select these students. So we get 120 equals 𝑛 factorial
over 119 factorial times 𝑛 minus 119 factorial. We’re now going to multiply both
sides of our equation by 119 factorial. The left-hand side then becomes 120
times 119 factorial. We could also consider that to be
equal to simply 120 factorial. And then on the right-hand side, we
have 𝑛 factorial over 𝑛 minus 119 factorial. But actually, we can simplify the
expression on the right-hand side somewhat. If we consider 𝑛 factorial as
being 𝑛 times 𝑛 minus one times 𝑛 minus two all the way down to one, then we’re
able to simplify this fraction by dividing the numerator and denominator by 𝑛 minus
119 factorial. And then that leaves us with 𝑛
times 𝑛 minus one times 𝑛 minus two all the way down to 𝑛 minus 117 times 𝑛
minus 118.
We divided by 𝑛 minus 119
factorial. So any term after this simply
disappears. We’re now going to use this to
compare each side of our earlier equation. We can say that 𝑛 times 𝑛 minus
one times 𝑛 minus two all the way down to 𝑛 minus 118 must be equal to this
left-hand side, 120 times 119 factorial. Now we can write this as 120 times
119 times 118 and so on. Now we do need to be a little bit
careful here. On the numerical side of our
equation, we have 120 term. And on the algebraic side, the side
with the 𝑛’s, we have 119 terms. But of course, this is the same as
multiplying 𝑛 by 𝑛 minus one by 𝑛 minus two and so on, all the way down to 𝑛
minus 118 and then multiplying that by one.
And so now there are two
expressions equal to one another that contain the product of 120 terms. In each case, we’ve got 119 terms
that follow the same pattern, that is, a number multiplied by one less multiplied by
one less and so on. And then each one itself is
multiplied by one. We can now equate both sides of
this equation. If we consider the largest terms in
our equation, we could say 𝑛 must equal to 120. It’s not necessary to just choose
this one. We could choose any terms in our
equation. The next smallest term on each side
is 𝑛 minus one and 119. Equating these gives us 𝑛 minus
one equals 119. And if we add one to both sides, we
get 𝑛 equals 120. Even moving all the way down to 𝑛
minus 118 and two, equating this gives us 𝑛 minus 118 equals two. And we add 118 to both sides to
give us 𝑛 equals 120. And we can therefore say that the
number of students at the college is 120.
We’re now going to summarize the
key points from this lesson. In this video, we’ve learned that
combinations are arrangements of 𝑟 items from a group of 𝑛. But order doesn’t matter. And of course, there must be no
repetition. We can count the number of
combinations, that’s the number of selections of 𝑟 items from a set of 𝑛, by
working out 𝑛 factorial over 𝑟 factorial times 𝑛 minus 𝑟 factorial. But of course, this representation
looks different depending on where in the world you come from.
