### Video Transcript

In this video, we’ll learn how to
solve problems involving combinations.

We say that a combination is a
selection of 𝑟 items chosen without repetition from a collection of 𝑛 items. And order doesn’t matter. A permutation, however, is a
selection of 𝑟 items chosen without repetition from a collection of 𝑛 items in
which order does matter. So we see that the main difference
between these is whether we’re interested in the order in which the items are
chosen. For example, to choose the elements
𝐴 and 𝐵 from a collection, we could choose 𝐴 then 𝐵 or 𝐵 then 𝐴. With combinations, order doesn’t
matter. So we consider these to be the
same. And so there are one way to choose
them. However, with permutations, these
are different as the order is reversed. And so the number of permutations
is two.

We see that counting with
permutations results in an overcount. In fact, we overcount by a factor
of 𝑟 factorial. And so this means we can define the
number of 𝑟 combinations from 𝑛 as the number of 𝑟 permutations of 𝑛 divided by
𝑟 factorial. We recall that 𝑛𝑃𝑟 is defined by
𝑛 factorial over 𝑛 minus 𝑟 factorial. Meaning 𝑛𝑃𝑟 divided by 𝑟
factorial can be written as 𝑛 factorial over 𝑟 factorial times 𝑛 minus 𝑟
factorial. We’re now able to apply the
following definition. We say that the number of
combinations of size 𝑟 taken from a collection of 𝑛 items is given by 𝑛𝐶𝑟,
which is equal to 𝑛 factorial over 𝑟 factorial times 𝑛 minus 𝑟 factorial.

This notation can be read as 𝑛𝐶𝑟
or 𝑛 choose 𝑟. And it’s sometimes also referred to
as the binomial coefficient. You might also sometimes see it
written as shown. We’re now going to consider the key
properties of 𝑛 choose 𝑟 and how we can apply these to simplify expressions and
solve equations. Let’s begin by looking at an
example where we use the formula to help us evaluating an expression involving
combinations.

Determine the value of 23 choose
eight over 23 choose six without using a calculator.

In our question, we’ve been asked
to evaluate a quotient. In order to do so without using a
calculator, we’re simply going to begin by recalling what we mean by 𝑛𝐶, or 𝑛
choose, 𝑟. 𝑛 choose 𝑟 represents the number
of combinations of size 𝑟 taken from a collection of 𝑛 items. It’s given by 𝑛 factorial over 𝑟
factorial times 𝑛 minus 𝑟 factorial. And so we’re going to begin by
finding expressions in terms of factorials for 23 choose eight and 23 choose
six.

Beginning with 23 choose eight, we
see that in our formula, we’re going to let 𝑛 be equal to 23 and 𝑟 be equal to
eight. This means that 23 choose eight can
be written as 23 factorial over eight factorial times 23 minus eight factorial. But since 23 minus eight is 15, we
can simplify this a little to get 23 factorial over eight factorial times 15
factorial.

Let’s repeat this process with 23
choose six. This time, 𝑛 is still 23, but 𝑟
is equal to six. And so we see 23 choose six is 23
factorial divided by six factorial times 23 minus six factorial. This simplifies to 23 factorial
over six factorial times 17 factorial.

Now, we’re looking to find the
quotient of these. That’s 23 choose eight divided by
23 choose six. So we’re going to work out 23
factorial divided by eight factorial times 15 factorial divided by 23 factorial over
six factorial times 17 factorial. We can make this calculation much
easier by remembering that when we divide by a fraction, we multiply by the
reciprocal of that fraction. So we multiply our expression for
23 choose eight by one over the expression for 23 choose six, which is the same as
six factorial times 17 factorial over 23 factorial.

Now, this is really useful because
we can simplify by dividing through by 23 factorial. In fact, we can simplify a little
further. Let’s multiply the numerators and
separately multiply the denominators to get six factorial times 17 factorial over
eight factorial times 15 factorial. And then we’re going to apply the
definition of the factorial. We know 𝑛 factorial is 𝑛 times 𝑛
minus one times 𝑛 minus two all the way down to one. This means 17 factorial must be 17
times 16 times 15 and so on.

But of course, we can write that as
17 times 16 times 15 factorial. And so in our fraction, if we
replace 17 factorial with 17 times 16 times 15 factorial, we can then divide through
by 15 factorial, leaving us with six factorial times 17 times 16 over eight
factorial. But what if we now write eight
factorial as eight times seven times six factorial? In doing so, we can then divide
through by six factorial. We’re now left with 17 times 16
over eight times seven.

In fact, we have one further factor
on our numerator and denominator. We can divide through by eight,
leaving a numerator of 17 times two and a denominator of simply seven. 17 times two is, of course, 34. So we see that, without using a
calculator, we found 23 choose eight over 23 choose six to be equal to 34 over
seven.

