Lesson Explainer: Combination Mathematics

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 𝑘=3 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 #𝑘𝑛×#𝑘=#𝑘𝑛.waystoselectfromwaystoorderrunnerswaystoorderrunnersfrom

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 𝐶?

  1. 𝑃5
  2. 𝑃5
  3. 𝑃×5
  4. 𝑃×5

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 𝑛=41 and 𝑘=5, 𝑃=4141−5=4136,𝐶=4141−55=41365.
  • We note that there is an extra 5 in the denominator of 𝐶. Multiplying 5 by 𝐶, we get 𝐶×5=41365×5=4136.
  • We note that the resulting expression is the same as the one for 𝑃. So, we have the identity 𝐶×5=𝑃. Dividing both sides of the equation by 5, we get 𝐶=𝑃5.

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 5 different ways to achieve this. Then, by the fundamental counting principle, 𝐶×5=𝑃.
  • Dividing both sides by 5, we get 𝐶=𝑃5.

Hence, the answer is option A.

Example 2: Evaluating Combinations

Evaluate 𝐶.

Answer

We recall the formula for combinations 𝐶=𝑛𝑛−𝑘𝑘.

In 𝐶, we have 𝑛=23 and 𝑘=19, so we need to compute 2323−1919=23419.

We can write 23=23×22×21×20×19 and 4=4×3×2×1, so 23419=23×22×21×20×19419=23×22×21×204×3×2×1.

We can reduce the factors: 204=5, 213=7, and 222=11. Then, the fraction on the right side of the equation above is reduced to 23×11×7×5=8855.

Therefore, 𝐶=8855.

Example 3: Evaluating Combinations

Evaluate 𝐶𝐶.

Answer

We recall the formula for combinations 𝐶=𝑛𝑛−𝑘𝑘. So, 𝐶=77−22=752𝐶=88−66=826.and

We note that dividing 𝐶 by 𝐶 to compute the given expression is equivalent to multiplying 𝐶 by the reciprocal of 𝐶. So, 𝐶𝐶=752×268=75×68.

We can write 8=8×76=6×5.and

Then, 75×68=75×6×58×7=68=34.

So, 𝐶𝐶=34.

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 𝑛=52 and 𝑘=3, giving us 𝐶=5252−33=52493.

We can write 52=52×51×50×49 and 3=3×2×1. So, 52493=52×51×50×49493=52×51×503×2×1.

We can reduce the fractions: 513=17 and 522=26. Then, the fraction on the right side of the equation above is equal to 26×17×50=22100.

This leads to 𝐶=22100.

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

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 𝑛=3+9=12, 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 12−3=9. So, 𝑛=12 should be the correct answer.

We can verify this answer by computing both combinations. Recall the formula 𝐶=𝑛𝑛−𝑘𝑘. Then, 𝐶=1212−33=1293.

On the other hand, 𝐶=1212−99=1239.

This verifies our answer: 𝑛=12.

So, if 𝐶=𝐶, then 𝑛=12.

Example 6: Evaluating Combinations to Find the Value of an Unknown

If 𝐶=120, find 𝑛.

Answer

We recall the formula for the combination: 𝐶=𝑛𝑛−𝑘𝑘.

Recall that we require 𝑛≥𝑘 when defining 𝐶. We are given 𝑘=3, so we need 𝑛≥3. So, substituting 𝑘=3 into the formula gives us 𝑛𝑛−33=120.

We multiply both sides by 3=3×2×1=6 to get 𝑛𝑛−3=720.

Since 𝑛≥3, we can write 𝑛=𝑛×(𝑛−1)×(𝑛−2)×𝑛−3. The left-hand side of the equation above is equal to 𝑛𝑛−3=𝑛×(𝑛−1)×(𝑛−2)×𝑛−3𝑛−3=𝑛(𝑛−1)(𝑛−2).

We are told this is equal to 120, so we have the equation 𝑛(𝑛−1)(𝑛−2)=720.

For any 𝑛>2, we note that (𝑛−2)<𝑛(𝑛−1)(𝑛−2)<𝑛.

So, we must have the condition (𝑛−2)<720<𝑛.

We take the cube root of the inequalities above. Since √720≈8.96, 𝑛−2<8.96<𝑛.

Since 8.96<𝑛, the integer 𝑛 must be at least 9. On the other hand, since 𝑛−2<8.96⟹𝑛<10.96, 𝑛 can be at most 10. So, 𝑛 must be either 9 or 10. Also, 𝑛 must satisfy the equation 𝑛(𝑛−1)(𝑛−2)=720. We can substitute 𝑛=9 and 𝑛=10 into this equation to see which one is the correct value of 𝑛.

If 𝑛=9, 𝑛(𝑛−1)(𝑛−2)=9×8×7=504.

Since this is not equal to 720, 𝑛≠9.

If 𝑛=10, 𝑛(𝑛−1)(𝑛−2)=10×9×8=720.

So 𝑛=10 agrees with 𝐶=120.

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 𝐶=𝐶.

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