Permutations

AS · S1 · 18 min

A permutation is an arrangement of objects in which the order matters. Counting arrangements quickly, without listing them, is the skill behind this topic: how many ways can seven people stand in a queue, how many different "words" can be made from the letters of NEEDLESS, how many four-digit codes are even. Paper 5 usually has one full question on permutations and combinations, worth around eight marks, built from exactly the situations in the syllabus: arrangements in a line, arrangements with repeated objects, arrangements with restrictions (two people together or apart, fixed ends), and people seated in rows. Circular arrangements are not examined.

The multiplication principle

Everything in this topic rests on one idea.

Key result

If one choice can be made in $m$ ways, and for each of those a second choice can be made in $n$ ways, then the two choices together can be made in $m \times n$ ways. This extends to any number of successive choices.

Think of filling boxes, one per position. To arrange the letters A, B, C, D in a line: the first position can be filled in $4$ ways, the second in $3$ (one letter has been used), the third in $2$ , the last in $1$ . That gives $4 \times 3 \times 2 \times 1 = 24$ arrangements.

Position	1st	2nd	3rd	4th
Choices	$4$	$3$	$2$	$1$

The product $n \times (n - 1) \times \cdots \times 2 \times 1$ is written $n!$ , read " $n$ factorial". By definition $0! = 1$ , which makes the formulas below work in every case.

Key result

The number of ways of arranging $n$ different objects in a line is

n! = n \times (n - 1) \times (n - 2) \times \cdots \times 2 \times 1.

Factorials grow very fast: $5! = 120$ , $8! = 40320$ , $10! = 3628800$ . That is why listing is hopeless and counting methods are needed.

Arranging some of the objects

Often only some of the objects are used. A club of $10$ members chooses a president, a secretary and a treasurer: the order matters (being president is different from being treasurer), and only $3$ of the $10$ are placed. Filling three boxes gives $10 \times 9 \times 8 = 720$ .

Definition

A permutation of $r$ objects from $n$ different objects is an ordered arrangement of $r$ of them. The number of such permutations is written ${}^{n}P_{r}$ :

{}^{n}P_{r} = n(n - 1)(n - 2)\cdots(n - r + 1) = \frac{n!}{(n - r)!}.

Check: ${}^{10}P_{3} = \dfrac{10!}{7!} = 10 \times 9 \times 8 = 720$ . And ${}^{n}P_{n} = \dfrac{n!}{0!} = n!$ , the full arrangement. Your calculator has an ${}^{n}P_{r}$ key.

Repeated objects

The word NEEDLESS has $8$ letters, but three are E and two are S, so many of the $8!$ orderings look identical. If the three Es were labelled $E_1, E_2, E_3$ , each visible arrangement would appear $3! = 6$ times (once for each way of ordering the labels). Likewise, each would appear $2!$ times because of the Ss. So the $8!$ labelled arrangements overcount every real arrangement by a factor of $3! \times 2!$ .

Key result

The number of arrangements of $n$ objects, of which $p$ are alike of one kind, $q$ alike of another kind, $r$ alike of another, and so on, is

\frac{n!}{p!\, q!\, r! \cdots}.

NEEDLESS: $\dfrac{8!}{3!\,2!} = \dfrac{40320}{12} = 3360$ arrangements. Letters that appear once contribute $1! = 1$ and can be ignored in the denominator.

Restrictions

Most marks are for arrangements with conditions. There are a few standard techniques; the art is recognising which one a question needs.

Fixed positions: deal with them first

If a position is restricted (the arrangement must start with a vowel, end with S, the number must be even), fill the restricted positions first, then arrange the rest freely.

Seven different letters C, A, M, B, R, I, D: arrangements beginning with C and ending with D. Fix C and D, then arrange the middle $5$ letters: $5! = 120$ .

Objects that must be together: glue them

Treat the objects that must be together as a single block. Arrange the block with the other objects, then multiply by the number of ways of arranging the objects inside the block.

Seven people including Ali and Bea stand in a line, with Ali and Bea next to each other. Glue them into one block: there are now $6$ items to arrange, in $6!$ ways, and the block can be "Ali Bea" or "Bea Ali", $2!$ ways. Total: $6! \times 2! = 1440$ .

Objects that must not be together: subtract, or use gaps

For two objects that must not be next to each other, the quickest method is

\text{not together} = \text{total} - \text{together}.

For the seven people: $7! - 1440 = 5040 - 1440 = 3600$ .

For three or more objects with no two of them adjacent, subtraction becomes complicated (there are several ways to be "together"). Use the gaps method instead: arrange the unrestricted objects first, then place the restricted objects in the gaps between and at the ends, at most one per gap.

Method

The gaps method (no two of $k$ particular objects adjacent)

