We began by saying that counting is the oldest mathematics there is, and that doing it cleverly is still one of the hardest. We asked three questions: how do you count without listing, when must something happen, and how do counting and probability help each other? Here is what the chapter’s thirteen questions showed.
1. How do you count without listing?
The chapter built up a toolkit.
Recurrences. Adding one line to the plane (Section 9.1) or one post to a fence (Section 9.3) changed the count in a simple way, giving a recurrence that could be solved. Recording a little extra information, the colour of the last post, made the recurrences close up.
Generating functions. Packaging a sequence as a power series turned recurrences into algebra (Section 9.4), explained why \(1/89 = 0.01123\ldots\), and turned counting combinations into multiplying polynomials: coins in Section 9.5, dice in Section 9.6, and balanced power sums in Section 9.7, where a repeated root at \(x = 1\) did all the work.
Bijections. The reflection principle (Section 9.10) counted bad queues by matching them with unrestricted paths, and complements of random sets turned subsets into disjoint pairs (Section 9.12).
Inclusion–exclusion. Overcounting and correcting found the number of derangements (Section 9.8).
Double counting. Counting regions with Euler’s formula (Section 9.1) and pairs of subsets by sizes (Section 9.12) gave the same answers by different routes, and proved identities on the way.
2. When must something happen?
Several sections showed that size alone forces structure. Among six people there must be three mutual friends or three mutual strangers (Section 9.2), by the pigeonhole principle, though five people are not enough. Twenty-three people make a shared birthday more likely than not (Section 9.9), because the number of pairs grows like the square of the number of people. Random subsets of a large set almost always overlap (Section 9.12). And some things cannot happen, however you try: no loading of two dice makes every total equally likely (Section 9.13), and no numbering of dice other than Sicherman’s reproduces the ordinary totals (Section 9.6).
3. How do counting and probability help each other?
In the second half of the chapter, probabilities were found by counting: derangements by inclusion–exclusion, the birthday problem by a product, the ballot problem by reflection. But the traffic went the other way too. Linearity of expectation gave the coupon collector’s \(nH_n\) (Section 9.11) and the expected number of matches in a shuffle without any counting at all. Thinking of a random subset as \(n\) coin tosses (Section 9.12) turned counts like \(3^n\) and \((m + 1)^n\) into one-line calculations. And Erdős’s probabilistic method (Section 9.2) proved that good colourings exist by showing that a random colouring works with positive probability. Two constants appeared from nowhere: \(e\), in the limiting chance of a derangement, and Euler’s \(\gamma\), in the cost of completing a collection.
4. A toolkit for counting
| Method | Where you used it |
|---|---|
| What changes when you add one | Lines (9.1); fence posts (9.3) |
| Pigeonhole principle | Ramsey (9.2) |
| Coupled recurrences | Fence posts (9.3) |
| Generating functions | 9.4, 9.5, 9.6, 9.7, 9.13 |
| Case analysis from the extremes | Strange dice (9.6); loaded dice (9.13) |
| Inclusion–exclusion | Derangements (9.8) |
| Complement and exponential approximation | Birthdays (9.9) |
| Reflection principle | Ballot problem (9.10) |
| Linearity of expectation | Coupons (9.11); matches (9.8) |
| One element at a time | Random subsets (9.12) |
| Contradiction with AM–GM | Loaded dice (9.13) |
Where next
The Poisson limit of derangements returns in Section 12.11, and generating functions of random variables drive the study of family trees in Section 12.15.
Coupled recurrences become Markov chains in Section 12.16.
The Gumbel distribution of the coupon collector describes the largest of many random quantities in Section 12.25.
Miklós Bóna, A Walk Through Combinatorics: a friendly first course covering almost every idea in this chapter.
Herbert Wilf, generatingfunctionology: the classic on generating functions; free online.
Ronald Graham, Donald Knuth & Oren Patashnik, Concrete Mathematics: sums, recurrences and generating functions, with wit and many exercises.
Geoffrey Grimmett & Dominic Welsh, Probability: An Introduction: the counting side of first-year probability.
Whitehead called combinatorics “the slums of topology”. This chapter has tried to show why nobody would say that now. Behind every clever count there was an idea that reaches far beyond it: a generating function, a bijection, a recurrence, an inequality. Those ideas connect counting with algebra, analysis and probability, and learning to look for them, rather than for one more trick, is what turns counting into mathematics.