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.

Jordy Greenblatt is a PhD student in pure math at UCLA doing research in harmonic analysis. His other intellectual interests include physics and history but he likes to spend his free time juggling and playing harmonica. He co-writes the humor blog Put It All on Red and contributes to Trop and McSweeney's Internet Tendency.

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

Categories

Get monthly email updates with the best from The Concepts Project. No spam, ever.

Get in touch, we'd love to hear from you: theconceptsproject@gmail.com

Greatest Hits

Thinking At The Margin: what to do when you drop your piggy bank in the middle of the forest.

Strategy and Backward Induction: how to win a week of lunches from your unsuspecting colleagues.

What is Multiple Imputation?: when statisticians turn into detectives.

On Shuttle Drivers, Chocolate and NP Completeness: a deliciously difficult problem in computer science.

Rest and Digest vs Fight or Flight: how your body (and medications) help with fighting tigers.

Sites we like

William Shaw, writing about Politics, Theatre, Sci-fi… Mainly Sci-fi.

Better Explained, for maths explanations that click.

Science Non Fiction, a graduate student perspective on science in the news and in our lives.

Clearer Thinking, learn to think more clearly and make better decisions.

EconScribe.org, working to improve the quality of research communications.

Jess Whittlestone, a blog about decision making and behavioural science.