Lesson Video: Properties of Combinations Mathematics

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.