{"id":120,"date":"2012-01-25T09:17:56","date_gmt":"2012-01-25T15:17:56","guid":{"rendered":"http:\/\/linesoftangency.wordpress.com\/?p=120"},"modified":"2012-01-25T09:17:56","modified_gmt":"2012-01-25T15:17:56","slug":"choosy","status":"publish","type":"post","link":"http:\/\/blog.chrislusto.com\/?p=120","title":{"rendered":"Choosy"},"content":{"rendered":"

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.\u00a0 To wit, combinations<\/strong>.<\/p>\n

Here is the current state of the art, according to the big boys of Advanced Algebra publishing:<\/p>\n

Fundamental Counting Principle ====> Permutations ====> Combinations ====> Pascal's Triangle ====> Binomial Theorem\u00a0 ====> Celebration<\/strong><\/p>\n

I submit that, when we do it this way, we're double-charging our students for their attention.\u00a0 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.\u00a0 It's bad marketing, and it's bad teaching.\u00a0 And we don't exactly get away scot-free in all this.\u00a0 I know I'm in for a rough couple of weeks any time I have to close my opening lesson with, \"Trust me.\"<\/p>\n

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.\u00a0 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.\u00a0 That's it, skill-wise.\u00a0 And the first step is to cut out the first two steps, at least for now, so we can dive right into combinations.<\/p>\n

A story, in one act:<\/p>\n

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?\u00a0 That would be supremely useful.\u00a0 It would be so useful, in fact, that we should all take a few minutes to daydream about it.\u00a0 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.\u00a0 Oh, and we shall name her Choosy<\/strong>.<\/em><\/p>\n

Choosy, being a respectable function, will take our inputs, do something with them, and produce outputs for our consumption.\u00a0 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.\u00a0 So Choosy is a bit of a black box, but that shouldn't bother us, particularly.\u00a0 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.\u00a0 Choosy shall be such a creature.<\/em><\/p>\n

Choosy will require two inputs.\u00a0 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.\u00a0 To avoid confusion, we'll agree upon a convention whereby we write the picked-from group first, and the picked-out group second.\u00a0 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)<\/strong>.\u00a0 She spits out 142,506<\/strong>, and we are happy.<\/em><\/p>\n

Even without knowing how, exactly, Choosy does her magic, we can perfectly predict her answers with a little bit of critical thinking.\u00a0 We notice that, by the very nature of her task, Choosy must obey the following four rules:<\/em><\/p>\n

    \n
  1. Choosy(n, 0) = 1<\/strong>\u00a0 There is only one way to pick out an empty group, regardless of the size of the picked-from group.<\/em><\/li>\n
  2. Choosy(n, n) = 1<\/strong>\u00a0 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.<\/em><\/li>\n
  3. Choosy(n, k) = 0 if k > n<\/strong>\u00a0 There is never a way for the picked-out group to be larger than the picked-from group.<\/em><\/li>\n
  4. Choosy(n, k) = Choosy(n-1, k-1) + Choosy(n-1, k)<\/strong><\/em><\/li>\n<\/ol>\n

    Now that last rule is by far the least obvious and most powerful of the bunch.\u00a0 Here's why it works.\u00a0 Let's suppose I want to count the number of ways to choose <\/em>k<\/strong> people from a pool of size <\/em>n<\/strong>.\u00a0 That's just Choosy(n, k)<\/strong>.\u00a0 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 <\/em>k<\/strong> people selected.\u00a0 If I want to count all the groups he's in<\/strong>, I will set him aside and then choose <\/em>k-1<\/strong> of the remaining <\/em>n-1<\/strong> people to join him to form a <\/em>k<\/strong>-sized group.\u00a0 That's Choosy(n-1, k-1)<\/strong>.\u00a0 If I want to count all the groups he's not in<\/strong>, then I will set him aside and pick all of my<\/em> k<\/strong>-sized groups out of the remaining <\/em>n-1<\/strong> people in the pool.\u00a0 That's Choosy(n-1, k)<\/strong>.\u00a0 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.\u00a0 But now I've counted Choosy(n, k)<\/strong> in two different ways: once without keeping track of anyone in particular, and once keeping track of Blaise.\u00a0 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)<\/strong>.<\/em><\/p>\n

    Now I have a recursive routine to generate Choosy's outputs, up to any group sizes I have the desire and patience for.\u00a0 By rules 1 and 2, I can say Choosy(0, 0) = 1<\/strong>, and Choosy(1, 0) = Choosy(1, 1) = 1<\/strong>.\u00a0 But that also gets me Choosy(2, 0) = Choosy(2, 2) = 1<\/strong>.\u00a0 My first trouble comes from Choosy(2, 1)<\/strong>, but that's not really so tough!\u00a0 By rule 4, I know that it's just the same as Choosy(1, 0) + Choosy(1, 1) = 1 + 1 = 2<\/strong>.\u00a0 I can keep going, ignoring all the <\/em>k<\/strong>'s that are bigger than their <\/em>n<\/strong>'s (thanks to rule 3), and organizing my work, perhaps triangularly:<\/em><\/p>\n

    1<\/em><\/strong><\/p>\n

    1, 1<\/em><\/strong><\/p>\n

    1, 2, 1<\/em><\/strong><\/p>\n

    1, 3, 3, 1<\/em><\/strong><\/p>\n

    ...<\/em><\/strong><\/p>\n

    And, if I'm exceedingly patient and\/or bored,\u00a0 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.<\/em><\/p>\n

    Kids can follow that story.\u00a0 Better yet, kids can write<\/em> that story (with some nudging toward rule 4).\u00a0 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<\/em>.\u00a0 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<\/strong>.<\/p>\n

    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?\u00a0 Why are we torturing numbers and symbols into little algebraic shapes in order to get at a fundamentally combinatorial idea?\u00a0 (One of my more awesome professors pejoratively called this practice \"manipulatorics<\/strong>.\")\u00a0 Even if the development of the \"combination formula\" is correct and legal and logically sound, it's conceptually uninformative and intuitively useless.\u00a0 At best it's an exercise in reducing fractions, and a terrible one.<\/p>\n

    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.\"\u00a0 I want them to learn to drive first, and maybe then we have the luxury of delving into the details of the black box.\u00a0 As in, \"Here's this really powerful tool and how to use it well.\u00a0 Once we've got that down, we can take a closer look at what makes it tick.\"\u00a0 There is value in talking about the algebraic relationships between the counting principle, permutations, and combinations, but as an afterthought, not an introduction.<\/p>\n

    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.\u00a0 The difficult bit, the important<\/em> bit, is what to do with the outputs she supplies.\u00a0 Or what inputs to feed her in order even to get<\/em> a useful output.\u00a0 Those are mathematical questions.\u00a0 How she arrived at any particular output value is an electromechanical one.\u00a0 It's interesting, just not in my class.<\/p>\n

    We have to be careful about confusing algorithmic faculty with mathematical skill, especially in their order of cultivation.\u00a0 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.\u00a0 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.\u00a0 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.\u00a0 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.<\/p>\n

    Sooner rather than later.<\/p>\n

    Special thanks to Prof. Dennis White<\/a> of the University of Minnesota for finally getting me straightened out.\u00a0 It's just too bad it had to wait until I was an adult.<\/em><\/p>\n","protected":false},"excerpt":{"rendered":"

    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.\u00a0 To wit, combinations. Here is the current state of the art, according to the big boys of Advanced Algebra publishing: Fundamental Counting […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[3],"tags":[5,9,10,32,55],"class_list":["post-120","post","type-post","status-publish","format-standard","hentry","category-math-teaching","tag-algebra","tag-binomial-theorem","tag-combinations","tag-math","tag-teaching"],"_links":{"self":[{"href":"http:\/\/blog.chrislusto.com\/index.php?rest_route=\/wp\/v2\/posts\/120","targetHints":{"allow":["GET"]}}],"collection":[{"href":"http:\/\/blog.chrislusto.com\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"http:\/\/blog.chrislusto.com\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"http:\/\/blog.chrislusto.com\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"http:\/\/blog.chrislusto.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=120"}],"version-history":[{"count":0,"href":"http:\/\/blog.chrislusto.com\/index.php?rest_route=\/wp\/v2\/posts\/120\/revisions"}],"wp:attachment":[{"href":"http:\/\/blog.chrislusto.com\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=120"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/blog.chrislusto.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=120"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/blog.chrislusto.com\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=120"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}