Revise Permutations and combinations for Cambridge 9709 (5.2)

Before diving into permutations and combinations, we must understand factorials. The factorial of a non-negative integer $n$, denoted by $n!$, is the product of all positive integers less than or equal to $n$. It represents the number of ways to arrange $n$ distinct items in a line.

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

A permutation is an arrangement of objects in a specific order. Think about situations where the sequence is important, such as creating a password, assigning roles like President and Vice-President, or determining the finishing order in a race. The notation $^n P_r$ represents the number of ways to arrange $r$ objects chosen from a set of $n$ distinct objects.

$\text{Number of permutations of } r \text{ objects from } n \text{ is } ^n P_r = \frac{n!}{(n-r)!}$

A combination is a selection of objects where the order of selection is irrelevant. Think about choosing a group of friends to go to the cinema, picking ingredients for a salad, or selecting a committee. The group {Alice, Bob, Charlie} is the same committee as {Charlie, Alice, Bob}. The notation $^n C_r$ (or $\binom{n}{r}$) represents the number of ways to choose $r$ objects from a set of $n$ distinct objects.

$\text{Number of combinations of } r \text{ objects from } n \text{ is } ^n C_r = \binom{n}{r} = \frac{n!}{(n-r)!r!}$

Notice that the combination formula is just the permutation formula divided by $r!$. This is because for any group of $r$ items, there are $r!$ ways to arrange them. Since order doesn't matter in combinations, we divide by $r!$ to eliminate these duplicate arrangements.

Many exam questions add layers of complexity, such as restrictions or repeated items. A common scenario involves arranging the letters of a word with repeated letters, like 'MISSISSIPPI'.

Arrangements of $n$ objects with repetitions: $\frac{n!}{p!q!r!...}$ where $p, q, r, ...$ are the frequencies of each repeated object.

For 'MISSISSIPPI', there are 11 letters total: one M, four I's, four S's, and two P's. The number of distinct arrangements is $\frac{11!}{1!4!4!2!}$. Another common problem involves items that must be together. For this, treat the grouped items as a single 'block' and arrange the blocks, then multiply by the internal arrangements of the block.