Contemporary Mathematics

# 7.2Permutations

Contemporary Mathematics7.2 Permutations

Figure 7.7 We can use permutations to calculate the number of different orders of finish in an Olympic swimming heat. (credit: “London 2012 Olympics Park Stratford London” by Gary Bembridge/Flickr, CC BY 2.0)

### Learning Objectives

After completing this section, you should be able to:

1. Use the Multiplication Rule for Counting to determine the number of permutations.
2. Compute expressions containing factorials.
3. Compute permutations.
4. Apply permutations to solve problems.

Swimming events are some of the most popular events at the summer Olympic Games. In the finals of each event, 8 swimmers compete at the same time, making for some exciting finishes. How many different orders of finish are possible in these events? In this section, we’ll extend the Multiplication Rule for Counting to help answer questions like this one, which relate to permutations. A permutation is an ordered list of objects taken from a given population. The length of the list is given, and the list cannot contain any repeated items.

### Applying the Multiplication Rule for Counting to Permutations

In the case of the swimming finals, one possible permutation of length 3 would be the list of medal winners (first, second, and third place finishers). A permutation of length 8 would be the full order of finish (first place through eighth place). Let’s use the Multiplication Rule for Counting to figure out how many of each of these permutations there are.

### Example 7.4

#### Using the Multiplication Rule for Counting to Find the Number of Permutations

The final heat of Olympic swimming events features 8 swimmers (or teams of swimmers).

1. How many different podium placements (first place, second place, and third place) are possible?
2. How many different complete orders of finish (first place through eighth place) are possible?

1.
You have a hand of 5 cards (that happen to create what’s called a royal flush in the game of poker): 10\spadesuit, J\spadesuit, Q\spadesuit, K\spadesuit, and A\spadesuit. Into how many different orders can you put those cards?

### Factorials

The pattern we see in Example 7.4 occurs commonly enough that we have a name for it: factorial.
For any positive whole number $nn$, we define the factorial of $nn$ (denoted $n!n!$ and read "$nn$ factorial") to be the product of every whole number less than or equal to $nn$. We also define 0! to be equal to one. We will use factorials in a couple of different contexts, so let's get some practice doing computations with them.

### Example 7.5

#### Computing Factorials

Compute the following:

1. $4!4!$
2. $8!6!8!6!$
3. $9!3!4!9!3!4!$

Compute the following:
1.
6!
2.
\frac{{12!}}{{10!}}
3.
\frac{{8!}}{{4!4!}}

### Permutations

As we’ve seen, factorials can pop up when we’re computing permutations. In fact, there is a formula that we can use to make that connection explicit. Let’s define some notation first. If we have a collection of $nn$ objects and we wish to create an ordered list of $rr$ of the objects (where $1≤r≤n1≤r≤n$), we’ll call the number of those permutations $nPrnPr$ (read “the number of permutations of $nn$ objects taken $rr$ at a time”). We formalize the formula we'll use to compute permutations below.

### FORMULA

$nPr=n!(n−r)!nPr=n!(n−r)!$

If you wondered why we defined $0!=10!=1$ earlier, it was to make formulas like this one work; if we have $nn$ objects and want to order all of them (so, we want the number of permutations of $nn$ objects taken $nn$ at a time), we get $nPn=n!(n−n)!=n!0!=n!1=n!nPn=n!(n−n)!=n!0!=n!1=n!$. Next, we’ll get some practice computing these permutations.

### Example 7.6

#### Computing Permutations

Find the following numbers:

1. The number of permutations of 12 objects taken 3 at a time
2. The number of permutations of 8 objects taken 5 at a time
3. The number of permutations of 32 objects taken 2 at a time

Find the following numbers:
1.
The number of permutations of 6 objects taken 2 at a time
2.
The number of permutations of 14 objects taken 4 at a time
3.
The number of permutations of 19 objects taken 3 at a time

