Beyond STEP
Chapter
9

Counting and Chance

Counting is the oldest mathematics there is. Doing it cleverly is still one of the hardest.

Download the whole chapterPDF, typeset for print

In this chapter

  1. 9.1 Lines Cutting the Plane STEP II 1990 Worksheet
  2. 9.2 Ramsey's Theorem in Miniature STEP I 1989 Worksheet
  3. 9.3 Colouring Fence Posts STEP II 1995 Worksheet
  4. 9.4 Sequences as Functions STEP I 2016 Worksheet
  5. 9.5 Making Change STEP I 1997 Worksheet
  6. 9.6 Strange Dice STEP I 1993 Worksheet
  7. 9.7 Equal Sums of Powers STEP I 1992 Worksheet
  8. 9.8 Nobody Gets Their Own Shirt STEP II 2016 Worksheet
  9. 9.9 The Birthday Problem STEP II 2007 Worksheet
  10. 9.10 Always Able to Give Change STEP I 2011 Worksheet
  11. 9.11 Collecting the Set STEP II 1994 Worksheet
  12. 9.12 Random Subsets STEP III 2019 Worksheet
  13. 9.13 Loaded Dice STEP I 1999 Worksheet
  14. ✔ Looking back: what we have learned
Chapter 9 \(\cdot\) Introduction

The Art of Counting

Combinatorics is the slums of topology.

— J. H. C. Whitehead, in the 1950s. It is not a view anyone holds today.

Everyone can count. But ask how many ways there are to make £1 from coins, or to seat ten people so that nobody sits in their own place, or to colour a map with four colours, and simple counting quickly breaks down. There are too many cases to list, and the cases overlap. Combinatorics, the mathematics of counting and arrangement, is the art of organising such problems so that they can be solved without listing.

For a long time, combinatorics was regarded as a collection of clever tricks rather than a serious subject, as Whitehead’s remark suggests. That changed in the second half of the twentieth century, driven partly by computer science, where counting the steps an algorithm takes is a combinatorial problem, and partly by the discovery of deep connections with algebra, geometry and probability. Today it is one of the most active areas of mathematics. In 2022 June Huh was awarded a Fields Medal, the highest honour in mathematics, partly for proving a 1968 conjecture about the chromatic polynomials of Section 9.3, using ideas from algebraic geometry.

Why counting matters

Probability, in its simplest form, is counting: when all outcomes are equally likely, the probability of an event is the number of favourable outcomes divided by the total. So every question about cards, dice and lotteries is a counting problem, and the second half of this chapter is drawn from the probability papers for exactly this reason. But counting also matters well beyond games. Computer scientists count the operations an algorithm needs, and the ways it might fail. Chemists count the possible structures of molecules. Biologists count the ways a strand of DNA can fold. Cryptographers count the keys an attacker must try, and, as Section 9.9 shows, how many are needed before two of something coincide.

What you will meet at university

Most universities offer a first- or second-year course in combinatorics or discrete mathematics, and its themes are the themes of this chapter. You will learn the basic counting principles (the product rule, bijections, inclusion–exclusion, the pigeonhole principle), and how to set up and solve recurrence relations. You will meet generating functions, which turn sequences into functions and counting into algebra. You will study graphs, from colourings to Ramsey theory, and partially ordered sets such as the lattice of subsets. And probability courses will use the same tools, together with linearity of expectation, to analyse random structures. Further on, combinatorics connects with algebra (symmetric functions, representation theory), with number theory (partitions, additive combinatorics) and with computer science (the analysis of algorithms, complexity theory).

The questions that run through this chapter

Three big questions

  1. How do you count without listing? What structures (recurrences, bijections, generating functions) let you count huge collections exactly?

  2. When must something happen? When does size alone force a pattern, a coincidence or a match?

  3. How do counting and probability help each other? When is a probability best found by counting, and when is a count best found by probability?

The chapter has two halves. The first seven sections come from the pure papers. They begin with recurrences (lines cutting the plane, colouring fence posts) and the pigeonhole principle (Ramsey’s theorem), then develop generating functions and use them to count coins, design strange dice and split numbers into teams with equal power sums. The last six sections are classic counting problems from the probability papers: derangements and the appearance of \(1/e\), the birthday problem, the ballot problem and its reflection principle, the coupon collector, random subsets, and the impossibility of loading dice so that every total is equally likely.

Ideas in this chapter

§ Topic Idea
9.1 Regions of the plane What changes when you add one more
9.2 Ramsey theory The pigeonhole principle
9.3 Graph colouring Coupled recurrences; chromatic polynomials
9.4 Generating functions A sequence becomes a function
9.5 Partitions Counting via coefficients
9.6 Sicherman dice Factorising polynomials
9.7 Thue–Morse Repeated roots give balanced sums
9.8 Derangements Inclusion–exclusion; \(1/e\)
9.9 Coincidences Complements; the square-root law
9.10 The ballot problem The reflection principle
9.11 Coupon collector Linearity of expectation; \(n\ln n\)
9.12 Random subsets One element at a time
9.13 Loaded dice Impossibility by AM–GM

How to read this chapter

Always start with small cases. Draw three lines, list the six orders of three cards, count the ways to make \(5\)p. Small cases give you data to guess from, and they check your formulas at the end. But do not trust a pattern until you have a reason for it: Section 9.1 includes a famous sequence, \(1, 2, 4, 8, 16, \ldots\), whose next term is \(31\).