Something deeply unsettling is afoot in the land of math education when I'm teaching the same backwards thing in the same backwards way it was presented to me as a high school kid. To wit, combinations.
Here is the current state of the art, according to the big boys of Advanced Algebra publishing:
Fundamental Counting Principle ====> Permutations ====> Combinations ====> Pascal's Triangle ====> Binomial Theorem ====> Celebration
I submit that, when we do it this way, we're double-charging our students for their attention. We bog them down in unnecessary algebraic trifling, and we go out of our way to delay the payoff for just as long as possible. It's bad marketing, and it's bad teaching. And we don't exactly get away scot-free in all this. I know I'm in for a rough couple of weeks any time I have to close my opening lesson with, "Trust me."
Beyond all that, we're missing a great and rare opportunity for kids to do some fairly sophisticated reasoning without the math getting in its own way. In fact, if you play your cards right, you can get to within an inch of the binomial theorem using only addition, and you can get all the way there if you bring in the distributive property. That's it, skill-wise. And the first step is to cut out the first two steps, at least for now, so we can dive right into combinations.
A story, in one act:
Wouldn't it be nice if we had a function that told us how many ways we could pick groups of things from other groups of things? That would be supremely useful. It would be so useful, in fact, that we should all take a few minutes to daydream about it. We needn't bother with the details, as dream functions are always 100% reliable, so we're free to ponder a few of the features we'd like a sensible, standard-model picking function to have when it rolls off the assembly line. Oh, and we shall name her Choosy.
Choosy, being a respectable function, will take our inputs, do something with them, and produce outputs for our consumption. For the time being we'll be content for the process to remain a total mystery, so long as reasonable inputs lead to reasonable outputs. So Choosy is a bit of a black box, but that shouldn't bother us, particularly. I have no idea, for instance, what goes on inside my computer's guts, but when I push the little button that looks like an 'h,' it spits out a little symbol that looks like an 'h,' and I am happy. Choosy shall be such a creature.
Choosy will require two inputs. She'll have to know the size of the group she's picking from, along with the size of the group she's required to pick out of it. To avoid confusion, we'll agree upon a convention whereby we write the picked-from group first, and the picked-out group second. So if we wanted to ask, for example, how many basketball teams we can make from a class of 30 students, our query would look like this: Choosy(30, 5). She spits out 142,506, and we are happy.
Even without knowing how, exactly, Choosy does her magic, we can perfectly predict her answers with a little bit of critical thinking. We notice that, by the very nature of her task, Choosy must obey the following four rules:
- Choosy(n, 0) = 1 There is only one way to pick out an empty group, regardless of the size of the picked-from group.
- Choosy(n, n) = 1 There is only one way for the size of the picked-out group to match the size of the picked-from group, i.e., she picks everybody.
- Choosy(n, k) = 0 if k > n There is never a way for the picked-out group to be larger than the picked-from group.
- Choosy(n, k) = Choosy(n-1, k-1) + Choosy(n-1, k)
Now that last rule is by far the least obvious and most powerful of the bunch. Here's why it works. Let's suppose I want to count the number of ways to choose k people from a pool of size n. That's just Choosy(n, k). One of those people, let's call him Blaise, is exceedingly important to me, and so I always like to keep track of whether or not he's among the k people selected. If I want to count all the groups he's in, I will set him aside and then choose k-1 of the remaining n-1 people to join him to form a k-sized group. That's Choosy(n-1, k-1). If I want to count all the groups he's not in, then I will set him aside and pick all of my k-sized groups out of the remaining n-1 people in the pool. That's Choosy(n-1, k). Since the two cases are mutually exclusive (I assume Blaise is mortal and thus can't be both in and out of a selected group) and exhaustive (there can't be a group that doesn't either contain or not contain him), I can simply take the sum of the two counts to find the total number of possible groups. But now I've counted Choosy(n, k) in two different ways: once without keeping track of anyone in particular, and once keeping track of Blaise. Since the two things I've counted are the same, they must be equal, and so Choosy(n, k) is indeed the same as Choosy(n-1, k-1) + Choosy(n-1, k).
Now I have a recursive routine to generate Choosy's outputs, up to any group sizes I have the desire and patience for. By rules 1 and 2, I can say Choosy(0, 0) = 1, and Choosy(1, 0) = Choosy(1, 1) = 1. But that also gets me Choosy(2, 0) = Choosy(2, 2) = 1. My first trouble comes from Choosy(2, 1), but that's not really so tough! By rule 4, I know that it's just the same as Choosy(1, 0) + Choosy(1, 1) = 1 + 1 = 2. I can keep going, ignoring all the k's that are bigger than their n's (thanks to rule 3), and organizing my work, perhaps triangularly:
1, 2, 1
1, 3, 3, 1
And, if I'm exceedingly patient and/or bored, I can keep adding up numbers until I hit the 6th entry in the 31st row (remember I start my counting at 0) and verify that there are precisely 142,506 potential basketball teams to be drafted out of 30 total players.
Kids can follow that story. Better yet, kids can write that story (with some nudging toward rule 4). And if you can get them to acknowledge that raising a binomial to some power means counting all the ways you can pluck out combinations of terms to multiply together, then the binomial theorem is a fait accompli. I'll say that again: one of the more significant theorems in mathematics follows naturally from a thought experiment that any student can participate in and that requires virtually no mathematical manipulation.
So why are we burying the lead six sections deep in a seven-section chapter, behind a bunch of factorials and questions about ice cream toppings? Why are we torturing numbers and symbols into little algebraic shapes in order to get at a fundamentally combinatorial idea? (One of my more awesome professors pejoratively called this practice "manipulatorics.") Even if the development of the "combination formula" is correct and legal and logically sound, it's conceptually uninformative and intuitively useless. At best it's an exercise in reducing fractions, and a terrible one.
I don't want to spend two weeks having my kids stare at timing belts and distributor caps and then say, "Now go take this baby for a spin." I want them to learn to drive first, and maybe then we have the luxury of delving into the details of the black box. As in, "Here's this really powerful tool and how to use it well. Once we've got that down, we can take a closer look at what makes it tick." There is value in talking about the algebraic relationships between the counting principle, permutations, and combinations, but as an afterthought, not an introduction.
The actual calculation of combinations is, and should be, trivial. It turns out that anybody with about $7 can purchase a brand new Choosy, straight from the factory. The difficult bit, the important bit, is what to do with the outputs she supplies. Or what inputs to feed her in order even to get a useful output. Those are mathematical questions. How she arrived at any particular output value is an electromechanical one. It's interesting, just not in my class.
We have to be careful about confusing algorithmic faculty with mathematical skill, especially in their order of cultivation. I have kids whose entire mathematical self-worth hinges on the ease or difficulty with which they can factor trinomials and invert 2x2 matrices without a calculator. The kids who are great mechanics may or may not be superb drivers, but they won't know it for awhile, and it'll be a terrible shock. And the kids who are struggling with the mechanical skills give up before they realize that driving might come naturally in the very near future. We owe it to both groups, especially when a particular topic hands itself over to us so beautifully as this one, to start our students down the right road.
Sooner rather than later.
Special thanks to Prof. Dennis White of the University of Minnesota for finally getting me straightened out. It's just too bad it had to wait until I was an adult.