Lesson Video: Counting Using Combinations | Nagwa Lesson Video: Counting Using Combinations | Nagwa

# Lesson Video: Counting Using Combinations Mathematics

In this video, we will learn how to use combinations to solve counting problems.

16:10

### 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.