Permutations

In this section, we'll learn about permutations and k-permutations. We'll also learn how to use the rule of product to count them.

What is a permutation?

A permutation is just an ordering of the members of a set. If the set is already ordered, then permutations are just the different reorderings we can do.

Here's a simple example.

Example: Permutations of a set of numbers

Consider the set {0, 1, 2, 3}. Here are some permutations of this set:

• (0, 1, 2, 3)
• (1, 0, 2, 3)
• (1, 2, 3, 0)
• (3, 2, 1, 0)

That's obviously just a partial list. You can easily come up with several more.

Counting permutations

Permutations come up a lot in math and computer science. In probability they come up because sometimes we need to count them to figure out how likely or unlikely some event is. To count permutations, we simply apply the rule of product: if a set has $$n$$ elements, then there are $$n!$$ (or n factorial) permutations of the set. This is because there are $$n$$ ways to choose the first element, but then only $$n - 1$$ ways to choose the second element since we've already used one of the elements up, and then $$n - 2$$ ways to choose the third element, all the way down the line. Applying the rule of product gives us

$${n \cdot (n - 1) \cdot (n - 2) \cdots 3 \cdot 2 \cdot 1 = n!}$$

possible permutations of the $$n$$ elements.

Let's do a couple of concrete examples.

Example: Counting the permutations of a set of numbers

Let's go back to our set {0, 1, 2, 3}. Here, we have $$n = 4$$, so the number of permutations is $$4! = 24$$.

To convince ourselves that this is actually true, let's enumerate them:

 (0, 1, 2, 3) (1, 0, 2, 3) (2, 0, 1, 3) (3, 0, 1, 2) (0, 1, 3, 2) (1, 0, 3, 2) (2, 0, 3, 1) (3, 0, 2, 1) (0, 2, 1, 3) (1, 2, 0, 3) (2, 1, 0, 3) (3, 1, 0, 2) (0, 2, 3, 1) (1, 2, 3, 0) (2, 1, 3, 0) (3, 1, 2, 0) (0, 3, 1, 2) (1, 3, 0, 2) (2, 3, 0, 1) (3, 2, 0, 1) (0, 3, 2, 1) (1, 3, 2, 0) (2, 3, 1, 0) (3, 2, 1, 0)

These are indeed 24 permutations of the original set.

Here's another example of counting permutations.

Example: Shuffling a standard deck of 52 cards

Say that we wanted to figure out how many different ways there are to shuffle a deck of 52 cards. Another way to ask the same thing is to ask how many permutations of the deck there are.

The answer is $$52!$$. This is quite a large number. You can read all about just how large 52! actually is.

For further high-quality amusement, see bogosort.

That does it for standard permutations. But there's another kind of permutation that comes up a lot, which is called a k-permutation. Let's look at those and also how to count them.

What is a k-permutation?

A k-permutation, also known as a partial permutation, is a not strictly a permutation. Instead, it involves weakening the permutation concept by requiring only that the orderings of the size n set have k elements, where kn.

It follows from the above that permutations in the strict sense are special cases of k-permutations, where the orderings involve every member of the set.

Example: Office raffle

Six employees Darci, Erica, Francis, Geoffrey, Hannah, and Isadore, are participating in the office raffle. The raffle has two prizes: a new iPad and dinner for two at the local Olive Garden.

We can think of the raffle as randomly selecting a 2-permutation of six employees. Here are some of the possible 2-permutations:

• Hannah wins the iPad, Erica wins the dinner
• Darci wins the iPad, Francis wins the dinner

Counting k-permutations

Counting k-permutations is similar to counting ordinary permutations, but we need to "stop multiplying" once we've accounted for all k elements. Using the special notation $$P(n, k)$$ to represent the number of permutations of k items taken from n items, we have:

$${P(n, k) = {\frac {n \cdot (n-1) \cdot (n-2) \cdots (n-k+1)}{k \text{ factors}}}}$$

which simplifies to

$${P(n, k) = {\frac {n!}{(n-k)!}}}$$

Example: Office raffle, continued

In the previous office raffle example, $$P(6, 2)$$ represents the number of permutations of two items taken from six items. How many are there?

The calculation is

{\begin{align} P(6, 2) & = {\frac {6!}{(6-2)!}} \\[10pt] & = {\frac {6!}{4!}} \\[10pt] & = {\frac {720}{24}} \\[10pt] & = 30 \end{align}}

Therefore there are 30 2-permutations in the office raffle.

The preceding example suggests a calculation shortcut that can be helpful, especially when dealing with factorials, which can become cumbersome to compute as they get larger. We can expand the factorials and then cancel common factors. See the following example.

Example: A simplified way to count the office raffle 2-permutations

The following is an alternative to computing the full factorials:

{\begin{align} P(6, 2) & = {\frac {6!}{4!}} \\[10pt] & = {\frac {6 \cdot 5 \cdot \cancel{4} \cdot \cancel{3} \cdot \cancel{2} \cdot \cancel{1}}{\cancel{4} \cdot \cancel{3} \cdot \cancel{2} \cdot \cancel{1}}} \\[10pt] & = 6 \cdot 5 \\[10pt] & = 30 \end{align}}

This is very helpful especially as n gets larger.

Try some exercises before moving on to the next section.

Exercises

Exercise 1. How many permutations are there for the set {A, B, C}? Solve this using the formula, and then enumerate the permutations explicitly.

Exercise 2. There are eight competitors competing in an Olympic event. How many different ways are there for the competitors to win the gold, silver and bronze medals?

Exercise 3. In the 2019 Boston Marathon, there were 27,360 competitors who started the race. How many ways were there for competitors to take first, second and third place?

Exercise 4. Evaluate $$P(17, 2)$$. Hint: Don't calculate 17! directly.