Counting and probability

The product rule

If a choice is made in stages, with $m$ options at the first stage and $n$ at the second whatever happened first, there are $m \times n$ ways in all. A sandwich with 3 breads and 4 fillings can be made in $3 \times 4 = 12$ ways. The rule extends to any number of stages, and nearly every counting formula is built from it.

Order matters: permutations

Arranging $n$ different items in a row: $n$ choices for the first place, $n - 1$ for the second, and so on, giving

$$n! = n \times (n - 1) \times \cdots \times 2 \times 1.$$

Values to know: $3! = 6$, $4! = 24$, $5! = 120$, $6! = 720$.

Filling only $r$ ordered places from $n$ items gives $n \times (n - 1) \times \cdots$ with $r$ factors. Electing a president, a secretary and a treasurer from 7 people: $7 \times 6 \times 5 = 210$ ways. If repetition is allowed, each place has all $n$ options: a 3-digit code using the digits 1 to 5 with repeats allowed has $5^3 = 125$ possibilities.

Order does not matter: combinations

Choosing a committee of 3 from 7 people, where the three seats are identical, counts each group once rather than once per ordering. Each group of 3 can be ordered in $3! = 6$ ways, so

$$\binom{7}{3} = \frac{7 \times 6 \times 5}{3 \times 2 \times 1} = \frac{210}{6} = 35.$$

In general, $\binom{n}{r} = \frac{n!}{r!\,(n - r)!}$, and choosing $r$ to take is the same as choosing $n - r$ to leave: $\binom{10}{8} = \binom{10}{2} = 45$. Useful values: $\binom{5}{2} = 10$, $\binom{6}{2} = 15$, $\binom{8}{2} = 28$, $\binom{10}{3} = 120$.

The deciding question is whether swapping two chosen items gives a different outcome. Different roles, positions or a code: order matters. A team, a hand of cards, a set of books to take: it does not.

Probability as counting

When every outcome is equally likely,

$$P(\text{event}) = \frac{\text{number of favourable outcomes}}{\text{total number of outcomes}}.$$

Count the top and the bottom the same way: both ordered or both unordered. A probability always lies between 0 and 1; an answer outside that range signals an error.

With two dice, the 36 ordered pairs are the equally likely outcomes, not the 11 possible sums. A sum of 7 arises in 6 ways, so it has probability $\frac{6}{36} = \frac{1}{6}$, while a sum of 2 arises only as $(1, 1)$.

Rules for combining events

• Complement: $P(\text{not } A) = 1 - P(A)$. "At least one" is almost always easiest as $1 - P(\text{none})$.
• And, for independent events: multiply. Two fair coin tosses both landing heads: $\frac{1}{2} \times \frac{1}{2} = \frac{1}{4}$.
• Or: $P(A \text{ or } B) = P(A) + P(B) - P(A \text{ and } B)$. Subtract the overlap, which would otherwise be counted twice. If the events cannot both happen, the overlap is 0 and you simply add.

For a number chosen at random from 1 to 20, the multiples of 2 are 10 numbers and the multiples of 5 are 4 numbers (5, 10, 15, 20). The multiples of both, 10 and 20, are counted in each list, so there are $10 + 4 - 2 = 12$ numbers that are multiples of 2 or 5, and the probability is $\frac{12}{20} = \frac{3}{5}$.

Without replacement

When items are drawn and not put back, later draws depend on earlier ones. From a bag of 5 red and 3 blue balls, two drawn without replacement are both red with probability

$$\frac{5}{8} \times \frac{4}{7} = \frac{20}{56} = \frac{5}{14},$$

because after one red is gone, 4 of the remaining 7 are red. Counting gives the same answer: $\frac{\binom{5}{2}}{\binom{8}{2}} = \frac{10}{28} = \frac{5}{14}$. Using $\frac{5}{8} \times \frac{5}{8}$ would treat the draws as if the ball were put back.