Permu-Combi-What-Now? (Or, the Mathematics of My Wedding Playlist)

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:

1. The Impression That I Get – The Mighty Mighty Bosstones
2. Livin’ on a Prayer – Bon Jovi
3. Sweet Caroline – Neil Diamond
4. Hey Ya! – Outkast
5. Little Talks – Of Monsters and Men
6. We Didn’t Start the Fire – Billy Joel
7. Crazy in Love – Beyoncé feat. Jay-Z
8. December, 1963 (Oh What a Night!) – Franki Valli & the Four Seasons
9. Mr. Brightside – The Killers
10. Ciega, Sordomuda – Shakira
11. Sweet Dreams (Are Made of This) – Eurythmics
12. All the Small Things – blink-182
13. To the Dogs or Whoever – Josh Ritter
14. Dancing in the Dark – Bruce Springsteen
15. Tubthumping – Chumbawumba
16. The Way You Look Tonight – Frank Sinatra
17. 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.