Permutations – OCR FSMQ Additional Maths

1 What a Permutation Is

EN4: enumerate the number of ways of obtaining an ordered linear subset — a permutation — of $r$ elements from a set of $n$ distinct objects. The specification also requires the notation ${}^nP_r$.

"Ordered" is the key word. In a permutation, who goes where matters. Choosing Amy then Ben is a different permutation from choosing Ben then Amy.

The permutation formula

${}^nP_r = \dfrac{n!}{(n-r)!} = \underbrace{n \times (n-1) \times \cdots \times (n-r+1)}_{r \text{ factors}}$

The second form is the one to use. For ${}^{10}P_3$, just write $10 \times 9 \times 8 = 720$. There is no need to go anywhere near $10!$.

Worked Example 1 — The specification's example

In how many ways can two prizes — a first prize and a second prize — be awarded in a group of ten people?

①The prizes are different, so order matters: this is a permutation.

②${}^{10}P_2 = 10 \times 9 = 90$

③Check with the formula: $\dfrac{10!}{8!} = 10 \times 9 = 90$ ✓

If the two prizes were identical, order would not matter and the answer would be ${}^{10}C_2 = 45$ — exactly half. Read the question carefully.

2 Why the Formula Works

The formula is just the product rule applied to $r$ stages, with one object used up at each stage.

Worked Example 2 — Building it from the product rule

Three positions are filled from $7$ candidates. Count the ways.

①First position: $7$ choices.

②Second position: that person is gone, so $6$ choices.

③Third position: $5$ choices.

④$7 \times 6 \times 5 = 210$, which is exactly ${}^7P_3$.

⑤As a factorial: $\dfrac{7!}{4!} = \dfrac{5040}{24} = 210$ ✓

Two special cases

${}^nP_n = n!$ — arranging all the objects
${}^nP_1 = n$ — just choosing one

${}^nP_n = \dfrac{n!}{0!} = \dfrac{n!}{1} = n!$. This is the reason mathematicians define $0! = 1$ — it makes the formula work at the extreme.

3 Permutation or Combination?

The test

Pick two of your chosen items and swap them.
Is the result a genuinely different outcome? Yes $\to$ permutation. No $\to$ combination.

Situation	Which?	Why
Gold, silver, bronze medals	Permutation	The medals are different
Three finalists chosen	Combination	All three are just "finalists"
President and treasurer	Permutation	Different roles
A committee of two	Combination	Same role
A PIN code	Permutation	$1234 \neq 4321$
A lottery ticket	Combination	The balls are drawn in any order
Seating people in a row	Permutation	Positions differ
Dealing a hand of cards	Combination	The hand is the same however it arrives

The word "combination" in everyday English is misleading. A "combination lock" actually needs a permutation — the order of the digits matters. Ignore the everyday usage and apply the swap test.

4 Permutations with Restrictions

Identify the restriction and deal with that position or item first.
Count the choices remaining for the free positions.
Multiply.
If the restriction is "not…", it is often easier to count the total and subtract.

Worked Example 3 — A fixed first choice

Four different prizes are awarded among $9$ people, no one winning twice. In how many ways can this happen if Priya must win the first prize?

①The first prize is fixed: $1$ way.

②The remaining three prizes go to $3$ of the other $8$ people, in order.

③${}^8P_3 = 8 \times 7 \times 6 = 336$

④$1 \times 336 = 336$ ways.

Worked Example 4 — Counting the complement

Three officers — chair, secretary and treasurer — are chosen from $8$ members. In how many ways, if Tom must not be the chair?

①Total without restriction: ${}^8P_3 = 8 \times 7 \times 6 = 336$

②Those with Tom as chair: chair fixed, then ${}^7P_2 = 7 \times 6 = 42$

③$336 - 42 = 294$

④Direct check: $7$ choices of chair (not Tom), then ${}^7P_2 = 42$ for the rest: $7 \times 42 = 294$ ✓

Two independent routes to the same number is the best evidence you have counted correctly.

Worked Example 5 — Repeated letters

How many distinct arrangements are there of all the letters of the word LEVEL?

①There are $5$ letters, so $5! = 120$ if all were different.

②But there are two Ls and two Es. Swapping the two Ls gives the same word.

③Each arrangement has been counted $2!$ times for the Ls and $2!$ times for the Es.

④$\dfrac{5!}{2!\,2!} = \dfrac{120}{4} = 30$

