### Combinations

In the previous lesson we looked at situations where the order of an arrangement is important. For example, when looking at 3-digit numbers, the number 123 is very different from the number 312, even though it contains the same 3 digits. But in some situations, the order is not important – for example, when looking at cards in a hand of poker, or choosing toppings to put on a pizza. In these situations, when **order is not important**, we are looking at ** combinations** of items. For example, if you are a poker player you might want to know the probability of being dealt four aces in a hand of five cards. You don’t care in which order you receive the ace cards – only the fact that you have four of them is important.

**Counting Combinations**

Just as with permutations, it’s sometimes easiest to calculate combinations by listing all the possibilities available, and counting them. The only difference is, when we list one combination, we automatically exclude a larger number of permutations. For example a poker hand that is (ace, ace, ace, ace, king\begin{align*}\clubsuit\end{align*}) is identical to (ace, ace, ace, king\begin{align*}\clubsuit\end{align*}, ace), (ace, ace, king\begin{align*}\clubsuit\end{align*}, ace, ace), (ace, king\begin{align*}\clubsuit\end{align*}, ace, ace, ace) and (king\begin{align*}\clubsuit\end{align*}, ace, ace, ace, ace). So we must be careful to use a listing method that includes all combinations without repeating ones that are really the same. Let’s examine a situation where it’s relatively straightforward to do that.

Anne wishes to knit herself a striped sweater. She has 4 colors of yarn available; red, blue, green and yellow. How many different combinations of two colors does she have to choose from?

When we just choose color pairs, there will be fewer combinations than we would have if we were counting permutations as in the previous lesson. For example ** red and blue** is equivalent to

**, and we should only count one as a unique pairing. We start by listing the color pairs but we will also write down equivalent pairings at the same time. This will help prevent us from repeating combinations:**

*blue and red*Pairing |
Equivalent pairings (do not count) |
---|---|

Red & blue | blue & red |

Red & green | green & red |

Red & yellow | yellow & red |

Green & blue | blue & green |

Green & yellow | yellow & green |

Yellow & blue | blue & yellow |

So there are 6 distinct combinations. There are also 6 “repeat” pairings – for every pair of colors we choose there is 1 combination but 2 permutations. **Anne can choose from six distinct color pairs for her sweater**.

#### Real-World Application: Pizza Toppings

Triominoes Pizza Company specializes in 3-topping pizzas. If the available toppings are cheese, pepperoni, mushroom, pineapple and olives, how many different 3-topping combinations can customers choose from?

We’ll start by making a table and list first choice, second choice and third choice:

\begin{align*}1^{st}\end{align*} topping |
\begin{align*}2^{nd}\end{align*} topping |
\begin{align*}3^{rd}\end{align*} topping |
---|---|---|

cheese | pepperoni | mushroom |

cheese | pepperoni | pineapple |

cheese | pepperoni | olives |

cheese | mushroom | pineapple |

cheese | mushroom | olives |

cheese | pineapple | olives |

pepperoni | mushroom | pineapple |

pepperoni | mushroom | olives |

pepperoni | pineapple | olives |

mushroom | pineapple | olives |

Note that as we progress through the choices for first topping, the number of combinations we have for the second and third toppings get fewer. This is because some combinations have already been used, in a different order.

By counting the table entries we see that there are **10 possibilities** for a 3-topping pizza.

**Determining Combinations by Looking at Permutations**

You can see that there are always fewer combinations than permutations in a given situation – but you should also see that knowing which combinations have already been used is important to avoid counting combinations twice. One combination can give rise to several permutations of the same objects.

Another way to calculate combinations is this: If we know how many **permutations** there are in a system and how many permutations there are for **each combination**, then we can **divide the number of permutations by the number of permutations for each combination to get the number of combinations**.

To illustrate this, look again at the *Triominoes Pizza* menu. If we were to look at **permutations** of toppings, we could quickly calculate that there are \begin{align*}5 \times 4 \times 3 = 60\end{align*} permutations. But for every 3-topping choice there are several permutations which are all equivalent. For example, the following all give identical pizzas:

