14.4 Combinations

Once again, this one is lecture, without an in-class worksheet, walking through a series of questions.

Suppose you have a Daisy, an Iris, a Lily, a Rose, and a Violet. You are going to make a floral arrangement with three of them. How many possible arrangements can you make?

Based on yesterday, it’s tempting to answer $5\times 4\times 3$ , or $\frac{5!}{2!}$ . But here’s why this is different from yesterday’s problems: order doesn’t matter. “A rose, a daisy, and an iris” is the same arrangement as “A daisy, an iris, and a rose”: you don’t want to count it twice.

So, let’s start the way we did yesterday: list them all. Give the class a minute to do this. Remind them, as always, that it’s best to be systematic to make sure you list every possibility exactly once. Here’s my list.

10 items in all. I generated the list by using the same kind of systematic approach I used for the permutations, but always moving forward in the list: so after “Lily” I’m allowed to list “Rose” and “Violet,” but not “Daisy” or “Iris.”

This turns out to be such a common and important operation that it gets its own name: “choose.” We would say “5 choose 3 is 10,” sometimes written $\left(\begin{array}{c}5\\ 3\end{array}\right)=10$ . It means, if you have five items, and want to choose 3 of them, there are ten ways to do so.

Give the class a minute to list—they should make a diagram like the one I made above!—and count. When they are done, you can point out that the answer (four combinations) is very obvious if you look at it backward: each combination leaves exactly one Beatle out. There is a very important insight here, which can also be applied to the flower example: each arrangement listed leaves exactly two flowers out. So 5 choose 3 (“which flowers should I include?”) is the same number as 5 choose 2 (“which flowers should I leave out?”).

Now we’re going to try something with bigger numbers. A drama teacher looks out at a class of 30 students, and wants to choose 2 of them to run a scene. How many possible pairs of students are there? As before, when the numbers get this large, we can’t reasonably list all the combinations: we need an algebraic way of figuring out how many there are, without actually counting them all.

To start off, let’s turn this combinations (“order doesn’t matter”) problem into a permutations (“order does matter”) problem. The teacher wants to choose one student to play the Child and one to play the Dog. In this version of the problem, “John plays the Child and Susan plays the Dog” is different from “Susan plays the Child and John plays the Dog,” and should be counted separately. So it is a straightforward permutations problem. There are 30 possible actors for the Child, and for each of those, 29 for the Dog. $30\times 29=870$ possible scenes.

Now let’s return to the original problem, how many pairs of students are there? In this problem, “John-Susan” and “Susan-John” are the same pair. The key insight here is that, when we ran the permutations problem, we counted each pair twice. So the answer is $870/2=435$ pairs.

Take this slow and easy. This is a very general approach to combinations problem. First, you solve the (easier) permutations problem. Then you ask, “How many times did I count every group?” and divide by that.

Ask the class to try this approach on the original (flower) problem. They should answer three questions.

• How many permutations are there? Remember that in this question, “rose–daisy–iris” and “daisy–iris–rose” are two different arrangements, as if each flower is being placed in a numbered slot.
• Now, when we counted up the permutations, how many times did they redundantly count each combination?
• Divide the first answer by the second, and you have the total number of combinations.

Lay out the process, then have them work the problem. Many of them will get stuck on step (2), incorrectly thinking that we counted each permutation three times. In fact, we counted each one six times:

daisy–iris–rose, daisy–rose–iris, iris–daisy–rose, iris–rose–daisy, rose–daisy–iris, rose–iris–daisy

The permutations are $5\times 4\times 3$ , or $\frac{5!}{2!}$ , or 60. But each combination is listed six times, so the total number of combinations is 10, as we counted before.

So...why six times? This is the last question, and it’s a hard one. When we were choosing two items, we counted each combination twice (John–Susan, Susan–John). When we were choosing three items, we counted each combination six times. What’s the pattern? Give them a minute to think about this. Then make sure they understand that it is, in fact...another permutations problem! The list of six I gave above is simply the number of ways you can arrange three items, or (3!). You would divide by (4!) for 4 items, and so on.

Homework

A sample test, and real test, and you’re done!