Counting

Almost every counting question reduces to one decision: does the order matter? Permutation if it does, combination if it does not. Getting that right is most of the work.

The multiplication principle

If one task can be done in $m$ ways and a second, independently, in $n$ ways, the pair can be done in $m \times n$ ways.

Three shirts and four pairs of trousers give $3 \times 4 = 12$ outfits. A four-digit PIN with digits 0–9 repeatable gives $10^4 = 10\,000$ possibilities.

Permutations

A permutation is an arrangement, and order matters.

$n$ distinct objects arrange in $n!$ ways:

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

So the letters of MATHS, all distinct, arrange in $120$ ways.

Arranging $r$ objects chosen from $n$:

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

$$^5P_3 = \frac{5!}{2!} = \frac{120}{2} = 60$$

— the number of ways of filling 1st, 2nd and 3rd place from five runners.

Repeated objects

Divide by the factorial of each repeat count. LETTER has 6 letters with two E's and two T's:

$$\frac{6!}{2!\,2!} = \frac{720}{4} = 180$$

Circular arrangements

Around a table only the relative order matters, so one person's position is fixed and the rest arranged:

$$(n-1)!$$

Five people at a round table: $4! = 24$ ways.

Combinations

A combination is a selection, and order does not matter.

$$^nC_r = \binom{n}{r} = \frac{n!}{r!(n-r)!}$$

$$\binom{5}{3} = 10 \qquad \binom{8}{3} = 56 \qquad \binom{7}{2} = 21$$

A committee of 3 chosen from 8 people can be formed in $\binom83 = 56$ ways — the committee $\{A,B,C\}$ is the same committee however it is listed.

Selecting from several groups

Multiply the separate choices. Two men from five and one woman from four:

$$\binom52 \times \binom41 = 10 \times 4 = 40$$

Arrangements with restrictions

Two particular people must sit together. Treat the pair as a single block, arrange the blocks, then arrange within the block.

Five people in a row with two of them together:

$$4! \times 2! = 24 \times 2 = 48$$

(four items to arrange — the block plus three individuals — and two orders inside the block).

Two particular people must not sit together. Count the total and subtract:

$$5! - 48 = 120 - 48 = 72$$

Probability

For equally likely outcomes:

$$P(A) = \frac{\text{favourable outcomes}}{\text{total outcomes}}$$

The rules:

$$P(A') = 1 - P(A)$$ $$P(A \cup B) = P(A) + P(B) - P(A \cap B)$$

The subtraction removes the overlap, which would otherwise be counted twice.

Mutually exclusive events cannot both happen, so $P(A \cap B) = 0$ and the addition rule simplifies to $P(A)+P(B)$.

Independent events do not affect each other:

$$P(A \cap B) = P(A) \times P(B)$$

Without replacement

A bag holds 3 red and 5 blue balls. Two are drawn without replacement. Find $P$(both red).

$$P = \frac38 \times \frac27 = \frac{6}{56} = \frac{3}{28}$$

The second fraction has changed: one red has gone, and the total is down to 7.

And $P$(one of each colour)?

Red then blue, or blue then red:

$$\frac38 \times \frac57 + \frac58 \times \frac37 = \frac{15}{56} + \frac{15}{56} = \frac{30}{56} = \frac{15}{28}$$

Conditional probability

$$P(A \mid B) = \frac{P(A \cap B)}{P(B)}$$

read as "the probability of $A$ given that $B$ has happened". Restricting attention to the outcomes where $B$ occurred is exactly what the denominator does.

If $P(A) = 0.6$, $P(B) = 0.5$ and $P(A \cap B) = 0.3$, find $P(A\mid B)$.

$$P(A\mid B) = \frac{0.3}{0.5} = 0.6$$

Since $P(A\mid B) = P(A)$, knowing $B$ tells us nothing about $A$ — the events are independent. Confirming it the other way: $P(A)P(B) = 0.6 \times 0.5 = 0.3 = P(A\cap B)$ ✓