In this explainer, we will learn how to use the properties of combinations to simplify expressions and solve equations.
A combination is a selection of items chosen without repetition from a collection of items in which order does not matter. The key difference between a combination and a permutation is the idea that order does not matter. For a permutation, order matters. Consider counting the number of ways we can assign the role of president and vice president to a group of 5 people: Mona, Amer, Samar, Bassem, and Dalia. If we choose Mona, then Dalia, this would not be the same as Dalia, then Mona since the first choice would be the president and the second the vice president. However, if we just wanted a committee of two people, it would not matter if we chose Mona, then Dalia or Dalia, then Mona. Hence, counting with permutations results in us overcounting the number of possible choices if order does not matter. In fact, we overcount by a factor of exactly . Therefore, we can define the number of combinations from as the number of permutations of divided by .
Definition: Number of Combination of a Given Size
The number of combinations of size taken from a collection of items is given by
The notation can be read as -- or as choose and is also referred to as the binomial coefficient. Another extremely common notation for is ; however, there are also various other forms of notation commonly used such as , , , and .
This explainer will focus on the key properties of and how we can apply these to simplify expressions and solve equations. We begin by looking at an example where we use the formula to evaluate an expression involving combinations.
Example 1: Evaluating Combinations
Determine the value of without using a calculator.
Substituting and , we have
Similarly, substituting in and , we have
Substituting these into the given expression, we get
Using rules of fractions, we can rewrite this as
Canceling the common factor of , we have
Since , we can simplify this further to get
To solve the previous example, we could have simply used the combinations function on our calculator to evaluate the expression. However, growing in fluency in manipulating the formulae for permutations and combinations will give us the necessary skills we need to tackle more challenging problems.
Let’s consider an example where we find an unknown from an equation that involves a permutation and a combination.
Example 2: Equality of Combinations and Permutations
If , find the value(s) of .
Recall, from the definition of combinations, that we have
Substituting this into the given equation results in
Cross multiplying by and dividing by , we can rewrite this as
We might be temped to immediately jump to the conclusion that . However, this would only be a partial answer since, recalling the definition of the factorial, we also have that .
Notice that when , we have and when , we have
Hence, the two possible values of are 1 and 0.
In the next example, we will find the expression involving permutations which is equal to a given expression involving combinations.
Example 3: Relationship between Combinations and Permutations
Which of the following is equal to ?
We begin by noting that . Hence, we can rewrite out the expression:
Since all we are trying to find is an expression involving permutations, we should try to express the combinations in terms of permutations. To do this, we can use the definition that to rewrite our expression as
Canceling , we have which we can also write as
Recalling the property of permutations that , we can we rewrite
Therefore, the correct answer is C.
Thus far, we have simply used the definition and formula for to solve problems. Many problems involving combinations can be solved this way. However, oftentimes, we can solve problems in a simpler and more straightforward manor by being familiar with the properties of combinations. One such property is related to the symmetry of combinations.
Notice from the definition of that there is a symmetry about the denominator. If we substitute for in the formula, we find that we get the same expression:
This leads to the general identity for combinations.
Identity: Symmetry of Combinations
Given positive integers and satisfying , we have
This has some interesting implications for solving equations involving with unknowns in . The next example will demonstrate one such implication.
Example 4: Symmetry of Combinations
Find the possible values of which satisfy the equation .
Using the rule , we get that
Thus, or .
The last example demonstrated that if then or .
Let’s consider another example that requires symmetry of combinations.
Example 5: Using the Symmetry of Combinations
If , find .
Using the property that , we can rewrite . Substituting this into the given equation, we find
This implies that or . Since the latter of these is inconsistent, we have that the only solution is .
In the next example, we will determine an unknown constant in combinations when we are given that the expressions involving combinations form an arithmetic sequence.
Example 6: Solving Combinations Problems
Given that is an arithmetic sequence, find all possible values of .
In an arithmetic sequence, there is a constant difference between consecutive terms. Hence, the difference between the first two and last two terms will be equal and we can write
Rearranging, we get
Using the definition we can rewrite this as
Dividing by the common factor of , we have
We can now multiply through by to get
Using the property of the factorial that , we can rewrite this as
Canceling the common factors in the numerators and denominators, we have
We can now divide through by 6 to get
Expanding the parentheses, we get
By gathering like terms, we arrive at the quadratic
Solving this by factoring or by the quadratic formula yields and .
One of the other key properties of combinations is the recursive relationship:
Formula: Recursive Relationship in Combinations
To derive this formula, we can use the definition to write the left-hand side as
We would like to express this as a single fraction over the common denominator of . We can do this by multiplying the first term by and the second term by as follows:
Using the properties of factorials that , we can rewrite this as
Expressing this as a single fraction and expanding the parentheses, we have
Simplifying and using the same rule of factorials, we have as required.
We will now turn our attention to one example where we apply this property to simplify an equation.
Example 7: Pairwise Sums of Combinations
Determine the value of .
This expression looks like it will be extremely laborious to evaluate or difficult to simplify. However, the first insight we gain is through noticing that when in the sum, we have the term . Taking this term out of the summation, we have
At this point, we can apply the recursive relationship, and simplify this to
Now we see that if we do the same thing again and take the last term out of the summation, we have
Continuing the same method, we will eventually get to the last term in the sum, , and have the expression
Therefore, the whole expression simplifies to
For the final couple of examples, we will consider the sums of all combinations for a given .
Example 8: Sums of Combinations
Find the value of .
Using the definition we can rewrite this expression as
Evaluating each term, we have
In the last example, we found that the sum of all combinations for is 32; it is no coincidence that this is equal to . In fact, the general rule is that the sum of all for any given is equal to . We can write this as or more concisely, we have the following identity.
Identity: Summation of Combinations
For any positive integer , we have
This rule is maybe not so surprising when we consider the recursive relationship for each term:
Since this does not apply for or , we can rewrite the sum as
Since and , we can rewrite this expression as
Regrouping the terms, we have
Therefore, the sum of the is twice the sum of . Moreover, since , we can see that the sum of for a given will be a power of two; in particular, it will be .
Finally, we will consider the alternating sum of combinations.
Example 9: Alternating Sums of Combinations
Find the value of .
Recall that . Using this, we see that
Evaluating each term gives us
Once again, this is a general rule, that the alternating sums of are zero: or, more concisely,
Identity: Alternating Sum of Combinations
For any positive integer , we have
An alternative way to represent this is that the sums of odd and even terms are equal. This is not surprising when is odd due to the reflective symmetry: . However, as the previous example showed, this is also true for even .
Let’s recap a few important concepts from the explainer.
- The number of combinations of size taken from a set of size is given by
- Combinations have the following key properties: given positive integers and satisfying ,
- Symmetry property:
- Recursive property:
- Alternating sum:
- Using the definition of and its properties, we can simplify many expressions and solve equations involving combinations.