Algebra 2

Permutations

A club of fifteen members elects a president, a vice-president and a treasurer. How many outcomes are there, when only three of the fifteen are placed and the other twelve are left out?

You need

Arrangements and factorialsAlgebra 2 Simplifying rational expressionsGrades 10 to 11

Unlocks

Counting with restrictionsAlgebra 2

Where you are 10 in Counting

Probability4

Counting10

▴ 5 above The fundamental counting principle Pascal's triangle

Permutations

Counting with restrictions The binomial theorem

Why this exists

The factorial counts the orders of a whole set, every object used once. Very often only some of the objects are placed. A club of 15 fills three offices, a contest gives out a first and a second prize, a lock code uses five of the ten digits. The rest of the set is left out, and yet the order of the ones chosen still matters: being president is not being treasurer.

The fundamental counting principle counts these too, by filling the places one at a time, but the product now stops part-way down. That stopped product turns up so often that it gets its own symbol, P(n, r), and a formula as a quotient of factorials. Working with that formula means simplifying factorial expressions, the way rational expressions are simplified by canceling common factors. The same dividing idea then answers a second question the factorial alone cannot: how many different rows can be made when some of the objects are exactly alike, such as the letters of a word with a repeated letter.

Definition

A permutation of r objects chosen from n is a row of r of the n different objects, each used at most once, where the order matters. The other n - r objects are not used. Here n and r are whole numbers with 0 \le r \le n.

The number of such permutations is written

P(n, r)

and read “the number of permutations of n objects taken r at a time”. Other books write {}_{n}P_{r} or P^{n}_{r} for the same number. When r = n every object is used, so P(n, n) is the number of arrangements of the whole set.

A permutation with repeated objects is a row that uses every one of n objects, where some of them are identical and cannot be told apart. Two rows are the same when they look the same, so swapping two identical objects does not make a new row.

Intuition

Picture the three offices of the club as three empty boxes, filled from the left. The president can be any of the 15 members. Whoever that is, 14 members are left for vice-president, and then 13 for treasurer. The remaining 12 members are never placed, so there is no factor for them.

Figure 1Each office is filled from the members still free, so the counts fall by one, and the product stops after three factors.

The product 15 \times 14 \times 13 is the start of 15! with the tail 12! cut off. Cutting off a tail of a product is division, which is where the formula P(n, r) = \dfrac{n!}{(n - r)!} comes from. There is also a counting way to see the division: line up all 15 members and read the first three as president, vice-president and treasurer. Each choice of officers comes from 12! different line-ups, one for every order of the twelve people behind them, so the 15! line-ups fall into groups of 12!.

When some objects are alike

The word EEL has three letters, but two of them are the same. Give the two E’s labels for a moment, \text{E}_1 and \text{E}_2. With labels, the three letters are different and have 3! = 6 arrangements. Rubbing out the labels makes them collapse in pairs.

Row once the labels are removed	Rows with labels
EEL	\text{E}_1\text{E}_2\text{L}, \text{E}_2\text{E}_1\text{L}
ELE	\text{E}_1\text{L}\text{E}_2, \text{E}_2\text{L}\text{E}_1
LEE	\text{L}\text{E}_1\text{E}_2, \text{L}\text{E}_2\text{E}_1

Every word appears exactly 2! = 2 times, once for each order of the two E’s, so there are \dfrac{3!}{2!} = 3 different words. Division again undoes the over-counting.

Results

Permutations of some of the objects. For whole numbers 0 \le r \le n, the number of rows of r objects chosen from n different objects is a product of r factors, falling by one each time:

P(n, r) = n(n - 1)(n - 2) \cdots (n - r + 1)

and, as a quotient of factorials,

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

Special values. P(n, n) = n!, since (n - n)! = 0! = 1. P(n, 1) = n. P(n, 0) = 1: there is exactly one row of no objects, the empty row.

One more place. For 0 \le r < n, P(n, r + 1) = P(n, r) \times (n - r): after r places are filled, n - r objects are left for the next.

Permutations with repeated objects. Suppose n objects are of k kinds, with a_1 identical objects of the first kind, a_2 of the second, and so on, so that a_1 + a_2 + \cdots + a_k = n. The number of different rows using all n objects is

