Appearance
7.1 — Counting Without Counting
A pizza place offers 12 toppings. How many different three-topping pizzas are possible? You could list them, and it would take a while and you would probably miss some or double-count. There are 220, and getting that number takes about five seconds once you know how.
Probability is, at bottom, counting: the chance of something is the number of ways it can happen divided by the number of things that could happen. So before probability comes combinatorics, the art of counting large collections without listing them.
1. The multiplication principle
If one choice can be made in m ways and an independent second choice in n ways, the pair can be made in m \times n ways.
Three shirts and four trousers give twelve outfits. Chain more choices and you keep multiplying.
Worked example. A number plate has 2 letters then 4 digits. Letters: 26 each. Digits: 10 each.
26 \times 26 \times 10^4 = 6{,}760{,}000
Worked example. An 8-character password using the 95 printable characters:
95^8 \approx 6.6\times10^{15}
At a billion guesses per second that is about 77 days. Add two more characters and it becomes 95^{10} \approx 6\times10^{19} — about 1,900 years. Each extra character multiplies the difficulty by 95, which is why length beats complexity in password advice. Volume I, 8.4.1 covers the security side, including why real attacks do not guess uniformly.
Worked example: subsets. A set of n things has 2^n subsets, because each element independently is either in or out — n binary choices. A menu with 12 optional toppings has 2^{12} = 4096 possible pizzas if any number of toppings is allowed.
2. Permutations: order matters
A permutation is an arrangement where the order counts.
Arranging all n objects. The first position has n choices, the second n-1, and so on:
n! = n\times(n-1)\times\cdots\times2\times1
This is the factorial. 5! = 120, 10! = 3{,}628{,}800.
And 0! = 1, which surprises people. There is exactly one way to arrange nothing — do nothing — and the definition also keeps every formula below working without special cases. It is the same kind of forced convention as a^0 = 1 in Chapter 1.4.
Factorials grow terrifyingly fast. 20! \approx 2.4\times10^{18}; 52! \approx 8\times10^{67}, which is more than the number of atoms in our galaxy. Every time you shuffle a deck properly, you almost certainly produce an ordering that has never occurred in the history of the world. That is not a figure of speech — the number of shuffles ever performed by humans is vanishingly small against 52!.
Arranging r objects from n:
P(n,r) = \frac{n!}{(n-r)!}
Choosing gold, silver and bronze from 8 runners: \frac{8!}{5!} = 8\times7\times6 = 336.
With repeated objects, divide by the repeats. The word MISSISSIPPI has 11 letters with 4 S's, 4 I's and 2 P's:
\frac{11!}{4!\,4!\,2!} = 34{,}650
The division removes the arrangements that are identical because you swapped two indistinguishable letters.
3. Combinations: order does not matter
A combination is a selection where order is irrelevant. Choosing Alice, Bob and Carol for a committee is the same committee however you name them.
\binom{n}{r} = \frac{n!}{r!\,(n-r)!}
Read \binom{n}{r} as "n choose r".
The reasoning: first count the ordered selections, P(n,r), then divide by r! because each unordered group was counted once for every way of ordering it.
The pizza problem. Three toppings from twelve:
\binom{12}{3} = \frac{12\times11\times10}{3\times2\times1} = 220
Two properties worth knowing.
\binom{n}{r} = \binom{n}{n-r}
Choosing 3 from 12 to include is the same as choosing 9 to exclude. Use it to make arithmetic easier: \binom{100}{98} = \binom{100}{2} = 4950.
\binom{n}{r} = \binom{n-1}{r-1}+\binom{n-1}{r}
Focus on one particular item. Either it is in your selection (then choose r-1 from the remaining n-1) or it is not (choose all r from the other n-1). Those cases do not overlap and cover everything.
That identity is Pascal's triangle, where each entry is the sum of the two above it.
The lottery. Choosing 6 numbers from 49:
\binom{49}{6} = 13{,}983{,}816
One ticket has about a one in fourteen million chance. To make that concrete: if you buy one ticket a week you should expect to win roughly once every 269,000 years. You are considerably more likely to be struck by lightning this year.
4. The binomial theorem
(a+b)^n = \sum_{r=0}^{n}\binom{n}{r}a^{n-r}b^r
(a+b)^3 = a^3 + 3a^2b + 3ab^2 + b^3
Why the coefficients are combinations. Expanding (a+b)^3 means picking either a or b from each of three brackets and multiplying. The term a^2b arises from every way of choosing which one bracket contributes the b — and there are \binom{3}{1} = 3 such ways.
So Pascal's triangle and the binomial expansion of Chapter 2.1 are the same object, and the coefficients are called binomial coefficients for this reason.
5. Counting problems that need care
The pigeonhole principle. If n+1 items go into n boxes, some box holds at least two. Trivially true, and surprisingly powerful.
Application: at least two people in London have exactly the same number of hairs on their head. A human head has fewer than about 200,000 hairs; London has nearly 9 million people; so by the pigeonhole principle, many share a count.
Application in computing: a hash function mapping arbitrary inputs to 256-bit outputs must have collisions, because there are more possible inputs than outputs. The security claim is not that collisions do not exist but that finding one is infeasible. Volume I, 8.2.
Inclusion–exclusion. To count things in A or B:
|A\cup B| = |A| + |B| - |A\cap B|
Add both, then subtract the overlap you counted twice. For three sets you add the singles, subtract the pairs, and add back the triple.
Worked example. Of 100 students, 60 study maths, 45 study physics, 25 study both. How many study neither?
Studying at least one: 60+45-25 = 80. Neither: 20.
The birthday problem
How many people must be in a room before there is a better than even chance that two share a birthday?
Most people guess around 180. The answer is 23.
Compute the probability that everyone is different, which is easier. The second person must avoid one date, the third must avoid two, and so on:
P(\text{all different}) = \frac{365}{365}\times\frac{364}{365}\times\cdots\times\frac{343}{365} \approx 0.493
So the chance of a shared birthday is about 0.507 — just over half.
Why intuition fails: you instinctively ask about your own birthday matching someone's, which is 23 comparisons. The actual question is about any pair matching, and 23 people make \binom{23}{2} = 253 pairs. The number of pairs grows with the square of the group.
With 50 people the probability is 97%; with 70 it is 99.9%.
This is not a party trick. In cryptography it is the birthday attack: finding some collision in an n-bit hash takes about 2^{n/2} attempts, not 2^n. A 128-bit hash gives only 64 bits of collision resistance, which is why modern systems use 256 bits.
Every formula above, built from scratch
None of the results in this chapter are worth memorising, because each one can be rebuilt in under a minute from something simpler. What follows is that rebuilding, one result at a time, so the formula and the reason for it sit on the same page as the explanation that needed them.
Counting
Everything starts with the multiplication principle: if one choice can be made in m ways and an independent second choice in n ways, the pair can be made in mn ways. Every formula below is that sentence applied carefully.
Permutations — order matters
P(n,r) = \frac{n!}{(n-r)!}
Where it comes from. Filling r ordered positions from n items: the first position has n choices, the second n-1 (one item is used up), and so on down to n-r+1 for the last. Multiply:
n(n-1)(n-2)\cdots(n-r+1)
That product is n! with the bottom (n-r) factors removed, which is exactly \frac{n!}{(n-r)!}. The factorial in the denominator is a cancellation device, not a new idea.
n! = n(n-1)\cdots 2\cdot 1, \qquad 0! = 1
Why 0! = 1. There is exactly one way to arrange nothing: do nothing. And the formula n! = n\times(n-1)! at n=1 forces 1 = 1\times 0!.
Combinations — order does not matter
\binom nr = \frac{n!}{r!(n-r)!}
Where it comes from. Count the ordered selections, then divide out the orderings you did not want. Each unordered group of r items can be written in r! different orders, and P(n,r) counted every one of them. So
\binom nr = \frac{P(n,r)}{r!} = \frac{n!}{r!(n-r)!}
The symmetry. \binom nr = \binom{n}{n-r}, because choosing which r to take is the same act as choosing which n-r to leave.
The rest of the counting toolkit
\text{Arrangements with repeats}: \frac{n!}{n_1!n_2!\cdots n_k!}
For MISSISSIPPI: 11 letters with 4 S's, 4 I's, 2 P's, giving \frac{11!}{4!4!2!} = 34{,}650. Divide by the factorial of each repeated group, because swapping two identical letters produces the same word.
\text{Choosing } r \text{ from } n \text{ types, repeats allowed}: \binom{n+r-1}{r}
Where this one comes from — the stars and bars picture. To choose 3 scoops from 5 flavours, draw 3 stars and 4 dividing bars, then read the stars between bars as the counts. Every arrangement of 3 stars and 4 bars is one selection, and there are \binom{3+4}{3} = 35 arrangements.
\text{Inclusion–exclusion}: |A\cup B| = |A|+|B|-|A\cap B|
|A\cup B\cup C| = |A|+|B|+|C|-|A\cap B|-|B\cap C|-|A\cap C|+|A\cap B\cap C|
Add the singles, subtract the doubles, add the triples. Anything counted twice must be removed once; anything removed too often must be put back.
6. Where this shows up in your life
Every password strength estimate. The multiplication principle.
Every lottery, card game and dice game. Combinations, and the reason the house edge is computable.
Every A/B test design. How many combinations of variants must be tested.
Every hash function's collision resistance. Pigeonhole and the birthday bound.
Every scheduling or seating problem. Permutations with constraints.
Every "how many possible..." question in an engineering estimate — configurations, states, test cases, routes. Volume I, 10.12 uses this style of counting for capacity planning.
Counting the possibilities is the first half. Assigning them likelihoods is the second, and that is probability proper.