6.2: Permutations

When we’re counting things, we often run into permutations. A permutation of \(n\) distinct objects is an arrangement of them in a sequence. For instance, suppose all three Davies kids need to brush their teeth, but only one of them can use the sink at a time. What order will they brush in? One possibility is Lizzy, then T.J., then Johnny. Another possibility is T.J., then Lizzy, then Johnny. Another is Johnny, then Lizzy, then T.J. These are all different permutations of the Davies kids. Turns out there are six of them (find all 6 for yourself!)

Counting the number of permutations is just a special application of the Fundamental Theorem of Counting. For the teeth brushing example, we have \(n=3\) different “parts" to the problem, each of which has \(n_i\) choices to allocate to it. There are three different Davies kids who could brush their teeth first, so \(n_1=3\). Once that child is chosen, there are then two remaining children who could brush second, so \(n_2=2\). Then, once we’ve selected a first-brusher and a second-brusher, there’s only one remaining choice for the third-brusher, so \(n_3=1\). This means the total number of possible brushing orders is: \[3 \times 2 \times 1 = 6.\]

This pattern comes up so much that mathematicians have established a special notation for it: \[n \times (n-1) \times (n-2) \times \cdots \times 1 = n!\ \text{(``$n$-factorial")}\]

We say there are “3-factorial" different brushing orders for the Davies kids. For our purposes the notion of factorial will only apply for integers, so there’s no such thing as 23.46! or \(\pi\)!. (In advanced computer science applications, however, mathematicians sometimes do define factorial for non-integers.) We also define 0! to be 1, which might surprise you.

This comes up a heck of a lot. If I give you a jumbled set of letters to unscramble, like “KRIBS" (think of the Jumble word game in the newspaper), how many different unscramblings are there? The answer is 5!, or 120, one of which is BRISK. Let’s say I shuffle a deck of cards before playing War.¹ How many different games of War are there? The answer is 52!, since any of the cards in the deck might be shuffled on top, then any but that top card could be second, then any but those two could be third, etc. Ten packets arrive near-simultaneously at a network router. How many ways can they be queued up for transmission? 10! ways, just like a larger Davies family.

The factorial function grows really, really fast, by the way, even faster than exponential functions. A five letter word like “BRISK" has 120 permutations, but “AMBIDEXTROUSLY" has 87,178,291,200, ten times the population of the earth. The number of ways to shuffle a deck is

80,658,175,170,944,942,408,940,349,866,698,506,766,127,860,028,660,283,290,685,487,972,352

so I don’t think my boys will end up playing the same War game twice any time soon, nor my wife and I the same bridge hand.

Enumerating permutations

We’ve discovered that there are 120 permutations of BRISK, but how would we go about listing them all? You can play around with the Davies kids and stumble upon all 6 permutations, but for larger numbers it’s harder. We need a systematic way.

Two of the easiest ways to enumerate permutations involve recursion. Here’s one:

Algorithm #1 for enumerating permutations

1. Begin with a set of \(n\) objects.

   1. If \(n=1\), there is only one permutation; namely, the object itself.

   2. Otherwise, remove one of the objects, and find the permutations of the remaining \(n-1\) objects. Then, insert the removed object at every possible position, creating another permutation each time.

As always with recursion, solving a bigger problem depends on solving smaller problems. Let’s start with RISK. We’ve already discovered from the toothbrushing example that the permutations of ISK are ISK, IKS, SIK, SKI, KIS, and KSI. So to find the permutations of RISK, we insert an R into each possible location for each of these ISK-permutations. This gives us:

RISK
IRSK
ISRK
ISKR
RIKS
IRKS
IKRS
IKSR
RSIK
\(\cdots\)

and so on. Once we have the RISK permutations, we can generate the BRISK permutations in the same way:

BRISK
RBISK
RIBSK
RISBK
RISKB
BIRSK
IBRSK
IRBSK
IRSBK
IRSKB
BRSIK
\(\cdots\)

Another algorithm to achieve the same goal (though in a different order) is as follows:

Algorithm #2 for enumerating permutations

1. Begin with a set of \(n\) objects.

   1. If \(n=1\), there is only one permutation; namely, the object itself.

   2. Otherwise, remove each of the objects in turn, and prepend that object to the permutations of all the others, creating another permutation each time.

I find this one a little easier to get my head around, but in the end it’s personal preference. The permutations of BRISK are: “B followed by all the permutations of RISK, plus R followed by all the permutations of BISK, plus I followed by all the permutations of BRSK, etc." So the first few permutations of a 4-letter word are:

  RISK
R IKS
R SIK
R SKI
R KIS
R KSI
I RSK
I RKS
I SRK
I SKR
I KRS
I KSR
S RIK
\(\cdots\)

Then, for the 5-letter word:

B RISK
B RIKS
B RSIK
B RSKI
B RKIS
B RKSI
B IRSK
  B IRKS
\(\cdots\)

Partial permutations

Sometimes we want to count the permutations of a set, but only want to choose some of the items each time, not all of them. For example, consider a golf tournament in which the top ten finishers (out of 45) all receive prize money, with the first place winner receiving the most, the second place finisher a lesser amount, and so on down to tenth place, who receives a nominal prize. How many different finishes are possible to the tournament?

In this case, we want to know how many different orderings of golfers there are, but it turns out that past tenth place, we don’t care what order they finished in. All that matters is the first ten places. If the top ten are 1.Tiger, 2.Phil, 3.Lee, 4.Rory, \(\dots\), and 10.Bubba, then it doesn’t matter whether Jason finished \(11^{\text{th}}\) or \(45^{\text{th}}\).

It’s easy to see that there are 45 possible winners, then for each winner there are 44 possible second-placers, etc., so that this total turns out to be: \[45 \times 44 \times 43 \times 42 \times 41 \times 40 \times 39 \times 38 \times 37 \times 36 = \text{11,576,551,623,436,800 finishes}.\] Each of the finishes is called a partial permutation. It’s a permutation of \(k\) items chosen from \(n\) total, and is denoted \(p_{n,k}\). The number of such permutations works out to \[n \times (n-1) \times (n-2) \times \cdots \times (n-k+1).\] The “\(n-k+1\)" bit can be confusing, so take your time and think it through. For the golf tournament case, our highest term was 45 and our lowest term was 36. This is because \(n\) was 45 and \(k\) was 10, and so we only wanted to carry out the multiplication to 36 (not 35), and 36 is 45-10+1.

This can be expressed more compactly in a few different ways. First, we can use factorials to represent it: \[\begin{aligned} n \times (n-1) \times (n-2) \times \cdots \times (n-k+1) &= \\ \dfrac{n \times (n-1) \times (n-2) \times \cdots \times 1}{(n-k) \times (n-k-1) \times (n-k-2) \times \cdots \times 1} &= \dfrac{n!}{(n-k)!}.\end{aligned}\] Too, we could use our compact product notation: \[\begin{aligned} n \times (n-1) \times (n-2) \times \cdots \times (n-k+1) &= \prod_{i=0}^{k-1}{(n-i)}.\end{aligned}\] Finally, as with (non-partial) permutations, this comes up so much that the professionals have invented a special notation for it. It looks like a power, but has an underline under the exponent: \[\begin{aligned} n \times (n-1) \times (n-2) \times \cdots \times (n-k+1) &= n^{\underline{k}}.\end{aligned}\] This is pronounced “\(n\)-to-the-\(k\)-falling," and was invented by one of the most brilliant computer scientists in history, Donald Knuth.

To keep straight what \(n^{\underline{k}}\) means, think of it as the same as plain exponentiation, except that the product diminishes instead of staying the same. For example, “17-to-the-\(6^{\text{th}}\)" is \[17^6 = 17 \cdot 17 \cdot 17 \cdot 17 \cdot 17 \cdot 17\] but “17-to-the-\(6^{\text{th}}\)-falling" is \[17^{\underline{6}} = 17 \cdot 16 \cdot 15 \cdot 14 \cdot 13 \cdot 12.\] In both cases, you’re multiplying the same number of terms, it’s just that in the second case, these terms are “falling."

Anyway, notation aside, partial permutations abound in practice. A late night movie channel might show four classic films back to back every evening. If there are 500 films in the studio’s library, how many nightly TV schedules are possible? Answer: \(500^{\underline{4}}\), since there are 500 choices of what to show at 7pm, then 499 choices for 9pm, 498 for 11pm, and 497 for the 1am late show.

The fastest 41 auto racers will qualify for Sunday’s race, and will be placed from Pole Position on down depending on their qualifying time. If 60 cars participate in the qualifying heat, then there are \(60^{\underline{41}}\) different possible starting configurations for Sunday.

Middle schoolers entering sixth grade will be assigned a semester schedule that consists of five “blocks" (periods), each of which will have one of thirteen classes (science, math, orchestra, study hall, etc.) How many schedules are possible? You guessed it, \(13^{\underline{5}}\). Notice that this is the correct answer only because no repeats are allowed: we don’t want to schedule any student for American History more than once. If a student could take the same class more than once in a day, then there would be \(13^5\) (not “falling") different possible schedules.

---

1. “War” is a mindless card game which involves no strategy or decisionmaking on the part of the players. Once you shuffle the initial deck, the entire outcome of the game is fixed.