Combinations
Learning Outcomes
- Find the number of combinations of n distinct choices.
[latex]\text{C}\left(n,r\right)=\dfrac{n!}{r!\left(n-r\right)!}[/latex]
An earlier problem considered choosing 3 of 4 possible paintings to hang on a wall. We found that there were 24 ways to select 3 of the 4 paintings in order. But what if we did not care about the order? We would expect a smaller number because selecting paintings 1, 2, 3 would be the same as selecting paintings 2, 3, 1. To find the number of ways to select 3 of the 4 paintings, disregarding the order of the paintings, divide the number of permutations by the number of ways to order 3 paintings. There are [latex]3!=3\cdot 2\cdot 1=6[/latex] ways to order 3 paintings. There are [latex]\frac{24}{6}[/latex], or 4 ways to select 3 of the 4 paintings. This number makes sense because every time we are selecting 3 paintings, we are not selecting 1 painting. There are 4 paintings we could choose not to select, so there are 4 ways to select 3 of the 4 paintings.tip for success
Note the similarity and difference between the formulas for permutations and combinations: Permutations (order matters), [latex]P(n, r)=\dfrac{n!}{(n-r)!}[/latex] Combinations (order does not matter), [latex]C(n, r)=\dfrac{n!}{r!(n-r)!}[/latex] The formula for combinations is the formula for permutations with the number of ways to order [latex]r[/latex] objects divided away from the result.A General Note: Formula for Combinations of n Distinct Objects
Given [latex]n[/latex] distinct objects, the number of ways to select [latex]r[/latex] objects from the set is[latex]\text{C}\left(n,r\right)=\dfrac{n!}{r!\left(n-r\right)!}[/latex]
How To: Given a number of options, determine the possible number of combinations.
- Identify [latex]n[/latex] from the given information.
- Identify [latex]r[/latex] from the given information.
- Replace [latex]n[/latex] and [latex]r[/latex] in the formula with the given values.
- Evaluate.
Example: Finding the Number of Combinations Using the Formula
A fast food restaurant offers five side dish options. Your meal comes with two side dishes.- How many ways can you select your side dishes?
- How many ways can you select 3 side dishes?
Answer:
- We want to choose 2 side dishes from 5 options. [latex]\text{C}\left(5,2\right)=\dfrac{5!}{2!\left(5 - 2\right)!}=10[/latex]
- We want to choose 3 side dishes from 5 options. [latex]\text{C}\left(5,3\right)=\dfrac{5!}{3!\left(5 - 3\right)!}=10[/latex]
Analysis of the Solution
We can also use a graphing calculator to find combinations. Enter 5, then press [latex]{}_{n}{C}_{r}[/latex], enter 3, and then press the equal sign. The [latex]{}_{n}{C}_{r}[/latex], function may be located under the MATH menu with probability commands.Q & A
Is it a coincidence that parts (a) and (b) in Example 4 have the same answers?
No. When we choose r objects from n objects, we are not choosing [latex]\left(n-r\right)[/latex] objects. Therefore, [latex]C\left(n,r\right)=C\left(n,n-r\right)[/latex].Try It
An ice cream shop offers 10 flavors of ice cream. How many ways are there to choose 3 flavors for a banana split?Answer: [latex-display]C\left(10,3\right)=120[/latex-display]
[embed]Finding the Number of Subsets of a Set
We have looked only at combination problems in which we chose exactly [latex]r[/latex] objects. In some problems, we want to consider choosing every possible number of objects. Consider, for example, a pizza restaurant that offers 5 toppings. Any number of toppings can be ordered. How many different pizzas are possible? To answer this question, we need to consider pizzas with any number of toppings. There is [latex]C\left(5,0\right)=1[/latex] way to order a pizza with no toppings. There are [latex]C\left(5,1\right)=5[/latex] ways to order a pizza with exactly one topping. If we continue this process, we get[latex]C\left(5,0\right)+C\left(5,1\right)+C\left(5,2\right)+C\left(5,3\right)+C\left(5,4\right)+C\left(5,5\right)=32[/latex]
There are 32 possible pizzas. This result is equal to [latex]{2}^{5}[/latex]. We are presented with a sequence of choices. For each of the [latex]n[/latex] objects we have two choices: include it in the subset or not. So for the whole subset we have made [latex]n[/latex] choices, each with two options. So there are a total of [latex]2\cdot 2\cdot 2\cdot \dots \cdot 2[/latex] possible resulting subsets, all the way from the empty subset, which we obtain when we say "no" each time, to the original set itself, which we obtain when we say "yes" each time.tip for success
Did you notice a pattern when you calculated the 32 possible pizzas long-hand? [latex-display]C\left(5,0\right)+C\left(5,1\right)+C\left(5,2\right)+C\left(5,3\right)+C\left(5,4\right)+C\left(5,5\right)=1+5+10+10+5+1=32[/latex-display] That is not a coincidence! We'll look more deeply at this phenomenon in the next section.A General Note: Formula for the Number of Subsets of a Set
A set containing n distinct objects has [latex]{2}^{n}[/latex] subsets.Example: Finding the Number of Subsets of a Set
A restaurant offers butter, cheese, chives, and sour cream as toppings for a baked potato. How many different ways are there to order a potato?Answer: We are looking for the number of subsets of a set with 4 objects. Substitute [latex]n=4[/latex] into the formula.
[latex]{2}^{n}={2}^{4} =16[/latex]
There are 16 possible ways to order a potato.Try It
A sundae bar at a wedding has 6 toppings to choose from. Any number of toppings can be chosen. How many different sundaes are possible?Answer: 64 sundaes
[ohm_question]7175[/ohm_question]Licenses & Attributions
CC licensed content, Original
- Revision and Adaptation. Provided by: Lumen Learning License: CC BY: Attribution.
CC licensed content, Shared previously
- College Algebra. Provided by: OpenStax Authored by: Abramson, Jay et al.. Located at: https://openstax.org/books/college-algebra/pages/1-introduction-to-prerequisites. License: CC BY: Attribution. License terms: Download for free at http://cnx.org/contents/[email protected].
- Question ID 7175, 7156. Authored by: unknown, mb Lippman,David, mb Sousa,James. License: CC BY: Attribution.
- Ex: Determine the Number of Ways 6 Books can be Selected from 9 Books (Combination). Provided by: OpenStax Authored by: James Sousa (Mathispower4u.com). License: CC BY: Attribution.