Lesson Explainer: Counting Using Combinations | Nagwa Lesson Explainer: Counting Using Combinations | Nagwa

Lesson Explainer: Counting Using Combinations Mathematics

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

A combination is used to count the number of different ways we can choose a certain number of elements from a given collection containing distinct elements. For instance, we would use the combination rule to count the number of different ways we can select 3 different letters from the English alphabet where the order of these letters does not matter.

The combination rule differs from the permutation rule in that the order of the selected elements does not matter. In permutations, the selections EAZ and AZE would count as two distinct outcomes, while both of these selections would be considered as the same outcome {,,}EAZ for combinations.

Let us recall the formula for combinations, which represents the number of distinct ways to choose a subset of certain size from a given collection.

Definition: Combination

Given nonnegative integers 𝑛 and 𝑘 satisfying 𝑛𝑘, the combination 𝐶 represents the number of different ways to select 𝑘 objects from the total of 𝑛 distinct objects. The order of the 𝑘 objects does not matter. Its formula is given by 𝐶=𝑛𝑛𝑘𝑘.

Let us begin with an example where we will use the combination rule to count the number of different outcomes.

Example 1: Using Combinations to Count the Number of Outcomes

Let 𝑋={𝑥𝑥,10𝑥16} and 𝑌={{𝑎,𝑏}𝑎,𝑏𝑋,𝑎𝑏}. Determine the value of 𝑛(𝑌), where 𝑛(𝑌) is the number of elements in 𝑌.

Answer

In this example, we want to count the number of distinct elements in set 𝑌, where the elements of set 𝑌 are two-element subsets of 𝑋. In other words, we need to determine the number of two-element subsets of 𝑋.

We can form a two-element subset of 𝑋 by selecting two distinct elements from set 𝑋, where the order of the elements does not matter. The number of such outcomes is given by the combination rule, which we now recall: given nonnegative integers 𝑛 and 𝑘 satisfying 𝑛𝑘, the combination 𝐶 represents the number of different ways to select 𝑘 objects from the total of 𝑛 distinct objects where the order of the 𝑘 objects does not matter. Its formula is given by 𝐶=𝑛𝑛𝑘𝑘.

Since 𝑋 contains all integers between 10 and 16, the number of elements in 𝑋 is given by 1610+1=7.

Hence, to form a two-element subset of 𝑋, we need to choose 2 distinct integers from 7 total distinct integers, where the order does not matter. This means that we can use the combination rule with 𝑛=7 and 𝑘=2, leading to the combination 𝐶. We can use the combination formula to write 𝑛(𝑌)=𝐶=7722=752=7×6×552=7×62×1=7×3=21.

Therefore, 𝑛(𝑌)=21.

In the previous example, we used the combination rule to count the number of elements in a set. We can also use this rule to solve real-world problems when we need to count the number of different ways to select a certain number of objects from a collection of distinct objects. To apply the combination rule, we need to make sure that the order of objects does not matter in context of the problem.

In the next example, we will use the combination rule to solve a real-world counting problem.

Example 2: Finding the Number of Chess Games That Can Be Played in a Tournament of n Participants

A chess tournament is to be held, where every player plays each of their opponents. Given that there are 78 participants, calculate the number of matches that will be played.

Answer

In this example, we need to count the number of different chess matches that will be played where every player plays each of their opponents. We can form each chess game by selecting 2 distinct players from the total participants. Since the order of the 2 selected players does not matter, this leads to the combination rule, which we now recall: given nonnegative integers 𝑛 and 𝑘 satisfying 𝑛𝑘, the combination 𝐶 represents the number of different ways to select 𝑘 objects from the total of 𝑛 distinct objects, where the order of the 𝑘 objects does not matter. Its formula is given by 𝐶=𝑛𝑛𝑘𝑘.

Since we are choosing 2 distinct players from 78 total participants where the order does not matter, we can apply the combination rule with 𝑛=78 and 𝑘=2 to count the number of chess matches. Using the formula above, we can write 𝐶=787822=78762=78×77×76762=78×772×1=39×77=3003.

Hence, the number of matches that will be played in this chess tournament is 3‎ ‎003.

The important distinction between combination and permutation rules is in whether or not the order of the selected elements matters. Let us recall the permutation rule for counting the number of outcomes where the order of the selected elements matters.

Definition: Permutation

Given nonnegative integers 𝑛 and 𝑘 satisfying 𝑛𝑘, the permutation 𝑃 represents the number of different ways to order 𝑘 objects from the total of 𝑛 distinct objects. Its formula is given by 𝑃=𝑛𝑛𝑘.