\frac{n!}{a_1!\, a_2! \cdots a_k!}

A kind with only one object contributes 1! = 1 to the bottom, so it may be left out.

Why it is true

The product. Fill the r places from the left. The first place can take any of the n objects. Whatever went there is used up, so the second place has n - 1 choices, and this number is the same whichever object went first. Each place has one choice fewer than the one before, so the r-th place has n - (r - 1) = n - r + 1 choices. The fundamental counting principle multiplies them, giving n(n - 1) \cdots (n - r + 1). Different sequences of choices put a different object in some place, so no row is counted twice.

The quotient. Multiply the product by \dfrac{(n - r)!}{(n - r)!}, which equals 1 because (n - r)! is never zero. The top becomes

\begin{aligned} &n(n - 1) \cdots (n - r + 1) \\ &\times (n - r)(n - r - 1) \cdots 1 = n! \end{aligned}

so the product equals \dfrac{n!}{(n - r)!}. When r = n the empty tail is 0! = 1, which is one of the reasons 0! is defined to be 1.

Repeated objects. Give every object a label, so that all n are different; with labels there are n! rows. Take any row of the unlabeled objects. The a_1 objects of the first kind sit in some a_1 places, and their labels can be put in those places in a_1! orders; whatever was done there, the labels of the second kind can go in a_2! orders, and so on. So each unlabeled row comes from exactly a_1!\, a_2! \cdots a_k! labeled rows, and every labeled row, with its labels rubbed out, gives exactly one unlabeled row. The n! labeled rows therefore fall into groups of equal size a_1!\, a_2! \cdots a_k!, one group per unlabeled row, and dividing gives the count.

Worked examples

Example 1

Electing three officers

A club of 15 members elects a president, a vice-president and a treasurer. No one may hold two offices. In how many ways can this be done? Compare it with the number of ways to put all 15 members in a row.

Solution

The offices are different, so the order of choosing matters: Ingrith as president with Bede as treasurer is a different outcome from Bede as president with Ingrith as treasurer. Fill the offices in turn. The president can be any of 15 members, the vice-president any of the 14 still free, and the treasurer any of the 13 left:

P(15, 3) = 15 \times 14 \times 13 = 2{,}730

The quotient form gives the same number once the 12! cancels:

\begin{aligned} \frac{15!}{12!} &= \frac{15 \times 14 \times 13 \times 12!}{12!} \\ &= 2{,}730 \end{aligned}

Placing all 15 members in a row would be 15! = 1{,}307{,}674{,}368{,}000 ways. Electing three officers is the first three factors of that product and nothing more.

Example 2

Reading the symbol

Find P(13, 3), P(6, 6), P(9, 1) and P(9, 0), and say what each counts.

Solution

P(13, 3) has three factors starting at 13:

P(13, 3) = 13 \times 12 \times 11 = 1{,}716

It counts the rows of 3 objects taken from 13 different ones.

P(6, 6) uses every object, so it is a factorial. In the quotient form the bottom is 0! = 1:

P(6, 6) = \frac{6!}{0!} = \frac{720}{1} = 720

P(9, 1) = \dfrac{9!}{8!} = 9: a row of one object is just a choice of that object, and there are 9 to choose from.

P(9, 0) = \dfrac{9!}{9!} = 1: there is one way to place none of the objects, the empty row.

Example 3

Simplifying factorial expressions

Simplify, for whole numbers n large enough that every factorial is defined.

(a) \dfrac{n!}{(n - 3)!} for n \ge 3

(b) \dfrac{(n - 1)!}{(n + 1)!} for n \ge 1

(d) \dfrac{1}{5!} + \dfrac{1}{6!}, as a single fraction

Solution

The tool throughout is m! = m \times (m - 1)!, used to write the larger factorial only as far down as the smaller one, so that a common factor can be canceled exactly as in a rational expression.

(a) Write n! = n(n - 1)(n - 2) \times (n - 3)! and cancel the (n - 3)!:

\frac{n!}{(n - 3)!} = n(n - 1)(n - 2)

This is P(n, 3).