\begin{align*}& \text{Cheese, pepperoni} \ \& \ \text{mushroom} \quad \text{Cheese, mushroom} \ \& \ \text{pepperoni}\\ & \text{Pepperoni, cheese} \ \& \ \text{mushroom} \quad \ \text{Pepperoni, mushroom} \ \& \ \text{cheese}\\ & \text{Mushroom, cheese} \ \& \ \text{pepperoni} \quad \ \text{Mushroom, pepperoni} \ \& \ \text{cheese}\end{align*}

So for every different combination there are 6 distinct permutations. Since we have a formula for counting permutations, we can use it to find out how many total permutations there are and simply divide that number by 6:

\begin{align*}\text{Combinations} = \frac{1}{6} \cdot _5P_3 = \frac{1}{6} \cdot \frac{5!}{2!} = \frac{1}{6} \cdot \frac{5 \times 4 \times 3 \times \cancel{2} \times \cancel{1}}{\cancel{2} \times \cancel{1}} = \frac{60}{6} = 10\end{align*}

**Find Combinations Using a Formula**

If you look back at examples 1 and 2 you can see that the number of permutations is a simple multiple of the number of combinations. In example 1 there are two times as many permutations as combinations. In example 2 there are six times as many permutations as combinations. One question you might be asking is: “How do I know how the number of combinations is related to the number of permutations?”

A more important question might be “where did the numbers two and six come from?” If you think carefully you should realize that any time you’ve chosen 2 objects, there are only 2 ways of ordering them, while if you’ve chosen 3 objects there are 3! ways of ordering them (6 ways). Similarly, if you choose 7 objects, there will be 7! ways of arranging them. We can make use of this fact when calculating combinations. The number of combinations is the number of permutations divided by the number of ways of arranging the items you choose. If you choose \begin{align*}r\end{align*} objects from a collection of \begin{align*}n\end{align*} objects there are \begin{align*}r!\end{align*} ways of arranging what you choose. In equation form, the number of combinations is therefore:

\begin{align*}{_n}C_r = \frac{n!}{(n-r)! r!}\end{align*}

In other words, the number of combinations is equal to the number of permutations divided by \begin{align*}r!\end{align*} (because \begin{align*}r!\end{align*} is the number of permutations for each combination). We can use this new formula to quickly calculate combinations without listing them all.

*Andrew is packing for a vacation. He owns twelve shirts and wants to pack five of them. How many combinations of shirts does he have to choose from?*

Since the order he packs his shirts in is not important, we are looking at a combination. He is choosing five shirts from a total of twelve:

Choosing 5 from 12: \begin{align*}_{12}C_5 = \frac{12!}{(12-5)! 5!} = \frac{12!}{7! 5! } = \frac{12 \times 11 \times 10 \times 9 \times 8 }{5 \times 4 \times 3 \times 2 \times 1} = 792 \ \text{combinations.}\end{align*}

### Example

#### Example 1

At Summerfield High School, the student council has 8 students, 3 of whom are needed to be on the prom committee. How many ways can the prom committee be chosen?

There are:

\begin{align*}{_n}C_r &= \frac{n!}{(n-r)! r!}\\ {_8}C_3 &= \frac{8!}{(8-3)! 3!}\\ {_8}C_3 &= \frac{8!}{5! 3!}\\ {_8}C_3 &= \frac{8\cdot 7\cdot 6}{ 3!}\\ {_8}C_3 &= 8\cdot 7= 56 \end{align*}

56 ways to chosen the prom committee.

### Review

For 1-3, how many combinations are possible in the following situations?

- Buying a hot-dog with
**two**of the following toppings: ketchup, mustard, chili, cheese, & pickles. - Choosing 5 CDs from a selection of 8.
- Selecting 3 games from a box containing Scrabble, Twister, Connect-4, Snap & Mousetrap.
- \begin{align*}_3C_1\end{align*}
- \begin{align*}_7C_1\end{align*}
- \begin{align*}_6C_2\end{align*}
- \begin{align*}_8C_8\end{align*}
- \begin{align*}_9C_3\end{align*}
- \begin{align*}_9C_6\end{align*}
- \begin{align*}_7C_3\end{align*}
- \begin{align*}_{17}C_4\end{align*}
- \begin{align*}_{30}C_{11}\end{align*}
- \begin{align*}_{10}C_0\end{align*}

### Review (Answers)

To view the Review answers, open this PDF file and look for section 13.5.