# Choosy

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:

1. Choosy(n, 0) = 1  There is only one way to pick out an empty group, regardless of the size of the picked-from group.
2. 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.
3. 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.
4. 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

1, 1

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.

## 4 thoughts on “Choosy”

1. Christopher

I'm only a quarter of the way through this one and I have to ask...When you write:

For the time being we’ll be content for the process to remain a total mystery,

Isn't this the "trust me" you scorned above?
I'll get back to the rest when I have some spare time. Looks interesting.

1. Chris Lusto

Let me know if you still feel that way when you finish reading the post, but I think it gets answered. "Trust me, all of this tedious algebraic browbeating will pay off in the end," is a lousy way to start a chapter. "Let's ignore the mechanical details for a while to gain a deep appreciation for the awesome math we can do without them," is much more palatable to me, both as a student and as a teacher.

2. Christopher

All right. I'm happy to concede this trust me leads to a more compelling storyline than the standard one. I can dig it.

Now for the agreeing by argumentation/critical feedback part...

No way is this a story in one act. Act one introduces little Susie Choosy and gives students a chance to familiarize themselves with her. Act two introduces her properties. Act three plays out her consequences.

You disparage (rightly so) ice cream toppings as a lame context for exploring S. Choosy's properties. What do you propose. How can you make Choosy appear to be a solution to a compelling problem?

Our man Karim asks kids how many different pairs of shoes can be designed at nike.com, and then offers a life lesson about paralysis in the face of too many choices. I suggest a more compelling reason to wonder how many pairs of shoes there are (albeit in a much crappier lesson): Could everyone in the world have a different pair?

But Choosy doesn't help us answer the question about shoes (at least not directly); that's a Fundamental Counting Principle question. So what's the problem that makes Choosy matter? I'm not going to argue that it must be a real-world problem. Pure mathematical motivations exist. But she's gotta be good for something. And I'm not sure I understand why anyone would care how many basketball teams might include Blaise.