Counting Techniques

Lessons

Senior 6 · Basic Mathematics

Counting Techniques

5 lessons

Lesson 4 of 5

Permutations of r objects from n, and circular permutations

25 min

Filling only some of the places

A youth cooperative of 10 members must elect a president, a secretary and a treasurer, three different posts held by three different people. The president can be any of 10, the secretary any of the remaining 9, the treasurer any of the remaining 8: $10 \times 9 \times 8 = 720$ possible results. This is an arrangement of 3 people chosen from 10.

Definition

The number of permutations of $r$ objects chosen from $n$ different objects ( $0 \le r \le n$ ) is

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

Example: ${}^{10}P_{3} = \frac{10!}{7!} = 10 \times 9 \times 8 = 720$ . Note that ${}^{n}P_{n} = \frac{n!}{0!} = n!$ .

Why the formula is right. Multiplying $n(n-1)\cdots(n-r+1)$ by $(n - r)!$ completes the full product $n!$ . So $n(n-1)\cdots(n-r+1) = \frac{n!}{(n-r)!}$ .

Choosing from a mixture of alike and unlike objects

When some objects are identical, ${}^{n}P_{r}$ no longer applies directly. Split the count into cases by how many identical objects are used, count each case, and add (the cases are mutually exclusive).

Worked example

Worked example 1. How many 3-letter arrangements can be made from the letters of AKAGERA?

The letters are A (three times), K, G, E, R: five different letters, and only A is repeated.

Case	Count
all three letters different (from A, K, G, E, R)	${}^{5}P_{3} = 60$
two A's and one other letter (4 choices), arranged	$4 \times \frac{3!}{2!} = 12$
three A's	$1$
Total	$\mathbf{73}$

Arrangements in a circle

Four friends, A, B, C and D, sit at a round table. In a row there would be $4! = 24$ orders. Round a table, though, turning everyone one seat to the left changes nobody's neighbours. The four seatings below are the same circular arrangement:

Every circular arrangement of $n$ people appears $n$ times among the $n!$ row orders (once for each rotation), so the number of circular arrangements is $\frac{n!}{n} = (n-1)!$ . Another way to see it: fix one person's seat, then arrange the other $n - 1$ in a row.

Definition

Circular permutations. $n$ different objects can be arranged round a circle in $(n - 1)!$ ways, when only their order relative to each other matters.

If the circle can also be turned over, as with beads on a bracelet or keys on a ring, clockwise and anticlockwise orders are the same, and the number is $\frac{(n-1)!}{2}$ (for $n \ge 3$ ).

Example: 4 friends at a round table: $3! = 6$ ways.

Worked example

Worked example 2. Six delegates sit round a circular table. In how many ways can they sit (a) with no restriction; (b) if two delegates, Mutesi and Habimana, sit together; (c) if they do not sit together?

(a) $(6 - 1)! = 5! = 120$ .

(b) Treat Mutesi and Habimana as one block: 5 units round the table, $4! = 24$ ways; the pair can swap: $\times 2$ . Total $48$ .

Worked example

Worked example 3. Seven different beads are threaded on a bracelet. How many different bracelets are possible?

\frac{(7-1)!}{2} = \frac{720}{2} = 360

We divide by 2 because a bracelet can be turned over, so an arrangement and its mirror image are one bracelet.

Eddie Woo introduces circular arrangements: why rotating everyone gives the same seating, and why fixing one person's place leads to (n − 1)!.

Warning

Do not divide by 2 at a table. People at a round table are not like beads: turning the table over is not possible, and A having B on the right differs from A having B on the left. Use $(n - 1)!$ for tables and $\frac{(n-1)!}{2}$ only for things that can be flipped, like necklaces.

Tip

Calculator: most models have an ${}^{n}P_{r}$ key. Type 10, then nPr, then 3 to get 720. Use it to check, but show the formula in your working.

✦

Practice

Evaluate ${}^{8}P_{3}$ and ${}^{6}P_{6}$ .
Twelve runners finish a race. In how many ways can the gold, silver and bronze medals be awarded?
How many 4-digit numbers with different digits can be formed from 2, 3, 5, 7, 8, 9?
Solve for $n$ : ${}^{n}P_{2} = 56$ .
In how many ways can 8 people sit at a round table?
A key ring holds 5 different keys. How many arrangements are possible?
How many 2-letter arrangements can be made from the letters of BANANA? Show your cases.

Show answersHide answers

$8 \times 7 \times 6 = 336$ ; $6! = 720$ .
${}^{12}P_{3} = 12 \times 11 \times 10 = 1320$ .
${}^{6}P_{4} = 6 \times 5 \times 4 \times 3 = 360$ .
$n (n - 1) = 56$ , so $n = 8$ (the negative root is rejected).
$7! = 5040$ .
$\frac{4!}{2} = 12$ .
Letters B, A (3), N (2). Different letters: ${}^{3}P_{2} = 6$ . Two alike: AA or NN: 2. Total 8.

Important

${}^{n}P_{r} = \frac{n!}{(n-r)!}$ . Round a table: $(n - 1)!$ . On a necklace or ring: $\frac{(n-1)!}{2}$ . With identical objects, count case by case.

Sources and credits

Text, diagram, worked examples and exercises: Written by Ganzaa.

Video: Introduction to Circular Arrangements, Eddie Woo, embedded from YouTube.

1Filling only some of the places

2Choosing from a mixture of alike and unlike objects

3Arrangements in a circle

Filling only some of the places

Choosing from a mixture of alike and unlike objects

Arrangements in a circle