### Example 7.7

#### Applying Permutations

1. A high school graduating class has 312 students. The top student is declared valedictorian, and the second-best is named salutatorian. How many possible outcomes are there for the valedictorian and salutatorian?
2. In the card game blackjack, the dealer’s hand of 2 cards is dealt with 1 card faceup and 1 card facedown. If the game is being played with a single deck of (52) cards, how many possible hands could the dealer get?
3. The University Combinatorics Club has 3 officers: president, vice president, and treasurer. If there are 18 members of the club, how many ways are there to fill the officer positions?

1.
One of the big draws at this year’s state fair is the pig race. There are 15 entrants, and prizes are given to the top three finishers. How many different combinations of top-three finishes could there be?

### Who Knew?

#### Very Big Permutations

Permutations involving relatively small sets of objects can get very big, very quickly. A standard deck contains 52 cards. So, the number of different ways to shuffle the cards—in other words, the number of permutations of 52 objects taken 52 at a time—is $52!≈8×106752!≈8×1067$ (written out, that’s an 8 followed by 67 zeroes). The estimated age of the universe is only about $4×10174×1017$ seconds. So, if a very bored all-powerful being started shuffling cards at the instant the universe began, it would have to have averaged at least $8×10674×1017≈2×10508×10674×1017≈2×1050$ shuffles per second since the beginning of time to have covered every possible arrangement of a deck of cards. That means the next time you pick up a deck of cards and give it a good shuffle, it’s almost certain that the particular arrangement you created has never been created before and likely never will be created again.

6.
Compute 5!.
7.
Compute \frac{{10!}}{{7!3!}}.
8.
Compute _{12}{P_3}.
9.
Compute _8{P_4}.
10.
The standard American edition of the board game Monopoly has a deck of 15 orange Chance cards. In how many different ways could the first 4 Chance cards drawn in a game appear?

### Section 7.2 Exercises

For the following exercises, give a whole number that’s equal to the given expression.
1.
3!
2.
9!
3.
\frac{{7!}}{{2!2!3!}}
4.
\frac{{8!}}{{5!2!}}
5.
\frac{{21!}}{{18!2!}}
6.
\frac{{28!}}{{26!2!}}
7.
\frac{{34!}}{{30!3!}}
8.
\frac{{17!}}{{12!5!}}
9.
[_4{P_3}
10.
_7{P_5}
11.
_{12}{P_{10}}
12.
_{14}{P_{10}}
13.
*_{10}{P_8}*
14.
_{15}{P_{11}}
The following exercises are about the card game euchre, which uses a partial standard deck of cards: It only has the cards with ranks 9, 10, J, Q, K, and A for a total of 24 cards. Some variations of the game use the 8s or the 7s and 8s, but we’ll stick with the 24-card version.
15.
A euchre hand contains 5 cards. How many ways are there to receive a 5-card hand (where the order in which the cards are received matters, i.e., 9, J, {\text{K}}\clubsuit , 9\spadesuit, 10\spadesuit is different from 9\spadesuit J, 9, {\text{K}}\clubsuit , 9\spadesuit?
16.
After all 4 players get their hands, the remaining 4 cards are placed facedown in the center of the table. How many arrangements of 4 cards are there from this deck?
17.
Euchre is played with partners. How many ways are there for 2 partners to receive 5-card hands (where the order in which the cards are received matters)?
18.
How many different arrangements of the full euchre deck are possible (i.e., how many different shuffles are there)?
The following exercises involve a horse race with 13 entrants.
19.
How many possible complete orders of finish are there?
20.
An exacta bet is one where the player tries to predict the top two finishers in order. How many possible exacta bets are there for this race?
21.
A trifecta bet is one where the player tries to predict the top three finishers in order. How many possible trifecta bets are there for this race?
22.
A superfecta bet is one where the player tries to predict the top four finishers in order. How many possible superfecta bets are there for this race?