Arrange the other $m$ objects: count the ways.
These create $m + 1$ gaps (one before each object and one at the end): $\_\, \text{O} \,\_\, \text{O} \,\_\, \cdots \,\_\, \text{O} \,\_$ .
Place the $k$ restricted objects into $k$ different gaps. If they are all different, this can be done in ${}^{m+1}P_{k}$ ways.
Multiply.

Seven people with Ali, Bea and Cal no two adjacent: arrange the other $4$ in $4! = 24$ ways, which leaves $5$ gaps. Put Ali, Bea and Cal in $3$ of these gaps in ${}^{5}P_{3} = 60$ ways. Total: $24 \times 60 = 1440$ .

Rows of seats

People seated in two rows are arrangements with fixed positions. Number every seat. If certain people must sit in a certain row, place them in that row first, then arrange everyone else in the remaining seats. Seats in different rows are different positions, so "front row" and "back row" are just restrictions on which positions are allowed.

Method

For any arrangement question

Decide what is being arranged and whether the objects are all different.
Deal with the restricted items first: fixed positions, blocks that must be together, items that must be separated (gaps).
Multiply the number of ways at each stage. Divide by $p!\,q!\cdots$ for any repeated objects that remain.
Sanity-check: the restricted count must be smaller than the unrestricted total, and complementary cases must add up to the total.

Permutations and probability

If all arrangements are equally likely (the letters are "arranged at random"), a probability is a ratio of counts:

P(\text{event}) = \frac{\text{number of arrangements with the property}}{\text{total number of arrangements}}.

For NEEDLESS arranged at random, the probability the arrangement starts with E: fix an E at the front, then arrange the other $7$ letters (two Es and two Ss among them) in $\dfrac{7!}{2!\,2!} = 1260$ ways. So the probability is $\dfrac{1260}{3360} = \dfrac{3}{8}$ , which agrees with the direct argument that $3$ of the $8$ letters are E.

Worked examples

Arrangements and fixed ends (routine)

Find the number of different arrangements of the $9$ letters of the word CAMBRIDGE.

(a) in total, (b) that begin with C and end with E, (c) in which the three vowels A, I, E are together.

Solution

All $9$ letters are different.

(a) $9! = 362880$ .

(b) Fix C first and E last; arrange the other $7$ letters: $7! = 5040$ .

(c) Glue A, I, E into one block. Arrange the block with the $6$ consonants: $7!$ ways. Arrange the vowels inside the block: $3!$ ways. Total $7! \times 3! = 5040 \times 6 = 30240$ .

Repeated letters with conditions

Find the number of different arrangements of the $8$ letters of NEEDLESS

(a) in total, (b) in which the three Es are together, (c) in which the two Ss are not next to each other.

Solution

NEEDLESS: N, E, E, E, D, L, S, S (three Es, two Ss).

(a) $\dfrac{8!}{3!\,2!} = 3360$ .

(b) Treat EEE as one block. Items: [EEE], N, D, L, S, S, that is $6$ items with two Ss alike. The Es inside the block are identical, so there is only $1$ internal arrangement. Total $\dfrac{6!}{2!} = 360$ .

(c) First count arrangements with the Ss together: block [SS] with N, E, E, E, D, L is $7$ items with three Es alike: $\dfrac{7!}{3!} = 840$ . So Ss not together $= 3360 - 840 = 2520$ .

People standing in a line

Seven people, including Ali, Bea and Cal, stand in a line. Find the number of arrangements in which

(a) Ali and Bea stand next to each other,

(b) Ali and Bea do not stand next to each other,

Solution

(a) Block [Ali Bea] plus $5$ others: $6!$ arrangements, times $2!$ for the order inside the block: $720 \times 2 = 1440$ .

(b) Total $7! = 5040$ , so $5040 - 1440 = 3600$ .

(c) Gaps method. Arrange the other $4$ people: $4! = 24$ ways. This gives $5$ gaps: $\_\,P\,\_\,P\,\_\,P\,\_\,P\,\_$ . Place Ali, Bea and Cal in $3$ different gaps: ${}^{5}P_{3} = 5 \times 4 \times 3 = 60$ ways. Total $24 \times 60 = 1440$ .

Forming numbers from digits

Four-digit numbers are formed from the digits $1, 2, 3, 4, 5, 6, 7$ , with no digit repeated. Find how many of these numbers are

(a) possible in total, (b) even, (c) greater than $5000$ , (d) even and greater than $5000$ .

Solution

(a) ${}^{7}P_{4} = 7 \times 6 \times 5 \times 4 = 840$ .

(b) The last digit must be $2$ , $4$ or $6$ : $3$ ways. The first three digits are then chosen in order from the remaining $6$ : ${}^{6}P_{3} = 120$ . Total $3 \times 120 = 360$ .

(d) Both the first and last digits are restricted, and they interact: whether the first digit is even affects how many even digits are left for the end. Split into cases.