In the next example, we will consider real-world counting problems using both combination and permutation rules.

Example 3: Counting When Order Matters

A school’s administration is choosing the colors of its new logo. The logo is made of three letters: CHS. They would like to have a different color for each letter. The options for the colors are red, green, blue, yellow, orange, and purple.

  1. How many different ways can they color their logo?
  2. The school administration decided that, instead of having a different color for each letter, they would buy three out of the six colors, mix them all together, and then paint the whole logo in the resulting color.
    How many color options do they now have for their logo?

Answer

Part 1

For the first part, we are counting the number of different ways to paint the letters CHS using different colors for each letter. To paint the three letters using different colors, we must first choose 3 colors to use, and then arrange the selected colors in order to paint each corresponding letter. In other words, we are choosing 3 colors where the order of the selected colors matters. This leads to the permutation rule, which we now recall: given nonnegative integers 𝑛 and 𝑘 satisfying 𝑛𝑘, the permutation 𝑃 represents the number of different ways to order 𝑘 objects from the total of 𝑛 distinct objects. Its formula is given by 𝑃=𝑛𝑛𝑘.

In this example, we are ordering 3 distinct colors from 6 different colors, so we can apply 𝑛=6 and 𝑘=3 to the permutation rule. This leads to 𝑃=663=63=6×5×4×33=6×5×4=120.

Hence, there are 120 different ways to color CHS out of the six given colors so that each letter has a different color.

Part 2

For the second part, the school is painting all three letters CHS with the same color, which is produced by mixing three different colors. We are still choosing 3 different colors from 6 colors, but the order of the 3 chosen colors does not matter in this context. This leads to the combination rule, since we are counting the number of distinct outcomes where the order does not matter.

Recall that, given nonnegative integers 𝑛 and 𝑘 satisfying 𝑛𝑘, the combination 𝐶 represents the number of different ways to select 𝑘 objects from the total of 𝑛 distinct objects where the order of the 𝑘 objects does not matter. Its formula is given by 𝐶=𝑛𝑛𝑘𝑘.

In this example, we are choosing 3 different colors from 6 total colors where the order does not matter. Hence, we can apply the combination rule with 𝑛=6 and 𝑘=3 to obtain 𝐶=6633=633=6×5×4×333=6×5×43×2×1=2×5×2=20.

Therefore, there are 20 different ways to color CHS in the color produced by mixing 3 different colors from 6 given colors.

We can also apply the fundamental counting principle (also known as product rule) with the combination rule to find the number of different outcomes in a given scenario. Let us recall the counting principle.

Theorem: Fundamental Counting Principle

If we have two independent events 𝐴 and 𝐵 such that the number of possible outcomes for event 𝐴 is 𝑥 and the number of possible outcomes for event 𝐵 is 𝑦, the total number of distinct possible outcomes of these two events together is the product 𝑥×𝑦.

Two events are independent if the outcome of one event does not change the number of possible outcomes of the other event. Furthermore, the fundamental counting principle works when there are more than two events. In short, we can multiply the number of possible outcomes for each event as long as they are independent.

In the next example, we will apply the fundamental counting principle and combinations to find the number of different outcomes.

Example 4: Applications of the Counting Principle (Product Rule) and Combination

A village has 2 committees, each containing 2 people. In how many ways can the committees be formed if the members are selected from 12 people with the condition that a person can only be chosen once?

Answer

In this example, we need to select 2 committees, each containing 2 people, so that each person is selected at most once. To form 2 committees, we can first form one committee containing 2 people, and then form the other committee of 2 people chosen from the remaining 10 people in the village.

To count the number of distinct outcomes of forming two committees, we recall the fundamental counting principle: given two independent events 𝐴 and 𝐵 such that the number of possible outcomes for event 𝐴 is 𝑥 and the number of possible outcomes for event 𝐵 is 𝑦, the total number of distinct possible outcomes of these two events together is the product 𝑥×𝑦. We also recall that two events are independent if the outcome of one event does not change the number of possible outcomes of the other event.

To apply the fundamental counting principle, let 𝐴 be the event of forming the first committee containing 2 people, and 𝐵 be the event of forming the second committee of 2 people. We can see that a specific selection of the first committee does not affect the number of different outcomes of the second committee. Hence, 𝐴 and 𝐵 are independent events. We now need to find the number of each event separately and then multiply them to obtain the total number of ways to form 2 committees.

