In this explainer, we will learn how to use combination properties to solve problems and use combinations to count possible outcomes.
The combination represents the number of different ways to select objects out of total distinct objects. The order of the objects does not matter for combinations. For this definition to be feasible, we need the parameters and to be nonnegative integers and to satisfy .
We recall that the permutation represents the number of different ways to order objects from total distinct objects. The order of the objects matters for the permutation , which distinguishes it from the combination .
To put the distinction between combinations and permutations in context, let us consider two different types of races with participants. In the first race, the top finishers receive medals with their ranks printed on the medals. For example, two different possible ways to assign medals with are pictured below.
Even though the same three runners took the top three spots in both cases, they ended up winning different medals. This is because the order of the three finishers matters since they receive different medals based on their rank. The number of different ways to assign medals for this race is the same as the number of different ways to order objects from total objects. This is given by the permutation .
Let us modify the award system of the race so that the top three finishers receive, instead of different medals, identical trophies with the word “WINNER” engraved. Under this system, the order of the top finishers does not lead to different results. For example, if we apply the modified award system to the two results above, we would have the same set of trophy winners as pictured below.
The number of different sets of trophy winners from this race is the same as the number of different ways to select objects out of total objects. This is given by the combination . Let us consider how to calculate this number using the fundamental 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 .
We recall that two events are independent if the outcome of one event does not change the number of possible outcomes of the other event.
Let us apply the fundamental counting principle to our example. We let be the event of selecting the top runners from total runners and be the event of ordering the top runners. Then, these are independent events, and applying both gives us the number of ways of ordering runners from . Next, by the fundamental counting principle, we have
As stated above, represents the number of ways to select runners from , and there are ways to order runners from total. Also, we recall that there are ways to order runners. So,
Dividing each side by , we get
This is an important identity relating combinations to permutations. Since , we get
This leads to the boxed formula below.
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
We remark that several equivalent notations are used for combinations. The notations , , and are all equivalent.
Looking at the formula , we note that there are two factors in the denominator, while the permutation only has one factor in the denominator. The extra factor in the denominator for the combination allows for an identity due to the symmetry:
Hence, we have the identity . For instance, .
We can also understand this identity from a counting perspective. The combination represents the number of different ways to select objects from total objects. But when we select objects, we create a group of objects as a by-product. So, each way of choosing objects out of total objects produces a unique way to choose objects from total objects. In short, this implies .
Let us consider a few examples to familiarize ourselves with different contexts.
Example 1: Writing Combinations in terms of Permutations
Which of the following is equal to ?
Answer
We present two methods to answer this example. For the first method, we use the formulae for permutation and combination to find their relationship. For the second method, we use the fundamental counting principle to find the solution.
Method 1
- We recall the formulae for permutation and combination: and . Since we are given and ,
- We note that there is an extra in the denominator of . Multiplying by , we get
- We note that the resulting expression is the same as the one for . So, we have the identity . Dividing both sides of the equation by , we get
Method 2
- We recall that the combination represents the number of different ways to select 5 objects from 41 total objects. On the other hand, we also recall that the permutation represents the number of different ways to order 5 objects from 41 total objects.
- We recall the fundamental counting principle, which states that the total number of distinct outcomes of multiple independent events is the product of their individual number of possible outcomes. From the definitions given above, we note that the task associated with the permutation can be decomposed into two stages. The first stage is to select 5 objects from 41 total objects, and there are different ways to do this. The second stage is to order the 5 objects, and there are different ways to achieve this. Then, by the fundamental counting principle,
- Dividing both sides by , we get
Hence, the answer is option A.
Example 2: Evaluating Combinations
Evaluate .
Answer
We recall the formula for combinations
In , we have and , so we need to compute
We can write and , so
We can reduce the factors: , , and . Then, the fraction on the right side of the equation above is reduced to
Therefore, .
Example 3: Evaluating Combinations
Evaluate .
Answer
We recall the formula for combinations So,
We note that dividing by to compute the given expression is equivalent to multiplying by the reciprocal of . So,
We can write
Then,
So, .
In the next example, we will examine a counting problem involving combinations.
Example 4: Solving a Simple Counting Problem Involving Combinations
How many 3-card hands can be chosen from a deck of 52 cards?
Answer
We recall that the combination represents the number of different ways to select objects from total distinct objects. We are counting the different collections of three cards selected from 52 distinct cards. We note that the order of the three selected cards does not matter. So, the number of ways to select 3 cards from 52 distinct cards is given by the combination .
We recall the formula for the combination:
We want to choose 3 cards from 52, so we set and , giving us
We can write and . So,
We can reduce the fractions: and . Then, the fraction on the right side of the equation above is equal to
This leads to .
So, 22 100 different 3-card hands can be chosen from a deck of 52 cards.
In the last two examples, we will consider how to identify unknown parameters in combinations.
Example 5: Evaluating Combinations to Find the Value of an Unknown
Fill in the blank: If , then .
Answer
We recall that represents the number of ways to select objects from total distinct objects, where the order of the objects does not matter. We recall the following identity for combinations:
This identity can be understood in context of a counting problem. counts the number of ways to select objects out of total objects. However, when we select objects out of total objects, we automatically create a group of the remaining objects. So, the number of ways to form a group of size should be exactly the same as the number of ways to form a group of size . The former number is given by , and the latter is given by .
In this example, we are given . If we let , then the number of ways to form a group of size 3 would be identical to the number of ways to form a group of size . So, should be the correct answer.
We can verify this answer by computing both combinations. Recall the formula . Then,
On the other hand,
This verifies our answer: .
So, if , then .
Example 6: Evaluating Combinations to Find the Value of an Unknown
If , find .
Answer
We recall the formula for the combination:
Recall that we require when defining . We are given , so we need . So, substituting into the formula gives us
We multiply both sides by to get
Since , we can write . The left-hand side of the equation above is equal to
We are told this is equal to 120, so we have the equation
For any , we note that
So, we must have the condition
We take the cube root of the inequalities above. Since ,
Since , the integer must be at least 9. On the other hand, since , can be at most 10. So, must be either 9 or 10. Also, must satisfy the equation . We can substitute and into this equation to see which one is the correct value of .
If ,
Since this is not equal to 720, .
If ,
So agrees with .
Key Points
- The combination represents the number of different ways to choose objects from total distinct objects. The order of the objects does not matter for combinations.
- The notations , , and are all equivalent.
- The permutation represents the number of different ways to order objects from total distinct objects. The order of the objects matters for permutations.
- and . Note that .
- The combination satisfies the identity .