First digit $5$ or $7$ (odd): $2$ ways; last digit $2$ , $4$ or $6$ : $3$ ways; middle two from the remaining $5$ : $5 \times 4 = 20$ . Subtotal $2 \times 3 \times 20 = 120$ .
First digit $6$ : $1$ way; last digit $2$ or $4$ : $2$ ways; middle two: $20$ . Subtotal $40$ .

Total $120 + 40 = 160$ .

Seating in two rows (exam style)

A family of $3$ adults and $5$ children sit for a photograph in two rows of $4$ seats, one row behind the other. Find the number of ways they can be arranged if

(a) there are no restrictions,

(b) all $3$ adults sit in the back row,

(c) all $3$ adults sit in the back row and two particular children, Dan and Eve, sit next to each other in the front row.

Solution

(a) $8$ people in $8$ different seats: $8! = 40320$ .

(b) Place the adults in $3$ of the $4$ back-row seats: ${}^{4}P_{3} = 24$ ways. The $5$ children fill the remaining $5$ seats: $5! = 120$ ways. Total $24 \times 120 = 2880$ .

(c) Adults in the back row: $24$ ways, as before. In the front row of $4$ seats there are $3$ pairs of adjacent seats, and Dan and Eve can sit in either order: $3 \times 2 = 6$ ways. The other $3$ children fill the remaining $3$ seats (one back, two front): $3! = 6$ ways. Total $24 \times 6 \times 6 = 864$ .

Repetition, restrictions and probability (exam-hard)

The $10$ letters of the word STATISTICS are arranged in a line.

(a) Find the number of different arrangements.

(b) Find the number of arrangements that begin and end with S.

(d) An arrangement is chosen at random. Find the probability that it begins and ends with S.

Solution

STATISTICS: S three times, T three times, I twice, A once, C once.

(a) $\dfrac{10!}{3!\,3!\,2!} = \dfrac{3628800}{72} = 50400$ .

(b) Fix S at each end. The middle $8$ letters are S, T, T, T, A, I, I, C: one S, three Ts, two Is. $\dfrac{8!}{3!\,2!} = 3360$ .

(c) Is together: block [II] with S, S, S, T, T, T, A, C, that is $9$ items with three Ss and three Ts alike: $\dfrac{9!}{3!\,3!} = 10080$ . Not together: $50400 - 10080 = 40320$ .

(d) $\dfrac{3360}{50400} = \dfrac{1}{15}$ . Check directly: $P(\text{first is S}) \times P(\text{last is S} \mid \text{first is S}) = \dfrac{3}{10} \times \dfrac{2}{9} = \dfrac{1}{15}$ .

Watch out

Forgetting the arrangements inside a block. Gluing Ali and Bea together gives $6!$ arrangements of the items, but each has Ali on the left or Bea on the left. Multiply by $2!$ (or $k!$ for a block of $k$ different objects). If the objects in the block are identical, as with EEE, there is only $1$ internal arrangement.

Watch out

Subtracting for three or more separated objects. "Total minus all three together" counts arrangements where two of them are still adjacent. Use the gaps method whenever no two of three or more objects may touch.

Watch out

Dividing out repeats too early or not at all. In "Ss together" for NEEDLESS, the two Ss are inside the block, so they no longer appear in the denominator, but the three Es outside still do: $\dfrac{7!}{3!}$ , not $\dfrac{7!}{3!\,2!}$ .

Watch out

Interacting restrictions. When two restrictions can use the same object (first digit and last digit both drawn from the even digits), a single product is wrong. Split into cases and add.

Exam tip

Write a short reason next to every factor: " $6!$ for the block and 5 others, $\times 2$ for the order inside the block". Method marks are given for the structure even if the arithmetic slips.
Final answers are exact integers; give them in full ( $30240$ , not $3.02 \times 10^4$ ).
Use the complement (total minus together) whenever it is quicker, but state that is what you are doing.
In probability parts, the total number of arrangements found earlier is usually the denominator; reuse it.
Read "next to each other", "together", "at each end", "in the front row" very carefully: each phrase signals a specific technique.
A sense check you can always do: the restricted answer must be smaller than the unrestricted one.

Summary

Multiplication principle: successive choices multiply. Fill positions one at a time.
$n$ different objects in a line: $n!$ ways; $0! = 1$ .
$r$ objects from $n$ , order mattering: ${}^{n}P_{r} = \dfrac{n!}{(n - r)!}$ .
Repeated objects: $\dfrac{n!}{p!\,q!\cdots}$ .
Fixed positions: fill them first.
Together: glue into a block, arrange, then multiply by the arrangements inside the block.
Not together (two objects): total minus together. No two of several: gaps method.
Rows of seats: treat seats as positions and place restricted people first.
Probability with random arrangements: favourable count $\div$ total count.

Practice questions

Question

