Counting and combinatorics
Introduced| English | Meaning |
|---|---|
| addition rule/əˈdɪʃn ruːl/ | addition rule |
| multiplication rule/ˌmʌltɪplɪˈkeɪʃn ruːl/ | multiplication rule |
| permutation/ˌpɜːmjuːˈteɪʃn/ | An ordered arrangement of selected objects, in which changing the order gives a different arrangement. |
| combination/ˌkɒmbɪˈneɪʃn/ | A selection of items in which their order is not significant. |
| inclusion–exclusion | inclusion–exclusion |
How long to guess a PIN?
- A phone PIN has 4 digits. A brute-force attack tries every PIN, so how many are there? And how many if no digit may repeat?
- Counting answers questions like this before any code runs: the size of a search space, the number of branches, the bound on a loop.
Two rules: add or multiply
- Addition rule 加法原理: if a choice is one option from A or one from B, with no overlap, the counts add. 5 buses or 3 trains give $5 + 3 = 8$ ways.
- Multiplication rule 乘法原理: if you choose from A and then from B, the counts multiply. 4 digits from 10 each give $10^4 = 10\,000$ PINs.
Match each situation to its count.
Difficulty 2/5 · 140 coins + a small bonus on first completion today
"Or" with no overlap adds; "and then" multiplies.
Order matters: permutations
- A permutation 排列 is an ordered selection. Choosing $r$ from $n$ in order: $n$ choices, then $n - 1$, … , $r$ factors, so $P(n, r) = \frac{n!}{(n-r)!}$.
- PINs with no repeated digit: $P(10, 4) = 10 \times 9 \times 8 \times 7 = 5040$.
How many 4-digit PINs use no digit twice?
Difficulty 2/5 · 140 coins + a small bonus on first completion today
Order matters and digits do not repeat, so $P(10, 4) = 10 \times 9 \times 8 \times 7 = 5040$.
Order ignored: combinations
- A combination 组合 is an unordered selection. Each set of $r$ appears $r!$ times among the permutations, so divide: $\binom{n}{r} = \frac{n!}{r!\,(n-r)!}$.
- A committee of 2 from 7: $P(7, 2) = 42$ ordered pairs, $\div\, 2! = 21$ committees. The division by $r!$ is the whole difference.
A team of 3 from 8 people, with one leader. Route 1: choose the team, $\binom{8}{3} = 56$, then the leader, 3 ways: $168$. Route 2: choose the leader, 8 ways, then 2 more from 7, $\binom{7}{2} = 21$: $168$ ✓. Two routes agreeing is the check.
How many committees of 3 can be chosen from 10 people?
Difficulty 2/5 · 140 coins + a small bonus on first completion today
$\binom{10}{3} = \frac{10 \times 9 \times 8}{3!} = \frac{720}{6} = 120$.
Choosing a gold, a silver and a bronze winner from 12 runners is counted with —
Difficulty 1/5 · 100 coins + a small bonus on first completion today
Swapping gold and silver gives a different result, so order matters; nobody can win twice, so the choices shrink.
Inclusion–exclusion
- Inclusion–exclusion 容斥原理: $|A \cup B| = |A| + |B| - |A \cap B|$. Adding counts the overlap twice, so subtract it once.
- Three sets: add the singles, subtract the pairs, add the triple back. The triple was added 3 times and subtracted 3 times, so it needs one more.
100 students: 45 like tea, 35 coffee, 30 cocoa; 12 tea and coffee, 10 tea and cocoa, 8 coffee and cocoa; 5 all three. At least one: $45 + 35 + 30 - 12 - 10 - 8 + 5 = 85$, so 15 like none.
In a class of 40, 22 study French, 18 study Spanish and 7 study both. How many study neither?
Difficulty 2/5 · 140 coins + a small bonus on first completion today
At least one is $22 + 18 - 7 = 33$, so $40 - 33 = 7$ study neither.
In three-set inclusion–exclusion, the triple intersection is subtracted at the end.
Difficulty 1/5 · 100 coins + a small bonus on first completion today
The singles add it 3 times and the pairs subtract it 3 times, so it must be added back once.
Marks that slip away
- Adding sequential choices. 4 routes then 3 vehicles is $4 \times 3$, not $4 + 3$.
- Permutations for a committee. If swapping two people gives the same group, order does not matter.
- Forgetting the triple. Three-set inclusion–exclusion ends with $+\,|A \cap B \cap C|$.
You've got it
- Disjoint alternatives add; sequential choices multiply.
- $P(n, r) = \frac{n!}{(n-r)!}$ ordered; $\binom{n}{r} = \frac{P(n, r)}{r!}$ unordered.
- Inclusion–exclusion: + singles − pairs + triple. Count two ways and compare.