Divide by the factorial of each repeat count. This is the same "divide out the overcounting" idea that turns ${}^nP_r$ into ${}^nC_r$.

5 Quick Reference

Meaning

An ordered selection of $r$ from $n$.

Formula

${}^nP_r = \dfrac{n!}{(n-r)!}$.

Fast method

$r$ descending factors from $n$.

${}^nP_n$

Equals $n!$.

The swap test

Different outcome after swapping $\Rightarrow$ permutation.

Different roles

Signals a permutation.

Same role

Signals a combination.

Restrictions

Fix the restricted position first.

"Not…"

Total minus the forbidden cases.

Repeats

Divide by the factorial of each repeat count.

6 Practice Questions

Question 1

Evaluate ${}^9P_2$ and ${}^6P_4$.

▶ Show solution

${}^9P_2 = 9 \times 8 = 72$

${}^6P_4 = 6 \times 5 \times 4 \times 3 = 360$

Question 2

Five different books are placed in $3$ of $5$ slots on a shelf. How many arrangements?

▶ Show solution

Choosing and ordering $3$ books from $5$:

${}^5P_3 = 5 \times 4 \times 3 = 60$

Question 3

A $4$-digit PIN uses the digits $0$–$9$ with no repeats. How many PINs are possible?

▶ Show solution

${}^{10}P_4 = 10 \times 9 \times 8 \times 7 = 5040$

Question 4

State whether each needs a permutation or a combination: (a) choosing $3$ pizza toppings, (b) choosing a captain and a vice-captain.

▶ Show solution

(a) Combination. Swapping two toppings gives the same pizza.

(b) Permutation. Swapping the two people changes who is captain.

Question 5

In how many ways can $6$ people be seated in a row of $6$ chairs?

▶ Show solution

${}^6P_6 = 6! = 720$

Question 6

Find the number of distinct arrangements of the letters of BANANA.

▶ Show solution

$6$ letters, with three As and two Ns.

$\dfrac{6!}{3!\,2!} = \dfrac{720}{6 \times 2} = 60$

Question 7

Three different medals are awarded among $12$ athletes. In how many ways, if a particular athlete must win the gold?

▶ Show solution

Gold is fixed: $1$ way.

Silver and bronze from the remaining $11$, in order: ${}^{11}P_2 = 11 \times 10 = 110$.

$110$ ways.

Question 8

Solve ${}^nP_2 = 56$.

▶ Show solution

${}^nP_2 = n(n-1) = 56$

$n^2 - n - 56 = 0$

$(n-8)(n+7) = 0$, so $n = 8$ or $n = -7$.

$n$ must be a positive whole number, so $n = 8$.

Question 9

Show that ${}^nP_r = r! \times {}^nC_r$, and explain in words what this means.

▶ Show solution

${}^nC_r = \dfrac{n!}{r!(n-r)!}$, so

$r! \times {}^nC_r = r! \times \dfrac{n!}{r!(n-r)!} = \dfrac{n!}{(n-r)!} = {}^nP_r$ ✓

In words: to make an ordered selection, first choose which $r$ objects (that is ${}^nC_r$ ways), then arrange them in order (that is $r!$ ways).

Equivalently, every combination corresponds to exactly $r!$ permutations.

Question 10

A code is made by arranging $4$ of the $7$ letters A, B, C, D, E, F, G, with no repeats.

(a) How many codes are possible? (b) How many begin with a vowel? (c) How many contain the letter A somewhere? (d) How many have A and B adjacent?

▶ Show solution

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

(b) The vowels available are A and E: $2$ choices for the first letter.

Then ${}^6P_3 = 6 \times 5 \times 4 = 120$ for the remaining three positions.

$2 \times 120 = 240$

(c) Count the complement: codes with no A use only the other $6$ letters.

${}^6P_4 = 6 \times 5 \times 4 \times 3 = 360$

Codes containing A $= 840 - 360 = 480$

(d) Treat AB as a block. The code has $4$ positions, so the block can start in position $1$, $2$ or $3$: that is $3$ placements.

The block can be AB or BA: $\times 2$.

The remaining $2$ positions are filled from the other $5$ letters, in order: ${}^5P_2 = 5 \times 4 = 20$.

$3 \times 2 \times 20 = 120$

Sense check: $120$ out of $840$ is about $1$ in $7$, which is plausible for such a specific requirement.

Permutations (EN4) · OCR FSMQ Additional Maths · Created with MathJax