(b) Now the larger factorial is on the bottom: (n + 1)! = (n + 1) \times n \times (n - 1)!. Cancel the (n - 1)!, which leaves 1 on top:

\frac{(n - 1)!}{(n + 1)!} = \frac{1}{n(n + 1)}

(c) There is no fraction here, but the same rewriting finds a common factor. Since (n + 1)! = (n + 1) \times n!, take out the factor n! by the distributive property:

(n + 1)! - n! = n!\,\big((n + 1) - 1\big) = n \times n!

Check with n = 3: 4! - 3! = 24 - 6 = 18, and 3 \times 3! = 3 \times 6 = 18.

(d) The common denominator is 6!, because 6! = 6 \times 5!. Multiply the first fraction by \dfrac{6}{6}:

\begin{aligned} \frac{1}{5!} + \frac{1}{6!} &= \frac{6}{6!} + \frac{1}{6!} \\ &= \frac{7}{6!} = \frac{7}{720} \end{aligned}

Example 4

Working back from a count

(a) A chess tournament awards a gold and a silver medal to two different players. There are 182 possible ways for the medals to go. How many players entered?

(b) Find n if P(n, 4) = 9 \times P(n, 3).

Solution

(a) With n players, the gold can go to any of n and the silver to any of the other n - 1, so P(n, 2) = n(n - 1) = 182. Expand and bring everything to one side:

n^2 - n - 182 = 0

Two numbers with product -182 and sum -1 are -14 and 13, so (n - 14)(n + 13) = 0 and n = 14 or n = -13. A number of players cannot be negative, so n = 14.

Check: 14 \times 13 = 182.

(b) By the “one more place” result, P(n, 4) = P(n, 3) \times (n - 3). For n \ge 4 the count P(n, 3) is not zero, so dividing both sides of P(n, 3) \times (n - 3) = 9 \times P(n, 3) by it is allowed:

n - 3 = 9, \qquad n = 12

Check: P(12, 4) = 11{,}880 and P(12, 3) = 1{,}320, and 9 \times 1{,}320 = 11{,}880.

Example 5

Painting rooms with and without repeats

The 4 rooms of a flat (kitchen, hall, bedroom and bathroom) are each painted one of 12 different colors.

(a) In how many ways can this be done if no two rooms may share a color?

(b) In how many ways if colors may be repeated?

Solution

(a) The rooms are different, so giving the kitchen red and the hall blue is not the same as the other way round. Without repeats, a painting is a row of 4 of the 12 colors, one for each room in a fixed order, so it is a permutation:

P(12, 4) = 12 \times 11 \times 10 \times 9 = 11{,}880

(b) With repeats allowed, every room has all 12 colors available, whatever came before. The counting principle gives 12 \times 12 \times 12 \times 12:

12^4 = 20{,}736

This is not a permutation count: the choices do not shrink.

(c) Every painting either repeats a color or does not, and not both, so the paintings with a repeat are all paintings minus those without:

20{,}736 - 11{,}880 = 8{,}856

Example 6

A word with three repeated letters

In how many different ways can the letters of CROSSROADS be arranged?

Solution

Count the letters by kind. CROSSROADS has 10 letters: C once, R twice, O twice, S three times, A once and D once. The kinds add up to 1 + 2 + 2 + 3 + 1 + 1 = 10, as they must. With labels on the repeated letters there would be 10! rows; each word comes from 2! orders of the R’s, 2! of the O’s and 3! of the S’s, so

\begin{aligned} \frac{10!}{2!\, 2!\, 3!} &= \frac{3{,}628{,}800}{2 \times 2 \times 6} \\ &= \frac{3{,}628{,}800}{24} = 151{,}200 \end{aligned}

The letters used once each contribute 1! = 1 to the bottom and change nothing.

Example 7

Shortest routes on a grid

Bramwell walks from the bottom left corner to the top right corner of a grid of streets five blocks wide and three blocks tall, always going east or north along a street. How many shortest routes are there?

Figure 2Every shortest route is a row of five E’s and three N’s, so the routes are counted like the arrangements of a word with repeated letters.

Solution

