Counting and Permutations

In short: A permutation is an arrangement where order matters. Multiply the number of choices at each step, so $n$ different objects can be arranged in $n!$ ways and choosing $r$ of them in order gives $^{n} P_{r} = \frac{n !}{( n - r )!}$ . Deal with any restrictions first.

Starting point: what you already know

Listing outcomes in a table or tree diagram, from probability in Years 9 and 10.
Probability $= \frac{favourable outcomes}{total outcomes}$ when outcomes are equally likely.
Index notation, such as $1 0^{4} = 10 \times 10 \times 10 \times 10$ .

The multiplication principle

Addition principle: if you choose either one thing (in $m$ ways) or another (in $n$ ways), and they cannot both happen, there are $m + n$ ways. "And" means multiply, "or" means add.

Factorials

How many ways can 5 people stand in a line? The first spot has 5 choices, then 4, then 3, 2, 1:

$5 \times 4 \times 3 \times 2 \times 1 = 120$

This product is written $5!$ and read "5 factorial".

$n! = n \times (n - 1) \times \dots \times 2 \times 1, 0! = 1$

Factorials grow very fast: $10! = 3628800$ .

Permutations

A permutation is an arrangement where order matters. The number of ways to arrange $r$ objects chosen from $n$ different objects is

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

Arrangements with restrictions

Deal with the restriction first.

Repeated objects

If some objects are identical, swapping them does not make a new arrangement, so divide.

$arrangements = \frac{n !}{p ! q ! \dots}$

where $p$ , $q$ , ... count the repeats.

Counting and permutations

Principles

And means multiply
Or means add

Factorial

n! = n × (n - 1) × ... × 1
0! = 1

Permutations

Order matters
nPr = n!/(n - r)!

Restrictions

Do the restriction first
Together: make a block
Not together: total minus together

Repeats

Divide by p! q!

Circles

(n - 1)!

Year 11Arrangements in a circle

Around a round table there is no "first seat", so turning everyone one place gives the same seating. Fix one person and arrange the rest: $ways = (n - 1)!$ Example. 7 people at a round table: $6! = 720$ ways. If two particular people must sit together: block them, so 6 items in a circle, $5! \times 2! = 240$ .

Someone in the middle. For Ana to sit between Ben and Cal at a round table of 8, glue B, A, C into a block (2 orders, since only B and C can swap). Then 6 items around the circle: $5! \times 2 = 240$ .

Two tables. For 9 people at round tables of 5 and 4, first choose who sits at the table of 5, $(5 9)$ , then arrange each table: $(5 9) \times 4! \times 3! = 18144$ .

Alternating. 4 boys and 4 girls in a row, alternating: the row starts with a boy or a girl (2 ways), then $4!$ for the boys and $4!$ for the girls: $2 \times 4! \times 4! = 1152$ .

Apart, with repeated letters. In LETTER the T's are together in $\frac{5 !}{2 !} = 60$ arrangements (glue TT, the two E's still repeat). All arrangements: $\frac{6 !}{2 ! 2 !} = 180$ . So the T's are apart in 120.

Numbers with conditions. For 4-digit numbers above 7000 from the digits 1 to 9 without repeats, the first digit is 7, 8 or 9: $3 \times 8 \times 7 \times 6 = 1008$ .

Cases. When one rule does not cover everything, split into cases that do not overlap and add them. For example, count numbers whose repeated digit is the first digit, then those whose repeated digit is a different digit.

Every box used. To put 4 different objects into 3 different boxes with none empty, count all ways ( $3^{4} = 81$ ), subtract those missing a chosen box ( $3 \times 2^{4} = 48$ ), then add back those missing two boxes ( $3 \times 1 = 3$ ): $81 - 48 + 3 = 36$ .

Quick summary

Multiply the number of choices for each step. "And" multiplies, "or" adds.
$n! = n (n - 1) \dots 1$ and $0! = 1$ .
Order matters: $^{n} P_{r} = \frac{n !}{( n - r )!}$ .
Handle restrictions first. Use blocks for "together" and subtract for "not together".
Identical objects: divide by the factorial of each repeat count. Circles: $(n - 1)!$ .

Quiz

13 questions with instant marking. It is free, and your scores are saved to your account so you can carry on from any device.

Turn on JavaScript to sign in and take the quiz.

Try 3 questions now

A café offers 4 mains and 3 desserts. How many main and dessert meals are possible?
1. A 7
2. B 12
3. C 24
4. D 64
Show answer
B: 12
Multiply: $4 \times 3$ .
A 3 digit code uses digits 0 to 9, and digits can repeat. How many codes?
1. A 30
2. B 720
3. C 1000
4. D 999
Show answer
C: 1000
$10 \times 10 \times 10$ .
Evaluate $5!$ .
1. A 25
2. B 60
3. C 120
4. D 720
Show answer
C: 120
$5 \times 4 \times 3 \times 2 \times 1$ .

Starting point: what you already know

The multiplication principle

Factorials

Permutations

Arrangements with restrictions

Repeated objects

Quick summary

Quiz

Feedback on this chapter

Mathematics Extension 1 chapters