Making Your Own Sense

Reflections on maths, learning and maths learning support, by David K Butler

Tag: counting

  • A story instead of stars and bars

    In a recent post (Counting the Story), I talked about how if you look closely at most solutions of combinatorics problems, you’ll see that they actually count the story of constructing the object rather than the object itself.

    One exception to this is a problem like this:

    “The balloon man has a huge collection of balloons in red, yellow and blue. I’d like to buy 10 for my granddaughter. How many collections of balloons could be made?”

    Or this:

    “The balloon man has a huge collection of identical balloons. I want to buy 10 and give them to my three grandchildren. How many ways are there to distribute them among the three children, allowing for the possibility that some children might not get any?”

    Or this:

    “The balloon man has a recurring nightmare about being asked to solve x+y+z=10 for non-negative integers x, y and z. How many solutions are there?”

    (The reason I mention the granddaughters, even though I have no granddaughters, is because I wanted to reference the most awesome Rey Casse, who used the first of these three to introduce this type of problem in my Discrete Maths II class back in 1999.)

    These three types of problems are usually solved using a method known in the USA as “stars and bars”. Google “stars and bars combinatorics” and you can find out about how it works. This is precisely the method I was taught, though with dots and lines, and I’m not aware of Australians actually giving the method a name.

    I am going to present a slightly different approach here. It will come out looking similar to the stars and bars method, but the road to getting there will be a bit different, and is based on telling a story of how to construct all of the possible solutions.

    Imagine I’m at the balloon man, and I am asking him for a particular combination of colours. One way to do this would be to say how many red ones I want, how many yellow ones I want, and how many blue ones I want, so that the total number is 10. So the number of combinations is the number of ways to choose three numbers (which could be zero) so that they add up to 10. This is precisely the same as solving the balloon man’s nightmare equation of x+y+z=10. Many people teach their students to turn such a problem into this equation and memorise the formula for the number of solutions to such an equation. They may possibly use a variant of the stars and bars to prove that the formula for the equation works.

    That’s not satisfying to me. I want to get the answer more directly from the story itself. So how about this scheme for describing how to get the balloons: put the colours in a particular order, say red, yellow, blue. Then progressively either ask the balloon man to get another balloon from this colour, or move over to the next colour.
    So if you wanted 3 reds, 2 yellows and 5 blues, you’d say “one of this colour”, “one of this colour”, “one of this colour”, “next colour”, “one of this colour”, “one of this colour”, “next colour”, “one of this colour”, “one of this colour”, “one of this colour”, “one of this colour”, “one of this colour”. If, when you got to a particular colour, you didn’t actually want any of those, you’d just move to the next colour straight away. So if you wanted 6 red, 0 yellow, 4 blue, you’d say “one of this colour”, “one of this colour”, “one of this colour”, “one of this colour”, “one of this colour”, “one of this colour”, “next colour”, “next colour”, “one of this colour”, “one of this colour”, “one of this colour”, “one of this colour”.

    You could represent these instructions with pictures. I’ve used a balloon to represent asking for a balloon, and an arrow to represent moving to the next colour. These pictures represent all the stories of choosing a collection of balloons, so now we can count the stories! There are 12 possible symbols and two of them have to be arrows, so the number of possible stories is the number of ways to choose 2 pictures out of 12 to be an arrow. That is, the number of ways is 12C2.

    Three collections of balloons, one red, one yellow and one blue. Below are two rows of symbols. The first row of symbols has three balloons, an arrow, two balloons, an arrow, and five balloons. At the end of the row is a little collection of three red, two yellow and five blue balloons. The second row of symbols has six balloons, then an arrow, then another arrow, then four balloons. At the end of the row is a little collection of six red and four blue balloons.

    Cool huh?

    Now let’s tackle the next problem. Let’s put the grandchildren in a particular order and move along the line. We can give the child we’re up to a balloon, or given them another one, or move on to the next child. Again I can represent this with pictures: a balloon for when we give a balloon, and an arrow for when we move to the next child. And again the number of allocations of balloons to children is the same as the number of ways to choose 2 out of 12 pictures to be an arrow. That is, the number of ways is 12C2.

    A collection of purple balloons with three stick figures next to it representing children. Below are two rows of symbols. The first row of symbols has three balloons, an arrow, two balloons, an arrow, and five balloons. At the end of the row is a picture of the three children with the first holding three balloons, the second holding two and the third holding five balloons. The second row of symbols has six balloons, then an arrow, then another arrow, then four balloons. At the end of the row is a picture of the three children with the first holding six balloons, the second holding none, and the third holding four balloons.

    Nice.

    On to the third problem. As I said earlier, many people teach students to reduce other problems to this, and then remember a formula for the number of ways to solve this. I, on the other hand, still tell the same sort of story. This time, I imagine starting with the equation 0+0+0=0, and then moving along the positions. At each stage I can add 1 to the number there currently, or I can move ahead to the next position. As long as I add 1 ten times, it will work. Once more, I can represent this with a picture. I’ve got “+1” for the action of increasing a position by 1, and and arrow for moving to the next position. The picture shows how to get 3+2+5=10 and 6+0+4=10. Except for the change of symbols, the pictures are the same as the other ones, so the number of solutions is still 12C2.

    An equation x + y + z = 10. Underneath is the equation 0 + 0 + 0 = 0 with the zeros in faded purple. Below are two rows of symbols. The first row of symbols has three boxes with +1, an arrow, two boxes with +1, an arrow, and five boxes with +1. At the end of the row is the equation 3 + 2 + 5 = 10. The second row of symbols has six boxes with +1, then an arrow, then another arrow, then four boxes with +1. At the end of the row is the equation 6 + 0 + 4 = 10.

    Sweet!

    In the traditional stars and bars method, the stars represent objects and the bars represent dividers between them. In my method, the symbols always represent instructions in a story of how the collection/allocation/solution is constructed. And yes the symbols do always match the context of the problem. I find this much easier to remember and apply. Plus it’s cuter!

  • Counting the story

    Combinatorics is one of my favourite topics in discrete maths – that topic which is all about counting the number of ways there are to choose, arrange, allocate or combine things. I like the idea that I could theoretically find out the answer by writing down all the possibilities systematically and literally counting them, but that I can also come up with a quick calculation that produces the same answer by just applying some creative thought. It’s this creativity in particular that appeals to me, so much so that I don’t call it combinatorics, but “creative counting”.

    Of course, not all students share my love of combinatorics. When I look into their books I can see why – they’re full of tables of formulas that split situations into repetition allowed and not allowed, identical objects versus distinguishable objects, and order important versus order unimportant. That makes it seem like it’s all about stimulus-response raw memory, and that is the opposite of creativity!

    I would love to convince students of the creative side to combinatorics, and relieve them from the burden of memory, but I also need to help them learn to solve the problems they are asked to solve. Somehow I am able to do all this in myself. If I can figure out how I do it, I might be able to pass it on to students.

    Only recently have I come to realise what it is I do to be creative, avoid memorisation and still succeed in solving problems: I tell a story. Whenever I see a counting problem, I construct a story of how the things we are counting are constructed, which proceeds in stages in a time order. Then I count the story rather than the objects themselves!

    If you think about it, this is what is often going on in the explanations for the common formulas. Take the number of permutations of n objects. You imagine constructing this permutation by choosing an object to go first, then an object to go second out of the remaining objects, and so on. There are n choices for the first object, which leaves n-1 choices for the second, and so on. Since the number of choices at the next stage is the same regardless of the choice at the previous stage, you can multiply them all together to get a total of n×(n-1)×…×2×1(also known as n!).

    Did you notice? The thing we counted along the way was the number of choices at each stage of the story! We counted the story, not the permutations. Look closely at worked examples for combinatorics problems and you’ll see the same thing happening almost all the time. What they describe is a story, and then they count the story.

    Working with a student recently, I pointed out that the key to success with creative counting is coming up with this story, and suddenly everything came together for him. He saw the common thread that connected everything, and was able to come up with his own solutions. He even came up with alternative stories for the same problem, and managed to explain to himself why to different-looking situations had the same calculation by constructing a similar story for both. I know one student doesn’t prove that it will work for all students, but it does show it’s possible!

    One final thing that help stories foster creativity is the fact that multiple stories will produce the correct answer. This allows you to celebrate each students’ choice, making it more personal, and therefore more creative. Take the following example:

    Suppose you have a televised singing competition with 30 contestants, and 12 must be chosen to go to the live shows. These people will be announced one by one on the show. If Johnny, who has the most compelling backstory, has to be chosen and has to be announced within the last three in order to increase suspense, how many possible announcements are there?

    Let’s see. We need a story for how the list is constructed.

    We could choose which position Johnny goes in, and then put everyone else in. That’s three places for Johnny, and then 29 choices for the first other position, 28 for the next, and so on. Every choice in the story goes with every other choice after it, so we get 3×29×28×…×13.

    Another way would be to choose two people to be with Johnny in that final three, then arrange them. Then choose the 9 people to be the rest of the list and arrange them. So we’d get
    9C2×3!×27C9×9!.

    We could also just make the list as we go, couldn’t we? Put down someone’s name first (who could be anyone except Johnny) and then another name (again anyone except Johnny or the first person) and so on, until we get to the last three. This is 29×28×27×26×25×24×23×22×21 so far.
    Now you can have anyone left including Johnny, and then again and again. So that’s 21×20×19 for the last three, giving 29×28×27×26×25×24×23×22×21×21×20×19 in total. But just a second, that counting arrangement isn’t guaranteed to put Johnny in the last three! Maybe we can fix that. Why don’t we count the end-of-stories that don’t end up with Johnny in the last three: 20×19×18 and take them off?
    So we get 29×28×27×26×25×24×23×22×21×(21×20×19-20×19×18).

    Finally, what if we try this one: choose the 11 other finalists, then out of those 11, chose the first person, the second person, all the way up to the ninth person. Then choose which position Johnny was in. Then chose which of the two orders the final two people were in. That would be 29C11×(11×10×9×8×7×6×5×4×3)×3×2.

    That’s four ways to tell the story, and so four ways to count the callout list, not to mention slight variations on these ways. How’s that for creativity? Not just that, but you have probably done quite a bit of maths checking that they indeed do all produce the same answer.

    Of course, you do need to know a few general principles, such as what dictates when multiplication or addition (or even division or subtraction) are useful to help you count. It also doesn’t hurt to know how to figure out the number of ways to choose a collection r things out of n things (nCr), and the number of ways to arrange n things (n!), so you can use these to make more complex stories. Once you have these elements, you can count a whole lot of things by telling the story of how you make them, and you don’t need any new formulas. That is, you can have the freedom to be creative.