A shortest route never goes west or south, so it uses exactly 5 blocks east and 3 blocks north, 8 blocks in all. Write E for a block east and N for a block north. The route in the figure is EENENEEN. Every shortest route gives a row of five E’s and three N’s, and every such row is a shortest route: follow the letters in turn, and after all eight the walker is 5 east and 3 north of the start. So the routes are counted like a word with two repeated letters:

\begin{aligned} \frac{8!}{5!\, 3!} &= \frac{40{,}320}{120 \times 6} \\ &= \frac{40{,}320}{720} = 56 \end{aligned}

The same count can be seen another way: a row of eight letters is fixed once it is known which 3 of the 8 places hold an N. Choosing places without caring about their order is the idea of combinations.

Boundaries

The objects must be different, unless the repeats are divided out. P(n, r) assumes n distinct objects. If some are identical, P(n, n) = n! counts each row several times, and the formula with a_1!\, a_2! \cdots a_k! on the bottom is needed instead. That formula is for rows that use all n objects; placing only some of a collection with repeats, such as 3 letters chosen from CROSSROADS, has no single quotient and is counted case by case.

No object may be used twice. The falling factors n, n - 1, n - 2, \ldots come from objects being used up. When repeats are allowed, as with the painted rooms in part (b), every place has all n choices and the count is n^r, not P(n, r).

The order must matter. P(n, r) counts rows, so the same r objects in two different orders are two outcomes. If only which objects are picked matters, such as a committee with no offices, each group of r has been counted r! times; that count is a combination.

r cannot exceed n. P(n, r) is defined for whole numbers with 0 \le r \le n. There is no way to fill more places than there are objects, and the quotient \dfrac{n!}{(n - r)!} would need the factorial of a negative number, which does not exist.

Where this goes next

Dividing P(n, r) by the r! orders of the chosen objects gives the number of unordered choices, the combinations; their values fill Pascal’s triangle and are the coefficients of the binomial theorem. When one place carries a rule, such as a given person being president, that place is filled first, which is counting with a restriction. The division by repeated objects returns when choosing several items of the same kind with repeats allowed, in stars and bars, and ordered and unordered counts together give the probabilities of drawing without replacement. The whole family lives under counting.

Exercises

The symbol and factorial expressions

Find P(8, 3).
Find P(13, 2).
Find P(7, 7) and P(20, 1).
Simplify \dfrac{(2n)!}{(2n - 2)!} for a whole number n \ge 1.
Simplify \dfrac{(n - 2)!}{n!} for a whole number n \ge 2.
Write \dfrac{1}{4!} - \dfrac{1}{5!} as a single fraction in lowest terms.
Write 20 \times 19 \times 18 \times 17 as a quotient of two factorials and as P(n, r), and find its value.

Ordered choices

A baking contest has 11 entries. A first prize and a second prize go to two different entries. In how many ways can the prizes be awarded?
How many rows of 4 different letters can be made from the six letters A, B, C, D, E and F?
Seven different young trees are available and four holes are dug in a row. In how many ways can four of the trees be planted, one in each hole?
A ten-sided die, numbered 1 to 10, is rolled 5 times and the results written in order. How many of these rows have all five numbers different? How many rows are there in all?
A committee of 16 people chooses a chair and a secretary, who must be different people. How many outcomes are there?

Repeated objects

In how many different ways can the letters of COFFEE be arranged?
In how many different ways can the letters of COCOA be arranged?
Four identical red counters and three identical blue counters are put in a row. How many different rows are there?
In how many different ways can the letters of REFERENCE be arranged?
A coin is tossed 10 times and the result written as a row of H’s and T’s. How many rows have exactly 3 H’s?

Working backwards

Find n if P(n, 2) = 90.
Find n if P(n, 3) = 7 \times P(n, 2).
How many shortest routes are there from one corner of a grid of streets four blocks wide and four blocks tall to the opposite corner, going only east or north?

Reasoning

Explain why P(n, n) = P(n, n - 1) for every whole number n \ge 1.
Explain, by counting, why P(n, r) = n \times P(n - 1, r - 1) for whole numbers 1 \le r \le n.
The word EEL has 3! labeled arrangements but only 3 words. Explain why the right step is to divide 3! by 2!, rather than to subtract the repeats one at a time, and why the division always comes out exact.
The product n(n - 1) \cdots (n - r + 1) can be written down even when r = n + 1. Explain what it equals then, why that value fits the counting meaning, and why the quotient \dfrac{n!}{(n - r)!} cannot be used for it.