First, let us determine the number of different ways to form the first committee. To form the first committee, we need to choose 2 different people from 12 people where the order of the 2 selected people does not matter. This leads to the combination rule, which we now recall: given nonnegative integers 𝑛 and 𝑘 satisfying 𝑛𝑘, the combination 𝐶 represents the number of different ways to select 𝑘 objects from the total of 𝑛 distinct objects where the order of the 𝑘 objects does not matter. Its formula is given by 𝐶=𝑛𝑛𝑘𝑘.

Here, we are choosing 2 different people from 12 people where the order does not matter, so we can apply the combination rule with 𝑛=12 and 𝑘=2, leading to 𝐶=121222=12102=12×11×10102=12×112×1=6×11=66.

Hence, there are 66 different ways to select the first committee.

Next, let us count the different ways to select the second committee. The second committee is chosen out of 10 remaining people in the village, so we can apply the combination rule with 𝑛=10 and 𝑘=2, which leads to 𝐶=101022=1082=10×9×882=10×92×1=5×9=45.

This tells us that there are 45 different ways to select the second committee.

Finally, we can apply the product rule to obtain the total number of ways to form the 2 committees, each containing 2 people. Multiplying these numbers gives us 66×45=2970.

Therefore, there are 2‎ ‎970 different ways to choose 2 committees, each containing 2 people, so that no person is chosen more than once.

Let us consider another example where we need to apply the product rule and combination rule together.

Example 5: Counting Using the Product Rule and the Combination Rule

There are 7 red balls and 6 white balls in a bag. Determine the number of ways of selecting 4 red balls and 3 white balls.

Answer

In this example, we need to determine the number of different ways to select 4 red balls and 3 white balls where each ball is distinct. To make this selection, we can begin by choosing 4 red balls and then choosing 3 white balls.

We recall the fundamental counting principle: given two independent events 𝐴 and 𝐵 such that the number of possible outcomes for event 𝐴 is 𝑥 and the number of possible outcomes for event 𝐵 is 𝑦, the total number of distinct possible outcomes of these two events together is the product 𝑥×𝑦. We also recall that two events are independent if the outcome of one event does not change the number of possible outcomes of the other event.

To apply the fundamental counting principle, let 𝐴 be the event of choosing 4 red balls and 𝐵 be the event of choosing 3 white balls. We can see that a specific selection of 4 red balls does not affect the number of different ways to choose 3 white balls. Hence, 𝐴 and 𝐵 are independent events. We now need to find the number of each event separately and then multiply them to obtain the total number of ways to choose 4 red balls and 3 white balls.

First, let us determine the number of different ways to select the red balls. We note that the order of 4 selected red balls does not matter. Since we are counting the number of distinct outcomes where the order does not matter, we recall the combination rule: given nonnegative integers 𝑛 and 𝑘 satisfying 𝑛𝑘, the combination 𝐶 represents the number of different ways to select 𝑘 objects from the total of 𝑛 distinct objects where the order of the 𝑘 objects does not matter. Its formula is given by 𝐶=𝑛𝑛𝑘𝑘.

We are choosing 4 different red balls from 7 distinct red balls where the order does not matter, so we can apply the combination rule with 𝑛=7 and 𝑘=4. This leads to 𝐶=7744=734=7×6×5×434=7×6×53×2×1=7×1×5=35.

Hence, there are 35 different ways to choose 4 red balls.

Next, let us count different ways to select the white balls. We are choosing 3 white balls from 6 white balls where the order does not matter, so we can apply the combination rule with 𝑛=6 and 𝑘=3 to obtain 𝐶=6633=633=6×5×4×333=6×5×43×2×1=2×5×2=20.

Thus, there are 20 different ways to select 3 white balls.

Finally, we can apply the product rule to find the total number of different selections. Multiplying the two numbers we get 35×20=700.

Therefore, there are 700 different ways to select 4 red balls and 3 white balls from the bag.

Let us finish by recapping a few important concepts from this explainer.

Key Points

  • Given nonnegative integers 𝑛 and 𝑘 satisfying 𝑛𝑘, the combination 𝐶 represents the number of different ways to select 𝑘 objects from the total of 𝑛 distinct objects. The order of the 𝑘 objects does not matter. Its formula is given by 𝐶=𝑛𝑛𝑘𝑘.
  • The combination rule is used in counting problems where the order of selected elements does not matter. If the order of selected elements matters, we need to apply the permutation rule.

Download the Nagwa Classes App

Attend sessions, chat with your teacher and class, and access class-specific questions. Download the Nagwa Classes app today!

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