Notice how, with some clever
manipulation and by rewriting our factorial terms slightly, we could simplify our
results really nicely. We’re now going to look at how we
can solve equations using these formulae.

If nine choose 𝑟 is equal to nine
choose three, find all the possible values of 𝑟.

Let’s begin simply by recalling
what we understand by 𝑛 choose 𝑟. 𝑛 choose 𝑟 or 𝑛𝐶𝑟, which
represents the number of combinations of size 𝑟 taken from a collection of 𝑛
items, is defined as 𝑛 factorial over 𝑟 factorial times 𝑛 minus 𝑟 factorial. We can, therefore, say that the
left-hand side of our equation nine choose 𝑟 can be written as nine factorial over
𝑟 factorial times nine minus 𝑟 factorial. We can then write the right-hand
side nine choose three as nine factorial over three factorial times nine minus three
factorial or simply nine factorial over three factorial times six factorial.

Now, of course, these are equal to
one another. In other words, nine factorial over
𝑟 factorial times nine minus 𝑟 factorial is equal to nine factorial over three
factorial times six factorial. So by comparing both sides, we
could relate 𝑟 to this value here. In this case, we’re saying that 𝑛
is equal to nine and 𝑟 is equal to three. But, in fact, there is another
value of 𝑟. This value of 𝑟 comes from the
fact that multiplication is commutative; it can be performed in any order. In other words, we can reverse the
terms on our denominator. That is, we can reverse the three
and the six.

In doing so, we don’t actually
change the value of our expression. But we can now say, “Well, 𝑛 must
be equal to nine, and 𝑟 must be equal to six.” If this is the case, then nine
minus 𝑟 should then be equal to three. Well, letting 𝑟 be equal to six,
we see that nine minus 𝑟 is nine minus six, which is indeed equal to three. And so there’s a second value of 𝑟
we could choose. 𝑟 could be equal to six. If nine choose 𝑟 is equal to nine
choose three, we can say 𝑟 could be equal to three or 𝑟 could be equal to six.

This example demonstrates the
symmetry of combinations. In fact, we can generalize and say
that 𝑛 choose 𝑟 is always equal to 𝑛 choose 𝑛 minus 𝑟. In our next example, we’ll consider
something called the recursive relationship.

By applying the relation 𝑛 choose
𝑟 plus 𝑛 choose 𝑟 minus one equals 𝑛 plus one choose 𝑟, deduce the value of 59
choose two plus 59 choose three.

This is called the recursive
relationship. And it can help us to simplify
expressions. In this case, we’re looking to
deduce the value of 59 choose two plus 59 choose three. So let’s compare this expression
with the recursive relationship. In this relation, we see that on
the left-hand side, we have two terms with the same value of 𝑛. We have 59 choose two and 59 choose
three. So we’re going to let 𝑛 be equal
to 59. Then we have 𝑟 and 𝑟 minus
one. The first term has a larger value
of 𝑟. And the second term has a value of
𝑟 that’s one less.

So let’s imagine we’re going to
swap 59 choose three and 59 choose two around so that it matches this criteria. Then we see 𝑟 must be equal to
three. 𝑟 minus one is three minus one,
which is two, as we require. According to the relation given in
the question then, 59 choose three plus 59 choose two must be equal to 𝑛 plus one,
so 59 plus one choose three. That’s 60 choose three. So to deduce the value of the
expression in our question, we need to work out what 60 choose three is.

And so we recall that 𝑛 choose 𝑟
is 𝑛 factorial over 𝑟 factorial times 𝑛 minus 𝑟 factorial. Now, we mustn’t confuse 𝑛 and 𝑟
with the values we defined earlier. This time, 𝑛 is going to be equal
to 60, and 𝑟 is still equal to three. This gives us that 60 choose three
is 60 factorial over three factorial times 60 minus three factorial or 60 factorial
over three factorial times 57 factorial. Now, we could use our calculator to
evaluate this, but let’s look at how the definition of the factorial can help us
simplify a little.

𝑛 factorial is 𝑛 times 𝑛 minus
one times 𝑛 minus two all the way down to one. This means 60 factorial is 60 times
59 times 58 and so on. But of course, we see that we can
actually rewrite that further as 60 times 59 times 58 times 57 factorial. This means our expression for 60
choose three can be rewritten as shown. And this is great because we can
now divide through by a constant factor of 57 factorial. In fact, three factorial is equal
to six, so we can also divide our numerator and denominator by six. And we see that 60 choose three is
10 times 59 times 58 over one. 59 multiplied by 58 is 3,422. So 10 times 59 times 58 is
34,220. 59 choose two plus 59 choose three
is, therefore, 34,220.

