I believe no mathematical formula should remain a mysterious black box. So, in this post, I endeavor to explain one of high school math’s most notorious and opaque tools: the formula for the number of combinations of a given collection of objects.

I also believe every human pursuit can be made sweeter and more majestic by the mystic power of dance. So, in this post, I share with you the meticulously cultivated dance playlist from my wedding this June.

The result is a choose-your-own adventure blog post.

- If you’re generally curious about combinatorics (i.e., combinacurious), read 1-4.
- If you’re comfortably counting permutations but stuck on combinations, skip to 4.
- And whenever you’re ready to start dancing, jump straight to 5.

**1. The Challenges of Counting**

Counting is one of the hardest parts of math. I don’t mean 1-2-3-4-can-I-have-a-little-more counting. I mean counting groups. Collections. Possibilities. I mean counting **permutations** and **combinations**.

A **permutation** is an ordered sequence of things. It’s like a playlist you’re making for a dance party, with a specific order, meant to be experienced from first song to last.

A **combination** is an unordered collection of things. It’s like a playlist you’re going to listen to during dinner, on random. You care what’s on it, but the specific sequence doesn’t matter.

Or instead of music, take baseball. Say lots of players are standing in a field, waiting to be chosen for a team. If I pick a group of nine, that’s a combination. Swap any two guys with one another, and it’s still the same team.

But once I assign specific positions (“You pitch; you play third base; and *you* go play right field and try not to mess anything up”), it’s a permutation. Now the order matters. I wouldn’t want to swap my bulky first-baseman (who barely needs to move) with my spry center-fielder (who has acres of outfield to patrol). Changing the order creates a new permutation.

It doesn’t matter what objects we’re combining and permuting. Songs, ballplayers, countries, tree frogs—they all follow the same rules and patterns. Mathematicians hunt deep ideas and laws, not fretting over superficial features. In mathematics, abstraction is beauty, and no abstraction is purer than counting. That’s why we count with the same numbers—1, 2, 3, and the rest of your favorites—no matter what’s being counted.

Few questions strike deeper at the combinatorial heart than this: Given a set of objects, how many permutations and combinations can we form?

**2. Permuting All**

Let’s say that it’s June 2013, and you’re planning the dance playlist for your wedding. “Twist and Shout” has to come last, obviously. Your slower songs—“The Way You Look Tonight” and “Sweet Caroline”—should appear spaced well apart. No consecutive songs by the same artist.

Since order matters, we’re talking about *permutations*. And the more songs you add, the more permutations there are to consider.

Let’s suppose there’s just one song—“Hey Ya!” presumably. There’s only one permutation:

Add a second song, “The Middle.” (No shame; it’s a middle-school throwback.) Now you’ve got two permutations available:

One song, 1 permutation. Two songs, 2 permutations. But at three songs, things start to balloon out of control. Throw in “Livin’ on a Prayer,” and we’re up to 6 permutations. We have two possibilities starting with “Hey Ya!”, two starting with “The Middle,” and two starting with “Livin’ on a Prayer.”

I’m dwelling on the choice of the first song, and not just because it’s crucial to get those feet moving early. Counting is much easier if we think about playlist design as a step-by-step decision process, taken one song at a time.

In the three-song scenario, we’ve got 3 options for the first track.

Then, we’ve got 2 choices for the second track.

And finally, we’re left with just 1 choice for the last track.

In other words, there are 3 * 2 * 1 = 6 options. This elegant formula applies not only for music, but for anything we might sequence.

Bring in a fourth song (“Crazy in Love”—you need some Beyoncé, and “Single Ladies” doesn’t fly at a wedding reception). Now how many permutations (i.e., playlists) are there? Well, we’ve got 4 choices for the first track.

Then 3 choices for the second…

And 2 choices for the third…

And as before, just 1 choice for the final track.

In other words, there are 4 * 3 * 2 * 1 = 24 options. We’ve arrived at a fundamental rule of playlist sequencing (or “combinatorics,” in math-ier terms). If you want to put, say, 18 songs in order, then the number of options is:

We call this number 18!, or “18 factorial.” It’s huge. Even if each song just lasted 1 second, listening through every possible permutation of them would take 3 billion years.

More abstractly, if we want to put *n* songs in order, then the number of options is n!, or

So why did I spend all of June tweaking the wedding playlist? Because there were lots of options to consider! As we’ve seen, a slight increase in the number of objects can lead to a dramatic (and eventually mind-boggling) increase in the number of permutations. (Also, I can’t be trusted to fold a program properly, and my wife and mother-in-law needed something to keep me occupied.)

