Combinatorics: Permutations

Even though counting is the first mathematical concept almost every kid learns, somehow a significant portion of cutting edge math research relates to questions that basically boil down to counting. Mathematicians call this field combinatorics, which is essentially a term for all the problems that start with the words "how many." The mathematician Regina described the field best, simply calling it "a faster way to count".

You probably bump into these questions every day, even if it's not crucial that you actually solve them. Questions like “how many ways can I choose 10 M&Ms so I have at least one of each color?” or “how many ways can I walk to work if I need to stop at Dunkin Donuts, Krispy Kreme, and IHOP on the way?” We’re going to figure out how to calculate permutations (ordered arrangements) by answering the question "how many ways can I schedule the 11 events I have lined up for my kid's eighth birthday party?"

You could count each of the event schedules one by one, but trust me when I say it would take a really long time because there are literally millions. The good news is that there's a much more efficient way. You can start by counting how many ways we can pick the first event. Since there are 11 events, there are 11 ways. Then you choose what comes second, which you have to choose from the remaining 10. Then you have 9 options for the third event and so on until you have 2 options for the tenth event and only 1 left over for the 11th.

I know from grading one too many discrete math exams that it is very tempting to say "11 options for the first choice plus 10 for the second plus 9 for the third ... plus 2 for the tenth plus 1 for the last means that are 11 + 10 + ... + 2 + 1 = 66 possible schedules." I'm going to let you in on a little trade secret. Even though that mistake is a pretty reasonable one, every time someone makes it a mathematician cries in a broom closet. Instead of taking this (incorrect) shortcut, let's think the thing through more carefully.

It will be a little more approachable if we start by thinking about how many ways there are to pick and order the first 2 events and then hope that gives us some intuition about how to finish the problem (spoiler alert: it will). If we have the “running with scissors race” first, there are 10 options for the second event. So just for the choice of starting the party with the race there are 10 ways to pick and order the first 2 events.

What if instead we chose to start with the bleach tasting contest? Then we have 10 options for the second event so just for the choice of starting the party with the tasting contest there are 10 ways to pick and order the first 2 events. Notice that these 10 orderings are all different from the 10 orderings we would have if we chose the race first. It's true that in either case we may pick both the race and the tasting contest as the first 2 events, but the order, which is ultimately what you care about, depends on which one you choose to do first.

These schedules are almost identical and both start with the tasting contest and the race, but the orders are reversed so the schedules are not identical.

If you continue this thought process for all 11 events, we notice that each choice of a first event, whether it be roof tobogganing, exploring the rusty tool shed, or the keg race, gives us 10 new ways to pick and order the first 2 events. Putting these all together we see that there are 10 + 10 + 10 + 10 + 10 + 10 + 10 + 10 + 10 + 10 + 10 (that was eleven '10's in case you don't feel like counting for whatever reason) possible ways to order the first two events. But if you think back a very long way, we have a nice expression for adding 10 eleven times. It's 11 times 10. It's multiplication! It's second grade!

You can go through all 11 choices this way. You just saw that we have 11 x 10 ways to schedule the first 2 events. For each of these first-two-event-schedules you have 9 choices for the third event, so you have 9 + ... + 9 (with 110, which is eleven times ten, '9's) ways to schedule the first 3 events. In other words you have 11 x 10 x 9 ways to schedule the first three events. For each of these there are 8 ways to schedule the fourth event, so you multiply by 8 and so on until we see that once you get to the last event, you have 11 x 10 x 9 x 8 x 7 x 6 x 5 x 4 x 3 x 2 x 1 possible schedules total. Usually, to be a little more concise, we call this eleven factorial or, in symbols, 11! (that is not a grammatical mistake; the symbol is actually an exclamation point).

As I mentioned earlier, that number comes out to just under 40 million. Of course nothing we said was specific to the fact that we were ordering events or really even to the fact that there happened to be 11 of them. If you wanted to arrange 27 different bleaches in a line for the tasting contest, there would be 27! = 27 x 26 x 25 … x 3 x 2 x 1 possible arrangements. If there are 114 snakes to be wrangled, there are 114! possible wrangling-lineups. If there are 15 kids at the party, there are 15! possible rankings for the race. I suppose if you were curious in what order the kids would go to the emergency room, there are also 15! possibilities for that.

cover image: Primary school children, sports day, by Anthea Sieveking, Wellcome Images, via Duncan Hull