Statistics › Section N · Counting, Bayesian inference, and multiple regression › Topic N.1
Counting, permutations, and combinations
The counting formula from the binomial chapter was borrowed without proof; this is its home. With replacement, without replacement, order or not - a few systematic rules count outcomes too many to list, and with equally likely outcomes, counting IS probability.
Why count?
The probability chapter's equally-likely formula needs the number of outcomes, and real sample spaces are too big to list: thousands of lottery tickets, millions of PINs. Systematic counting replaces listing: a few rules multiply and divide their way to exact totals, and with equally likely outcomes, \(P(A)\) becomes favourable count over total count. Counting is the binomial chapter's \(\binom{n}{k}\) finally given its derivation, and the tool behind several famous surprises.
The multiplication principle
If a first choice can be made in \(m\) ways and, after it, a second in \(n\) ways, the pair can be made in \(m \times n\) ways - and the rule extends through any number of stages. A menu of 3 starters, 5 mains and 4 desserts offers \(3 \times 5 \times 4 = 60\) meals. A 4-digit PIN has \(10 \times 10 \times 10 \times 10 = 10{,}000\) possibilities - digits repeat because each stage is a fresh choice with all options available (sampling WITH replacement). A tree diagram of a multi-stage process is this principle drawn as branches.
Factorials: counting arrangements
The number of ways to arrange \(n\) distinct objects in order is
- \(n\) choices for the first slot, \(n-1\) for the second, and so on, all multiplied. Five books arrange on a shelf in \(5! = 120\) ways. The convention \(0! = 1\) makes the formulas work for empty selections (there is exactly one way to arrange nothing). Factorials grow ferociously: \(10! = 3{,}628{,}800\), and 20! already exceeds a quintillion.
Permutations: ordered selections
Choosing \(r\) of \(n\) objects where ORDER MATTERS: the first pick has \(n\) options, the next \(n-1\), down to the \(r\)-th's \(n-r+1\):
Awarding gold, silver and bronze among 8 runners: \(8 \times 7 \times 6 = 336\) podium orders - the same three runners can finish in 6 different orders, and each order is a different outcome. Without replacement: every choice removes an option, which is why the counts shrink.
Combinations: unordered selections
When order does NOT matter, divide out the \(r!\) orderings each unordered group was counted under:
A committee of 3 from 8 people: \(\binom{8}{3} = 56\) - whereas 336 would count the same committee 3! = 6 times under different internal orderings. The binomial formula's "arrangements factor" from section D is exactly this expression, now derived: choosing which \(r\) trials succeed is an unordered selection from \(n\).
The key question: does order matter?
Every counting problem begins with one question: does the order of selection change the outcome? Podiums, sequences, passwords: yes - permutations. Committees, hands of cards, lottery numbers: no - combinations. The test is simple: take one outcome and reorder it - if the result is a different outcome, order matters; if it is the same outcome counted twice, it does not. Misreading this single question accounts for most counting errors, and no formula rescues a wrong classification.
Worked example: lottery odds
A lottery draws 6 numbers from 49, order irrelevant: \(\binom{49}{6}\) possible tickets. 1. \(\binom{49}{6} = \frac{49!}{6! \times 43!} = 13{,}983{,}816\). 2. One ticket's winning chance: \(1/13{,}983{,}816\) - about 1 in 14 million. 3. Check the scale: buying 100 tickets a week, a player expects a win roughly once per 2,700 years. Counting is how such astonishingly small probabilities stay honest - no other tool prices them so plainly.
Worked example: probability from counting
With equally likely outcomes, probability is favourable over total: the heart of the counting-probability partnership. A 5-card poker hand being all hearts: \(\frac{\binom{13}{5}}{\binom{52}{5}} = \frac{1287}{2{,}598{,}960} \approx 0.0005\) - about 1 in 2,000, and five cards all of one suit, whichever suit, is 4 times likelier. The numerator counts favourable hands (choose 5 of the 13 hearts), the denominator all hands (choose 5 of 52 cards), and both are combinations because card order in a hand is irrelevant.
The birthday surprise
In a room of 23 people, the probability that at least two share a birthday exceeds 50%. The complement counts the other case - all birthdays distinct: \(\frac{365}{365} \times \frac{364}{365} \times \cdots \times \frac{343}{365} \approx 0.49\), so the chance of a match is about 0.51. Intuition fails because it imagines ONE comparison, while 23 people form \(\binom{23}{2} = 253\) pairs, each pair a chance for a match. The birthday problem is counting's most famous ambush - and a reminder that "how many chances?" often matters more than "how likely is one chance?".
Common mistakes to avoid
First, permuting what should be combined, or combining what should be permuted - the order question first, always. Second, forgetting \(0! = 1\) and breaking an otherwise correct formula. Third, double-counting: unordered groups counted under multiple orderings. Fourth, treating with-replacement and without-replacement as the same - PIN digits repeat, committee members do not. Fifth, adding where stages multiply: 3 starters AND 5 mains give 15 meals, not 8. Sixth, trusting small-sample intuition against birthday-scale counts - 253 pairs beat one pair's "obvious" rarity.
Key takeaways
Stages multiply: \(m\) then \(n\) gives \(mn\) (PINs: \(10^4\) with replacement). Arrangements of \(n\): \(n!\), with \(0! = 1\). Ordered selections of \(r\) from \(n\): \(P(n,r) = n!/(n-r)!\) (podiums: 336). Unordered: \(\binom{n}{r} = n!/[r!(n-r)!]\) (committees: 56) - the binomial chapter's factor, derived. Counting plus equally-likely gives probability: the lottery's \(\binom{49}{6} = 13{,}983{,}816\), about 1 in 14 million; poker's heart flush \(\approx 0.0005\); the birthday problem's 23 people and 253 pairs passing 50%. Ask "order?" first - the formulas follow the answer.
Flashcards
Flashcard
m ways then n ways: mn ways
Test your understanding
Question 1 of 5
How many ways can a president, vice president and treasurer be chosen from 10 people (distinct roles)?
Question 2 of 5
A committee of 3 is chosen from 8 people (no roles). How many committees?
Question 3 of 5
A 4-digit PIN (digits may repeat) has how many possibilities?
Question 4 of 5
A lottery draws 6 of 49 numbers, order irrelevant. One ticket's winning chance is about:
Question 5 of 5
Why does the birthday problem exceed 50% with only 23 people?