Remember, we said that this is
called the recursive relationship. And it can help us to simplify
expressions. We can generalize it a little
further and say that 𝑛 minus one choose 𝑟 plus 𝑛 minus one choose 𝑟 minus one is
equal to 𝑛 choose 𝑟.

In our last examples, we’ll look at
how to find sums of combinations.

Find the value of five choose zero
plus five choose one plus five choose two all the way up to five choose five.

To answer this question, we’re
going to recall two facts. 𝑛𝐶𝑟 or 𝑛 choose 𝑟 is found by
dividing 𝑛 factorial by 𝑟 factorial times 𝑛 minus 𝑟 factorial. But we also know that combinations
have symmetry such that 𝑛 choose 𝑟 is equal to 𝑛 choose 𝑛 minus 𝑟.

Now, let’s look at all of the terms
in our summation. We can see that 𝑛 here is going to
be equal to five. And so let’s begin by evaluating
five choose zero. In this case, 𝑟 is equal to
zero. So five choose zero is five
factorial over zero factorial times five minus zero factorial. Except, zero factorial is simply
one. So we get five factorial divided by
five factorial, which must also be equal to one. Due to this symmetry, we know that
this must also be equal to five choose five. And so we see that five choose zero
and five choose five are both equal to one.

We’re now going to work out five
choose one. That’s five factorial over one
factorial times five minus one factorial. One factorial is also one. So we get five factorial over four
factorial. But since five factorial is five
times four times three and so on, we can actually write it as five times four
factorial. This means we can divide through by
four factorial, and we find that five choose one is equal to five. And then using the symmetry, we
find that five choose four is also equal to five.

We’re now going to evaluate five
choose two and five choose three. For five choose two, we get five
factorial over two factorial times five minus two factorial, which gives us 10. Since there’s this symmetry, we
know this is also equal to five choose three. And so this means our sum is one
plus five plus 10 plus 10 plus five plus one, which is equal to 32.

Now, in fact, it’s no coincidence
that this solution is a power of two. In fact, the general rule is that
the sum of all 𝑛𝐶𝑟 for a given 𝑛 is two to the 𝑛th power. We can use summation notation. And we see that this is the sum
from 𝑟 equals zero to 𝑛 of 𝑛𝐶𝑟 is equal to two to the 𝑛th power.

Let’s consider one final
example.

Find the value of four choose zero
minus four choose one plus four choose two minus four choose three plus four choose
four.

Remember, we know that combinations
have symmetry such that 𝑛𝐶𝑟 is equal to 𝑛𝐶𝑛 minus 𝑟. And so this means that four 𝐶 zero
will be equal to four 𝐶 four and four 𝐶 one will be equal to four 𝐶 three. In fact, we can go further than
this and say that 𝑛𝐶 zero and 𝑛𝐶𝑛 are both equal to one. So we find four 𝐶 zero and four 𝐶
four are equal to one. Since 𝑛𝐶𝑟 is 𝑛 factorial over
𝑟 factorial times 𝑛 minus 𝑟 factorial, we find that four choose one is four
factorial over one factorial times three factorial, which is equal to four, giving
us four choose one is four and four choose three is four.

Let’s finally evaluate four choose
two. It’s four factorial over two
factorial times two factorial, which is equal to six. And so we’re ready to evaluate this
alternating sum. We could use summation notation as
shown. And we get one minus four plus six
minus four plus one, which is equal to zero. And so the value of our alternating
sum is zero. In fact, once again, we have a
general rule. And that is the alternating sums of
𝑛 choose 𝑟 are equal to zero. In general, we can say that the sum
from 𝑟 equals zero to 𝑛 of negative one to the power of 𝑟 times 𝑛 choose 𝑟 is
equal to zero.

In this video, we learned that the
number of combinations of size 𝑟 taken from a set of size 𝑛 is defined as 𝑛𝐶𝑟
or 𝑛 choose 𝑟. It’s equal to the number of
permutations divided by 𝑟 factorial or 𝑛 factorial over 𝑟 factorial times 𝑛
minus 𝑟 factorial. We saw that these have a reflective
property such that 𝑛 choose 𝑟 is always equal to 𝑛 choose 𝑛 minus 𝑟 and that 𝑛
choose zero and 𝑛 choose 𝑛 will always give us a value of one.

We saw that 𝑛 minus one choose 𝑟
plus 𝑛 minus one choose 𝑟 minus one is equal to 𝑛 choose 𝑟. This is called the recursive
property. And it can help us to simplify
expressions. We saw that the sum from 𝑟 equals
zero to 𝑛 of 𝑛 choose 𝑟 is two to the 𝑛th power and that the sum from 𝑟 equal
zero to 𝑛 of negative one to the power of 𝑟 times 𝑛 choose 𝑟 is equal to
zero. We saw that using the definition of
𝑛 choose 𝑟 and its properties, we can simplify expressions and solve equations
involving combinations.