BLOGS WEBSITE

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 ballooon 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.

choosing coloured 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.

allocating balloons to children

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.

solving diophantine equation

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!

This entry was posted in Isn't maths cool?, Thoughts about maths thinking and tagged , . Bookmark the permalink.
 

Leave a Reply