**3. Permuting Some**

We only had time for 17 songs at the wedding. But that didn’t stop me from crafting a preliminary batch of 50 contenders. And this turns out to be a common issue in combinatorics: sometimes you want a permutation that includes only *some* of the objects, not all of them.

Say that after I picked those 50 songs, we’d only had time for 1. Clearly, we have 50 possibilities (and a bummer of a reception) on our hands.

What if we’d had time for 2? Well, there are 50 choices for the first song. And, with one song used up, there are 49 options for the second.

That’s a pretty intimidating number of permutations already. And we’re just getting started.

And what if we wanted to cull a 10-song playlist from the 50 contenders?

50 choices for first song… 49 for the second… 48 for the third… and so on, until the tenth song, for which we have 41 choices.

Here’s a faster way to write it, using factorial notation:

Replacing our numbers with variables, we’ll get a general formula that works for all situations involving permutations. So let’s say we have *n* total songs, and we want a playlist featuring *k* of them. The number of permutations is

Was it worth my whole June to find the perfect permutation? If you’d seen my Uncle Paul’s dance moves, you’d know the answer is yes.

**4. Combining**

For last, I’ve saved the question which seems easiest and turns out to be hardest. What if we don’t care about the order? What if it only matters *which* songs we pick, not the sequence we play them in? What if we’re counting not permutations, but *combinations*?

Let’s start simple. We’ve got 5 songs, and we want to pick 2. That’s 5 choices for the first song, and 4 for the second. Sounds like 20 combinations, right?

Wrong! We’re double-counting every combination. Here, “Hey Ya!” + “The Middle” is no different than “The Middle” + “Hey Ya!” and yet we’re listing them separately.

So what do we do? Well, each combination is being counted exactly twice. So we divide by 2, meaning that we’ve really got 10 combinations.

What if there are 7 songs, and we want 3? A similar process applies: 7 choices for the first, 6 for the second, and 5 for the third. So 7 * 6 * 5 = 210 combinations.

But how many times are we counting each combination? Are we double-counting? Triple-counting? Actually, we’re sextuple-counting. Once we pick our 3 songs, we don’t care how they’re sequenced. But our method lists each three-song combo as 6 separate sequences. (That’s because there are 6 ways to permute any three-song group.)

So we divide 210 by 6, yielding 35 combinations.

Keep going. Say we’ve got 11 possible songs, and we’re picking 4. How many combinations?

Well, if we cared about order, there’d be 11 * 10 * 9 * 8 possible playlists.

But we don’t care about order. Each 4-song combination appears many times on our list. So we’ve got to divide by 4! (because that’s the number of ways to permute any 4-song group).

This gives a final answer of 330 combinations.

Finally, we can give a general formula. Suppose that there are *n* songs, and we want to combine *k* of them. How many possible combinations are there?

First, we count the number of *permutations *of length k. Then we divide by k!, because each k-item combination yields k! permutations on our list.

And we’ve solved it! If you want to combine *k* out of *n* objects, then there are n!/k!(n-k)! possible ways to do it.

By now, maybe you see what I mean: counting is hard. We tend to picture counting as an additive process. But here, counting is multiplicative. Throwing one more song into contention can drastically increase the number of possible playlists.

Combinations seem simpler than permutations, because their order doesn’t matter. But that lack of structure actually makes them *harder* to count. In fact, it’s easier to pretend that order matters, and adjust later for the fact that you’ve over-counted.

**5. Finally, the Dance Playlist**

The wedding playlist, by the way, wound up too long. I made adjustments on the fly, so the exact order is now lost to the sands of time, but here’s a rough reconstruction:

- The Impression That I Get – The Mighty Mighty Bosstones
- Livin’ on a Prayer – Bon Jovi
- Sweet Caroline – Neil Diamond
- Hey Ya! – Outkast
- Little Talks – Of Monsters and Men
- We Didn’t Start the Fire – Billy Joel
- Crazy in Love – Beyoncé feat. Jay-Z
- December, 1963 (Oh What a Night!) – Franki Valli & the Four Seasons
- Mr. Brightside – The Killers
- Ciega, Sordomuda – Shakira
- Sweet Dreams (Are Made of This) – Eurythmics
- All the Small Things – blink-182
- To the Dogs or Whoever – Josh Ritter
- Dancing in the Dark – Bruce Springsteen
- Tubthumping – Chumbawumba
- The Way You Look Tonight – Frank Sinatra
- Twist and Shout – The Beatles

