The Fundamental Counting Principle
When you build a
sample space for
two things happening together, counting the outcomes one by one is slow. The
fundamental counting principle gives the total straight away: if one choice can
be made in m ways and a second, independent choice in
n ways, then the two together can be made in
m \times n \text{ ways.}
Two shirts and three pairs of trousers make 2 \times 3 = 6 outfits.
The principle chains on for more stages: just keep multiplying the number of ways at each step.
Why it works: branches of a tree
A tree diagram shows the reason. Each choice splits every branch into more branches, so the
leaves multiply. Step through it: two shirts, each with two bottoms, gives four
complete outfits at the tips.
Repetition, and arrangements
Each stage just needs its own count of options. A 4-digit PIN, where
every digit can be 0–9 with repetition
allowed, has
10 \times 10 \times 10 \times 10 = 10^4 = 10\,000 \text{ PINs.}
When items cannot repeat, the count shrinks at each stage. Arranging
5 different books in a row uses
5 for the first slot, then 4 left, then
3, and so on:
5 \times 4 \times 3 \times 2 \times 1 = 120.
- independent choices multiply:
m \times n \times \dots ways in total;
- with repetition allowed, each of k stages has
the same count s, giving s^k;
- without repetition, the count drops by one each stage
(n, n-1, n-2, \dots);
- arranging all n distinct items in order gives
n! = n \times (n-1) \times \dots \times 1.