Permutations

We have opportunities to count everyday. Some of the counting is done for us, such as the number of likes on your favorite social media post. We even celebrate victories when the count, the score, is a desired result. Too often though, numerics bring a gravity—an unfortunate heaviness—to life, especially when we are asked to do the (ac)counting. What if, instead of straining, we let our minds wander and play? What if we could sustain playfulness even when facing a challenging question?

---

In reading about Pascal’s Triangle, you may have discovered the number of combinations of 3 people you can make when choosing from a gathering of 5 people. Order does not matter in those combinations. A set with {a,b,c} is the same as {c,a,b}. But, what if order does matter? What if those 3 folks will hold distinct positions, such as president, vice president, and secretary? We would no longer be talking combinations. We would be asking about permutations instead.

How many permutations are there of three objects when picking from a set of five?

In the last post, we saw there are 5! = 120 permutations of 5 people (or any 5 objects). It seems reasonable to suspect the number of permutations of 3 when picking from 5 is less than 120. How much less?

To shine a little more light on this, I might gather my four friends again: Abel, Boris, Charles, and Dylan. The game is to see how many distinctly ordered trios the five of us can form. If we start with Abel, Boris, and Charles and rearrange them, we will see there are 6 rearrangements.

a b c       b a c
a c b       b c a
c a b       c b a

If each position in the list corresponds to a distinct executive position, then you might imagine the different social dynamics of each rearrangement. These 6 are distinct executive committees.

Those 6 are not the only possible permutations. We could pick three more folks, maybe Abel, Boris, and Dylan. Rearrange them to get 6 more permutations, and we are up to 12. We could continue this way, but there is serious potential for losing track—missing rearrangements, double-counting, and the like—especially if the numbers were larger.

If you have some math savvy, you might suggest we use Pascal’s Triangle to find out how many distinct combinations of 3 we could form. That is a good idea, except my somewhat hidden agenda is to uncover why those numbers are in Pascal’s Triangle in the first place. It would be circular to use a value from Pascal’s Triangle in explaining Pascal’s Triangle. “There is a 10 there, because there is a 10 there.” may be a true statement, but it does not deepen my understanding of Pascal’s reasoning. Also, I want a general formula for counting combinations and an easier way to answer the 1000 goat question.

So then, back to the question at hand: how many distinctly ordered trios are possible if you are picking from Abel, Boris, Charles, Dylan, and Eric? Rather than listing and counting, we can use a similar line of reasoning from when we were rearranging all five of us.

How many choices do you have for the first spot?

Five

With that spot taken (and one of you now in a position of power),
how many choices are left for the next spot?

Four

The spot after that?

Three

This time, we stop there. We only wanted to fill three spots.

What to do with the 5, 4, 3? Multiply. There are 5 ⋅ 4 ⋅ 3 = 60 distinctly-ordered groups (permutations) of 3 when picking from 5. That is, there are 60 possible executive committees of president, vice-president, and secretary for our group of 5 people.

What if there had been 7 of us, how many executive committees of 3 are possible?

---

You may have noticed the language describing permutations can be a little clunky. Instead of asking the number of permutations of 3 objects picked from a set of 5 objects, we can simply ask the number of 3-permutations of 5. That phrase “3-permutations of 5” can be expressed even more compactly with common notation, P(5,3). You may have also seen this as 5P3. Jargon and notation can streamline communication with people familiar with a bit of mathematics. The challenge is to make sure the jargon or symbols don’t shut out folk not familiar with math. Still, rather than write out sentences to describe the pattern at play, I am going to wrap things up with formulae.

When we calculated P(5,3) above, we did not include the 2 ⋅ 1 that is present in 5!.

versus

We left out the 2 ⋅ 1 = 2 ways the other two people could be rearranged. Since we are only rearranging 3 of the 5, these 2 did not get included as factors: “factors” as in multiplication. “Leaving them out” can be construed as dividing in this case. For P(5,3), the number of 3-permutations of 5, we can perform the following computation.

This division is the key step in writing a general formula for k-permutations of n. Before generalizing, let’s consider another example and look for pattern. (If you already know the formula, see if you are willing to re-discover it. Be on the lookout for what you don’t already know or understand.)

To calculate P(7,3), we want to multiply 7 ⋅ 6 ⋅ 5. That is 7! without 4 ⋅ 3 ⋅ 2 ⋅ 1 = 4!. Again, “without” tells me to undo the multiplication. What operation undoes multiplication?

If you are comfortable with the facts 4/4 = 1, 3/3 = 1, and so on, then you might accept the following cancelations.

The formulation 7!/4! seems to work, and the cancelation eases computation. If you take a moment, you can compute 7 ⋅ 6 ⋅ 5 without the aide of a handheld device. Then, you will know the number of permutations of 3 objects when picking from a set of 7, i.e. the number of 3-permutations of 7.

There might be enough pattern to speculate a general formula for P(n,k), the number of k-permutations of n. If not, think through more examples. How would you calculate the number of distinctly ordered pairs possible when picking from 10? That is how many 2-permutations of 10 are there? How can you express P(10,2) with factorials?

Now, how about P(n,k)?