If I could do it all again, I’d probably cut “Sweet Dreams” in favor of Cascada’s Everytime We Touch. That said, the dancing hit dangerous levels of vigor as is. We were lucky to escape with no serious injuries. The addition of Cascada’s energy might’ve sent a few dancers to the ER.

I think the pictures help mitigate your clash with the “can’t teach a math lesson in writing” rule.

And I think the Bosstones help mitigate, I don’t know, everything ever because the Bosstones are mighty. Great post!

Great call starting with the Bosstones. Also, great post. Thanks for your work on this blog – learning a lot to apply to my students, too.

I need to read and reread this excellent post to make sure I completely understand, but thanks to you I’m looking forward to impressing my math grad. student son with my understanding of combinatorics! Thanks for working so hard on the only site I know to provide coherent, humorous, and interesting math info. plus some great new-to-me music recommendations!

Have you seen what James Tanton has to say on this issue? If not, do check it out. I think you’ll find his take helps eliminate much of the confusion via what he calls the labeling principle.

http://www.jamestanton.com/wp-content/uploads/2010/05/Pamphlet-on-Counting.pdf

http://www.jamestanton.com/wp-content/uploads/2010/05/combinations-and-permuations.pdf

http://www.jamestanton.com/wp-content/uploads/2012/03/Curriculum-Newsletter_June-2012.pdf

Mr. Saturn – thanks. It’d be a completely impossible task without pictures! Glad both you and Jason endorse the Bosstones in the leadoff position. And Jason, I’m glad to hear posts like these are helpful.

Thanks for reading, Bonny! I’ve got a post coming up about our email conversation regarding how to talk with a mathematician.

And Michael, I like Tanton’s take, which doesn’t rely on the combination/permutation distinction at all. I also like that he accounts for both terms in the denominator of the combinations “formula” by the same logic – k! to adjust for overcounting in the “on” group, and (n-k)! to adjust for overcounting in the “off” group. (My presentation, somewhat less elegantly, gives a different explanation for each term in the denominator.)

Ben, glad you found Tanton useful. I think he’s a true gem when it comes to streamlining unnecessarily recondite mathematics. Sometimes, I see what he does with a topic and wonder why so many teachers for so long have insisted on any other way. ;^)

Must have been one hell of a party. But don’t listen to a word that I say (hey!), the screams all sound the same.

Also, nice read, although I knew this. I love your black boxes although I think I have none.

And though the truth may vary, this math will carry our bodies safe to shore.

This is one of my favorite blog posts, ever. Maybe I’m a sucker for wonderful bad drawings, or maybe I just I like the idea of shuffling songs on a dance playlist more than rearranging children’s alphabet blocks… Either way, this is fantastic. Thanks for sharing!

Thanks for reading – I’m glad you enjoyed it!

I love these. I reposted your probability stories on my AP Stats class blog, and got some great feedback from my students. We even had a running joke about curling up with a cup of hot chocolate and your baby calculator (non graphing) to read. Mind if I share this with them as well?

Go right ahead! I’m glad the probability stories went over well – I hope this gives another excuse for hot chocolate (in a season when most of the US could use some).

We’re in Chicago, so we for sure can here! Maybe they’ll spill it on those darn baby calculators 🙂

Pingback: Math Instruction Philosophies: Instructivist and Constructivist | educationrealist

Pingback: Permu-Combi-Whatsits | Solorio AP Statistics 2013-14

Is there an error in Step 4?

You wrote that:

For a 2-song comination you divide by 2.

For a 3-song combintation you divide by 6.

For a 4-song combination you divide by 4?

Wouldn’t there be 16 possible duplicate combinations for a 4-song selection?

(I’m using logic, not maths, to make that suggestion. So I could be wrong here.)

Ah – I realize now the notation was confusing. I meant to say “divide by 4!” as in “divide by 4 factorial,” meaning “divide by 24,” since that’s the number of ways to permute 4 songs.

Ben, check out James Tanton’s approach here:

http://gdaymath.com/courses/permutations-and-combinations/

He treats all of these problems as exercises in labeling! The neat thing is that he argues we need not make a distinction between “combinations” and “permutations.” Just get the labelling part right, and that’s it!

Ever read other comments before adding yours? I already pointed out Tanton’s ideas here and Ben responded to that suggestion.

Oops! You did indeed beat me to the punch there. Sorry!

Well, thanks to both of you once again for the suggestion!

The more I think about it, the more I prefer Tanton’s approach. I may give it a test drive the next time I teach this.

Tanton has lovely videos up on YouTube via a couple of his web pages. I think he’s got a mini-course up on his gdaymath.com site.

Pingback: Permutations and Combinations | Mean Green Math