Lesson Video: Counting Using Combinations

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

16:12

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.

Nagwa uses cookies to ensure you get the best experience on our website. Learn more about our Privacy Policy.