In how many ways can $6$ different books be arranged on a shelf? In how many of these are two particular books at the two ends of the shelf?
Find the number of different arrangements of the letters of BANANA.
Ten runners compete in a race. In how many ways can the gold, silver and bronze medals be awarded?
Find the number of arrangements of the letters of PARALLEL (a) in total, (b) in which the three Ls are together.
Five boys and three girls stand in a line. Find the number of arrangements in which (a) the three girls stand together, (b) no two girls stand next to each other.
Three-digit numbers are formed from the digits $0, 1, 2, 3, 4, 5$ with no repetition. (A number cannot begin with $0$ .) How many of these numbers are odd and greater than $300$ ?
Find the number of arrangements of the letters of DECIDED (a) in total, (b) that begin and end with D, (c) in which the three vowels are together.
Ten people sit in two rows of $5$ seats. Two of them, Fay and Gus, must sit in the front row. Find the number of arrangements (a) with this condition only, (b) if also Fay and Gus must sit next to each other.
The letters of MISSISSIPPI are arranged at random. Find the probability that the arrangement begins and ends with S.
Find the number of arrangements of NEEDLESS in which no two Es are next to each other.

Answers

$6! = 720$ . With two particular books at the ends: they can be placed in $2! = 2$ ways, and the other $4$ books arranged in $4! = 24$ ways, giving $48$ .
Six letters with three As and two Ns: $\dfrac{6!}{3!\,2!} = \dfrac{720}{12} = 60$ .
Order matters (gold is different from silver): ${}^{10}P_{3} = 10 \times 9 \times 8 = 720$ .
PARALLEL: P, A, A, R, L, L, L, E (two As, three Ls). (a) $\dfrac{8!}{2!\,3!} = \dfrac{40320}{12} = 3360$ . (b) Block [LLL] with P, A, A, R, E: $6$ items with two As alike: $\dfrac{6!}{2!} = 360$ .
(a) Block of $3$ girls plus $5$ boys: $6!$ arrangements, times $3!$ inside the block: $720 \times 6 = 4320$ . (b) Arrange the boys: $5! = 120$ . They create $6$ gaps; place the $3$ girls in $3$ different gaps: ${}^{6}P_{3} = 120$ . Total $120 \times 120 = 14400$ .
The first digit is $3$ , $4$ or $5$ ; the last digit is $1$ , $3$ or $5$ , and these can clash. First digit $3$ : last digit $1$ or $5$ ( $2$ ways), middle digit from the $4$ remaining: $8$ . First digit $4$ : last digit $1$ , $3$ or $5$ ( $3$ ways), middle $4$ ways: $12$ . First digit $5$ : last digit $1$ or $3$ , middle $4$ ways: $8$ . Total $8 + 12 + 8 = 28$ .
DECIDED: D three times, E twice, C, I. (a) $\dfrac{7!}{3!\,2!} = 420$ . (b) Fix D at each end; arrange D, E, E, C, I in the middle: $\dfrac{5!}{2!} = 60$ . (c) The vowels are E, I, E. Block [vowels] with D, D, D, C: $5$ items with three Ds alike: $\dfrac{5!}{3!} = 20$ . Inside the block, E, I, E can be arranged in $\dfrac{3!}{2!} = 3$ ways. Total $20 \times 3 = 60$ .
(a) Fay and Gus in $2$ of the $5$ front seats: ${}^{5}P_{2} = 20$ ways. The other $8$ people fill $8$ seats: $8! = 40320$ . Total $20 \times 40320 = 806400$ . (b) A row of $5$ has $4$ adjacent pairs of seats, and Fay and Gus can sit in either order: $8$ ways. Total $8 \times 8! = 322560$ .
MISSISSIPPI: M once, I four times, S four times, P twice. Total arrangements $\dfrac{11!}{4!\,4!\,2!} = 34650$ . Beginning and ending with S: the middle $9$ letters are M, I, I, I, I, S, S, P, P: $\dfrac{9!}{4!\,2!\,2!} = 3780$ . Probability $\dfrac{3780}{34650} = \dfrac{6}{55} = 0.109$ (3 s.f.). Check: $\dfrac{4}{11} \times \dfrac{3}{10} = \dfrac{6}{55}$ .
Arrange N, D, L, S, S first: $\dfrac{5!}{2!} = 60$ ways. This creates $6$ gaps. The three Es are identical, so we only choose which $3$ gaps receive an E: ${}^{6}P_{3} \div 3! = \dfrac{120}{6} = 20$ ways (this is ${}^{6}C_{3}$ , see combinations). Total $60 \times 20 = 1200$ .

The multiplication principle

Arranging some of the objects

Repeated objects

Restrictions

Fixed positions: deal with them first

Objects that must be together: glue them

Objects that must not be together: subtract, or use gaps

Rows of seats

Permutations and probability

Worked examples

Practice questions

Console