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 explanatons 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.
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 calculaton 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*…*19.
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 (29C2)*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 of r things out of n, and the number of ways to arrange n things, 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.