Counting and Permutations

Starting point: what you already know

• Listing outcomes in a table or tree diagram, from probability in Years 9 and 10.
• Probability $=\frac{\text{favourable outcomes}}{\text{total outcomes}}$ when outcomes are equally likely.
• Index notation, such as $10^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 \cdots \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)\cdots (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.

$$\text{arrangements}=\frac{n!}{p!q!\cdots }$$

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

Quick summary

• Multiply the number of choices for each step. "And" multiplies, "or" adds.
• $n!=n(n-1)\cdots 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