Permutations and Combinations

In the last couple years I’ve regained interest in solidifying my math chops. One mathematical concept that I see popping up again and again is that of permutations and combinations. I tried searching around for quick explanations, but I wasn’t really pleased with what I found. I thought I would share an approach that really helped me get it.

Permutations

Finding the number of permutations of a unique set is simple, but tricky to understand. Once it “clicks,” you’ll think to yourself, “why did I think that was so hard?” (if you’re like me anyways).

Given a set with unique elements, you can permute it by mixing up the elements. Finding the permutations of a set involves figuring out all the unique ways you can mix those elements. The key concept in a permutation is ordering: it matters how the elements are ordered. Thus, the permutation \left \{ab \right \} is distinct from \left \{ba \right \}. The question, “how many permutations are there of a set?”, is asking for all possible orderings of the elements in that set. Consider the set:

S = \left \{abc \right \}

What are all the permutations of S? One way to do this by hand is by picking an element to go first and enumerating the permutations of the remaining elements:

(a goes first)

\left \{abc \right \} \left \{acb \right \}

(b goes first)

\left \{bac \right \} \left \{bca \right \}

(c goes first)

\left \{cab \right \} \left \{cba \right \}

As you can see, there are 6 permutations of this set. One thing to notice is that there are 3 members in the set, and we could pick any of those to be the first element. More generally, given N elements in a set, there are N ways to pick the first element.

But what about the second element? Assuming all members are unique, we can take the subset of N-1 elements and pick any of those to be the second. For example, let’s assume we’ve picked a already, we’re left with a subset of S without a:

\left \{bc \right \}

This particular set is trivial, but let’s stick with our plan:

(b goes first)

\left \{bc\right \}

(c goes first)

\left \{cb \right \}

We end up with only two permutations of this subset. More generally, we’ve got N-1 elements, and we can pick any of those to go first in our subset.

You may be spotting a pattern here, and that’s the key insight. We started with N elements, and we’re free to pick any one of those to go first. Then, for every one of those N choices, we have a subset of N-1 elements. Following our pattern, we can pick any N-1 of those elements to go first in that subset. If we keep going, we end up with N-2, N-3, etc–all the way down to 1. When we reach a set of 1 element, we’re done. This is our base case.

The trickiest part is knowing how to combine these results.

Starting with N elements, we have N choices for the first one. For each of those N choices, we have N-1 sub-choices. These are multiplied together to give us the total number of choices, N * (N-1). But we aren’t done, because have to consider the N-2 choices for each of the N-1 sub-choices, for each of the N original choices, which is N * (N-1) * (N-2). If you continue this pattern all the way down to 1, you get the familiar factorial function, N! Going back to our example, we had 3 choices for our first element, which gave us the three lines above. For each of those 3 lines, we had a 2 element subset, of which the permutations are merely the 2 possible “flippings” of those elements. We ended up with 3*2*1 = 6 permutations, just as we expected.

Thus, the answer to our question, “how many permutations are there of a set?” is N!, where N is the number of elements in our set.

Combinations

You may be familiar with the “n choose r” notation, which is denoted mathematically by the following equation:

\binom{n}{r} = \frac{n!}{r!(n-r)!}

This is a pretty scary looking equation, and it’s not easy to “reverse engineer.” the meaning by just looking at it. Fortunately, there’s an easy way to understand it that builds on the idea of permutations presented in the previous section, so bear with me.

First of all, what is a combination? Remember how permutations were ordered sets? The key behind a combination is that it is unordered. How many ways can you divide a group of 4 students into 2 person teams? That’s a combination problem. We don’t care who’s first or second on each team–only who is on each team. Thinking about it, combinations must somehow relate to permutations. More precisely, the combinations must be a subset of the permutations. Why? Well, if you have any combination of students on a team, you could generate permutations from that–by picking someone to go first, etc., like we learned above. It “feels” like there are duplicate sets being counted that we don’t care about–which is exactly the case. The equation above is basically computing all possible permutations and then “trimming” the duplicate results to give us the combinations.

With that insight, let’s examine that scary equation once again, just for a bit.

\binom{n}{r} = \frac{n!}{r!(n-r)!}

This equation is saying, “how many ways can we choose r elements from n elements?” Using our team example above, we’d be choosing 2 person teams from 4 total people. Let’s plug it in and see what we get:

\binom{4}{2} = \frac{4!}{2!(4-2)!} = \frac{24}{2*2} = 6

Given a set, \left \{abcd \right \}, it’s not too hard to pick out those 6 combinations:

\left \{ab\right \} \left \{ac \right \} \left \{ad \right \} \left \{bc \right \} \left \{bd \right \} \left \{cd \right \}

As you can see, each combination includes a unique group of people, in no particular order. We could visit each of these groups, permute them by picking all possible orderings, and combine the results to get 24 total permutations. I’ll leave that as an exercise for you. The key insight is that we can compute permutations from combinations. Each permutation is the same combination, just mixed up differently. Let’s just examine one of these combinations: \left \{ab\right \}.

Finding the permutations in this set is trivial. Here they are:

\left \{ab \right \} \left \{ba \right \}

There are 2! = 2 permutations here. These are the permutations of the combination, \left \{ab\right \}. Hmmm, it seems like we’re ending up with twice as many results as we want. For each combination, we have a duplicate. We need to take our original n! permutation estimate and somehow remove these duplicates. We do this by dividing by r!. Think about it, if we have a 2 element set, we end up double counting everything. We need to divide by 2. If we had a 3 element set, we could have even more duplicates. We would need to divide by 3! = 6.

Using our previous example, dividing 24 (the number of permutations of n elements) by 2 (the number of permutations of r elements) gives us 12–not 6. What gives?

We’ve still got the (n – r)! term in there. If you think about it, n-r counts the remaining elements not chosen in our combination. Let’s take a look at our team example once more to see why we need this.

Let’s say we’ve chosen the combination, \left \{ab \right \}. We know that this expands into 2 permutations, so we divide our total number of permutations (24 in this example) by 2, but we still have duplicates. The issue is that our n! permutations still include permutations of the remaining elements, which are incorrectly included in our count. Let’s examine our first combination once again:

\left \{ab \right \}

We know we can permute this, but we still have to combine it with the remaining unused elements, which combined form a permutation of the original set. Thus, even if we purge duplicates from our subset, we still end up with more duplicates. Assuming we’ve purged duplicates from our example subset, our combined set still includes the permuted unused elements:

\left \{abcd \right \} \left \{abdc \right \}

To correct this, we need to divide by the (n-r) element permutations, which gives us the missing (n-r)! term. If we divide our original n! permutations by these two terms, we finally get the correct result:

\binom{n}{r} = \frac{n!}{r!(n-r)!}