Answers

336. P(8, 3) = 8 \times 7 \times 6 = 336.
156. P(13, 2) = 13 \times 12 = 156.
P(7, 7) = 7! = 5{,}040 and P(20, 1) = 20.
2n(2n - 1). Since (2n)! = 2n \times (2n - 1) \times (2n - 2)!, the (2n - 2)! cancels. For example, with n = 3: \dfrac{6!}{4!} = 30 = 6 \times 5.
\dfrac{1}{n(n - 1)}. Since n! = n(n - 1) \times (n - 2)!, the (n - 2)! cancels and leaves 1 on top. For example, with n = 4: \dfrac{2!}{4!} = \dfrac{2}{24} = \dfrac{1}{12}.
\dfrac{1}{30}. Since 5! = 5 \times 4!, write \dfrac{1}{4!} = \dfrac{5}{5!}; then \dfrac{5 - 1}{5!} = \dfrac{4}{120} = \dfrac{1}{30}.
\dfrac{20!}{16!} = P(20, 4) = 116{,}280. The four factors fall from 20, and the missing tail is 16!.
110. P(11, 2) = 11 \times 10 = 110.
360. P(6, 4) = 6 \times 5 \times 4 \times 3 = 360.
840. P(7, 4) = 7 \times 6 \times 5 \times 4 = 840; the holes are in a row, so order matters.
30{,}240 with all numbers different, since P(10, 5) = 10 \times 9 \times 8 \times 7 \times 6; and 10^5 = 100{,}000 rows in all, since every roll can show any of the 10 numbers.
240. P(16, 2) = 16 \times 15 = 240.
180. COFFEE has 6 letters with F twice and E twice: \dfrac{6!}{2!\, 2!} = \dfrac{720}{4} = 180.
30. COCOA has 5 letters with C twice and O twice: \dfrac{5!}{2!\, 2!} = \dfrac{120}{4} = 30.
35. \dfrac{7!}{4!\, 3!} = \dfrac{5{,}040}{24 \times 6} = 35.
7{,}560. REFERENCE has 9 letters with E four times and R twice: \dfrac{9!}{4!\, 2!} = \dfrac{362{,}880}{48} = 7{,}560.
120. A row of 3 H’s and 7 T’s: \dfrac{10!}{3!\, 7!} = \dfrac{3{,}628{,}800}{6 \times 5{,}040} = 120.
n = 10. n(n - 1) = 90 gives n^2 - n - 90 = 0, so (n - 10)(n + 9) = 0, and n cannot be negative.
n = 9. P(n, 3) = P(n, 2) \times (n - 2), and P(n, 2) is not zero for n \ge 3, so n - 2 = 7. Check: 9 \times 8 \times 7 = 504 = 7 \times 72.
70. A route is a row of four E’s and four N’s: \dfrac{8!}{4!\, 4!} = \dfrac{40{,}320}{576} = 70.
Once n - 1 of the n objects are in a row, exactly one object is left and it must go in the last place, so filling the last place adds a factor of 1. In symbols, the “one more place” result gives P(n, n) = P(n, n - 1) \times 1.
Choose the object for the first place in n ways. Whatever it is, the remaining r - 1 places are filled from the n - 1 objects left, in P(n - 1, r - 1) ways. The counting principle multiplies these, and the total is also P(n, r).
Each word appears among the labeled rows exactly 2! times, once for each order of the two labeled E’s, so the 3! labeled rows split into equal groups of 2!, one group per word. A number made of equal groups is divided by the group size to count the groups; subtracting would need to know how many rows to remove, which is the same question. The division is exact because the groups are all the same size, so 3! is exactly 3 groups of 2.
The last factor is n - (n + 1) + 1 = 0, so the product is 0. That fits: there is no way to put n + 1 different objects from a set of n in a row, because some object would have to be used twice. The quotient would be \dfrac{n!}{(-1)!}, and there is no factorial of -1.