Part VII · Chance & data Chapter 45 of 60
Combinatorics
A board-game evening: dice, cards, counters, hats and guests. We’ll learn to count possibilities without listing them, and see that in a large enough crowd some order appears all by itself.
Builds on: 44 · The zeta function and elliptic curves
You will learn
- count possibilities with the rules of sum and product without listing them
- tell permutations, arrangements and combinations apart and count them with formulas
- expand a power of a binomial and share identical objects between people
- prove with the pigeonhole principle that the coincidence you need is bound to occur
The last chapter ended with a question about three dice. Let’s start there: the science of chance itself began with problems about dice. Around 1620 Galileo Galilei wrote a short note on how the points fall on three dice. The question is said to have been put to him by his patron, the Grand Duke of Tuscany. Players who threw three dice had noticed something odd: a total of $10$ comes up more often than $9$. And yet both totals can be made in six ways.
Check for yourself. Nine: $1 + 2 + 6$, $1 + 3 + 5$, $1 + 4 + 4$, $2 + 2 + 5$, $2 + 3 + 4$, $3 + 3 + 3$. Ten: $1 + 3 + 6$, $1 + 4 + 5$, $2 + 2 + 6$, $2 + 3 + 5$, $2 + 4 + 4$, $3 + 3 + 4$. Six and six. Where does the advantage come from?
This chapter is set out like a board-game evening. Each table has its own game: dice, seating the guests, dealing cards, counters, hats in the cloakroom. And at every table the same question: how many possibilities are there in all? Listing them is usually impossible, as there are millions. We’ll learn to count without going through them one by one.
The Grand Duke’s dice
Galileo noticed what the players had missed: dice are distinguishable even if they look identical. Paint them in your mind in three colours, red, blue and green. Then “$1 + 2 + 6$” isn’t one outcome but six: the one can be on any of the three dice, the two on either of the remaining two, the six on the last. That’s $3 \cdot 2 \cdot 1 = 6$ ways in all. But “$1 + 4 + 4$” comes up in only three ways: all that matters is which die shows the one. “$3 + 3 + 3$” comes up in just one.
Let’s add up honestly. Nine has $6 + 6 + 3 + 3 + 6 + 1 = 25$ outcomes, ten has $6 + 6 + 3 + 6 + 3 + 3 = 27$. Three dice have $6 \cdot 6 \cdot 6 = 216$ outcomes in all, and they’re all equally likely. So ten comes up in $27$ cases out of $216$, nine in $25$. A difference of two outcomes, under one per cent, but over hundreds of evenings at the gaming table the players felt it.
The mistake of “counting partitions instead of outcomes” long outlived Galileo. According to a well-known story, Leibniz thought that with two dice the totals $11$ and $12$ come up equally often: each, he said, can be made in only one way, $5 + 6$ and $6 + 6$. In fact eleven has two outcomes, $(5, 6)$ and $(6, 5)$, and twelve has one.
Two rules
The whole chapter rests on two rules we’ve already used without naming them: the rule of sum and the rule of product.
If you can choose either one of $m$ options or one of $n$ other options, and the two groups have no options in common, there are $m + n$ options in all.
Number the options of the first group from $1$ to $m$, and those of the second from $m + 1$ to $m + n$. Since there are no options in common, each option gets exactly one number, and each number from $1$ to $m + n$ goes to exactly one option. So there are as many options as numbers: $m + n$. If the groups had an option in common, it would get two numbers and be counted twice; that’s why the condition “no options in common” is essential.
Suppose a choice is made in $k$ steps: at the first step there are $n_1$ options, at the second $n_2$ options for any choice at the first, at the third $n_3$ for any choices at the first two, and so on. Then there are $n_1 \cdot n_2 \cdots n_k$ options in all.
Draw the choice as a tree. From the root come $n_1$ branches, the options of the first step. In the picture the first step is choosing one of three games, $n_1 = 3$.
From the end of each branch come $n_2$ new branches, the options of the second step. This is where the condition of the rule works: their number is the same whichever branch of the first step we chose. Each game comes with four kinds of biscuit, $n_2 = 4$.
A complete choice is a path from the root to a leaf, and different choices correspond to different leaves. The leaves are split into $n_1$ groups with $n_2$ leaves each. Adding the groups by the rule of sum, we get $n_2 + n_2 + \ldots + n_2 = n_1 \cdot n_2$ leaves. In the picture $3 \cdot 4 = 12$.
If there are more steps, we attach $n_3$ new branches to each leaf (here, three kinds of juice), and the number of leaves is multiplied again: $n_1 n_2 \cdot n_3$. Each further step multiplies the number of leaves by its number of options, so after $k$ steps there are $n_1 \cdot n_2 \cdots n_k$.
On the shelf there are five card games and three board games. You can take one game in $5 + 3 = 8$ ways: that’s the rule of sum. The game needs a snack too: four kinds of biscuit and three kinds of juice. A biscuit and a juice can be chosen in $4 \cdot 3 = 12$ ways, and a game with a biscuit and a juice in $8 \cdot 4 \cdot 3 = 96$ ways. That’s the rule of product.
The condition “for any choice” is easy to overlook. How many three-digit numbers are written with different digits? The first digit is anything except zero: nine options. The second is anything except the first: nine again (zero is now allowed). The third is anything except the two already used: eight. Which digits are free depends on the first steps, but how many are free doesn’t. That’s why the rule works.
How many three-digit numbers have all three digits different?
The first digit is from $1$ to $9$: nine options. The second is any of the ten except the first: nine. The third is anything except the two used: eight. By the rule of product $9 \cdot 9 \cdot 8 = 648$.
The rule of sum needs care too. If the groups overlap, the shared options get counted twice. We’ll see how to deal with that at the table with the hats.
Who sits where
Six guests sit down on six chairs along a table. The first chair can be taken by any of the six, the second by any of the remaining five, the third by one of four. The last guest gets the last chair. That’s $6 \cdot 5 \cdot 4 \cdot 3 \cdot 2 \cdot 1 = 720$ seatings in all. If the guests want to sit differently every evening, they’ll have enough for almost two years.
A permutation of $n$ different objects is any ordering of them in a row. The product $1 \cdot 2 \cdot 3 \cdots n$ is called the factorial of $n$ and written $n!$ (read “$n$ factorial”).
$n$ different objects can be arranged in a row in exactly $n!$ ways.
An arrangement is a choice in $n$ steps: which object goes in the first place, which in the second, and so on. Any of the $n$ objects will do for the first place. For the second, any of the $n - 1$ remaining ones; which ones remain depends on the first step, but there are always $n - 1$ of them. For the third place $n - 2$ options remain, and so on down to the last place, which takes the one remaining object. The condition of the rule of product holds at every step, so there are $n \cdot (n - 1) \cdot \ldots \cdot 2 \cdot 1 = n!$ arrangements.
The factorial grows at a tremendous rate. A pack of $52$ cards can be shuffled in $52!$ ways, a number with $68$ digits, about $8 \cdot 10^{67}$. If all eight billion people on Earth had shuffled a pack a second since the Big Bang, they’d have produced about $3.5 \cdot 10^{27}$ packs. That’s a negligible fraction of all the orders. Almost certainly the pack you shuffle well this evening will be in an order no pack in history has ever been in.
Now back to the dice. Why does “$1 + 4 + 4$” come up in three ways rather than six? Arrange the set $\{1, 4, 4\}$ on three dice. If the fours were different (say, one red and one blue), there’d be $3! = 6$ ways. But swapping the two fours gives nothing new, so each outcome has been counted twice: $3!/2! = 3$.
“Words” made from letters with repeats are counted the same way. The letters of MAMA give $\frac{4!}{2! \cdot 2!} = 6$ words: MMAA, MAMA, MAAM, AMMA, AMAM, AAMM. The word COMBINATORICS has thirteen letters, and three of them occur twice (C, O, I). Rearranging them, you can get $\frac{13!}{2!\cdot 2! \cdot 2!} = 778{,}377{,}600$ different “words”.
How many different “words” (not necessarily meaningful) can be made by rearranging the letters of BANANA?
Six letters in all: A three times, N twice, B once. If all the letters were different, there’d be $6! = 720$ permutations. The three A’s can be permuted among themselves in $3! = 6$ ways and the two N’s in $2! = 2$ ways, and these permutations don’t change the word. Answer: $\frac{720}{6 \cdot 2} = 60$.
The podium
A draughts tournament has eight players, and we care only about the three prize-winners: who gets gold, who silver, who bronze. Gold can go to any of the eight, silver to any of the remaining seven, bronze to any of six. There are $8 \cdot 7 \cdot 6 = 336$ podiums.
An arrangement of $k$ out of $n$ is an ordered choice of $k$ different objects out of $n$: both who is chosen and in what order matter. Their number is written $A_n^k$ (that’s how some textbooks write it; English ones more often use $P(n, k)$).
$k$ different objects can be chosen in order from $n$ in $A_n^k = n(n - 1)\cdots(n - k + 1) = \dfrac{n!}{(n - k)!}$ ways.
The first place is taken by any of the $n$ objects, the second by any of the $n - 1$ remaining, and so on; the $k$th place by any of the $n - (k - 1) = n - k + 1$ remaining. By the rule of product there are $n(n - 1)\cdots(n - k + 1)$ ways: a product of $k$ factors. To write it with factorials, multiply and divide it by $(n - k)! = (n - k)(n - k - 1)\cdots 1$. The numerator becomes the product of all the numbers from $n$ down to $1$, that is, $n!$, so $A_n^k = \frac{n!}{(n - k)!}$.
The deal
From the same eight players we need to choose three for a team event. There’s no captain and no order: the team “Ann, Ben, Cat” is the same as “Cat, Ann, Ben”. Each team of three can be put on a podium in $3! = 6$ ways, so there are six times as many podiums as teams. There are $336 / 6 = 56$ teams.
A combination of $k$ out of $n$ is a choice of $k$ objects out of $n$ without regard to order. The number of combinations is called a binomial coefficient and written $\binom{n}{k}$ (read “$n$ choose $k$”). Some textbooks also write $C_n^k$.
$k$ objects can be chosen from $n$ without regard to order in $\dbinom{n}{k} = \dfrac{n!}{k!\,(n - k)!}$ ways.
Let’s count the ordered choices, the podiums, in two ways. On the one hand, there are $A_n^k = \frac{n!}{(n - k)!}$ of them. On the other hand, a podium can be chosen in two steps: first an unordered team of $k$ people (that’s $\binom{n}{k}$ options), then its order on the podium (that’s $k!$ options for any team, the number of permutations of $k$ people). By the rule of product there are $\binom{n}{k} \cdot k!$ podiums. Setting the two equal, $\binom{n}{k} \cdot k! = \frac{n!}{(n - k)!}$, and dividing both sides by $k!$.
At the card table this formula answers every question about deals. In poker a player gets five cards out of $52$, and there are $\binom{52}{5} = 2{,}598{,}960$ different hands. Exactly four of them are a royal flush (ace, king, queen, jack and ten of one suit), so one comes up about once in six hundred and fifty thousand deals. In a lottery where you pick $6$ numbers out of $45$ there are $\binom{45}{6} = 8{,}145{,}060$ combinations: one ticket matches all six numbers with a chance of one in eight million.
In how many ways can two people on duty be chosen from five?
Order doesn’t matter, so these are combinations: $\binom{5}{2} = \frac{5 \cdot 4}{2} = 10$. If we needed a senior and an assistant, the answer would be $A_5^2 = 20$.
At the end of the evening each of the ten guests shook hands with every other guest. How many handshakes were there in all?
A handshake is a pair of guests without regard to order: $\binom{10}{2} = \frac{10 \cdot 9}{2} = 45$. You can also argue differently: each shook $9$ hands, that’s $10 \cdot 9 = 90$, but each handshake has been counted twice, from both sides. This idea will come back in the next chapter.
The rook goes home
On an empty chessboard a rook stands in the corner a1 and wants to reach the opposite corner h8. It moves one square at a time, right or up. How many paths does it have?
Any such path consists of fourteen moves: seven “right” and seven “up”. A path is completely determined by which seven of the fourteen moves are “up”. So there are $\binom{14}{7} = 3432$ paths.
There’s also a second way to count, without the formula. The rook enters each square either from the left or from below. So the number of paths to a square equals the sum of the numbers of paths to its neighbour on the left and its neighbour below. Along the bottom edge and the left edge there’s one path. Filling the board with this rule, we get a table that’s more convenient turned through forty-five degrees. It becomes a triangle in which each number is the sum of the two above it.
For $1 \le k \le n - 1$ we have $\dbinom{n}{k} = \dbinom{n - 1}{k - 1} + \dbinom{n - 1}{k}$.
A path of the rook from the corner $S$ to the square $T$ consists of $n$ moves, $k$ of them up and the rest right. A path is completely given by which $k$ of the $n$ moves go up, so there are exactly $\binom{n}{k}$ paths to $T$. In the picture $n = 5$, $k = 2$.
Look at the last move. If it was up, the rook came into $T$ from the square directly below it. Up to that square it made $n - 1$ moves, $k - 1$ of them up. There are $\binom{n - 1}{k - 1}$ such paths (the square exists because $k \ge 1$), and each continues into $T$ by a single move.
If the last move was to the right, the rook came from the square to the left of $T$. Up to it there are $n - 1$ moves, and all $k$ of the up moves are among them. There are $\binom{n - 1}{k}$ such paths (the square exists because $k \le n - 1$).
The last move is either up or right, not both at once. So the two groups of paths don’t overlap and together give all the paths to $T$. By the rule of sum $\binom{n}{k} = \binom{n - 1}{k - 1} + \binom{n - 1}{k}$; in the picture $10 = 4 + 6$. Filling in square after square this way, we get the numbers of the whole board: that’s Pascal’s triangle, turned through $45°$.
Pascal’s triangle is the table whose $n$th row contains the numbers $\binom{n}{0}, \binom{n}{1}, \ldots, \binom{n}{n}$. Rows are numbered from zero; there are ones along the edges, and each inner number is the sum of the two neighbours above it.
There’s more hidden in Pascal’s triangle than it seems. Colour the odd numbers and leave the even ones blank. The first rows look innocent, but in thirty-two rows a pattern of triangles within triangles emerges: the very one the Polish mathematician Wacław Sierpiński described in 1915.
Why does the pattern appear? We only care about parity, and when parities are added, $1 + 1$ gives even. Row number $2^m$ (for example $16$ or $32$) consists of two ones at the edges with nothing but even numbers between them. From there each of the two ones produces below it an exact copy of the top of the triangle, and between the copies there’s emptiness. Hence the self-similarity. The odd numbers can be counted too: doubling the number of rows triples their number (three copies), so the first $2^m$ rows contain exactly $3^m$ of them. Thirty-two rows hold $528$ numbers, and $3^5 = 243$ of them are odd: less than half, and with each doubling of the rows the share of odd ones falls.
Along the shallow diagonals the numbers add up to $1, 1, 2, 3, 5, 8, 13, \ldots$, the Fibonacci numbers. And the sum of the numbers in row $n$ is $2^n$: $1 + 4 + 6 + 4 + 1 = 16$. We’ll see why when we start tossing coins.
Heads and tails
Toss a coin four times. There are $2^4 = 16$ outcomes, and each is written as a word of the letters H and T, for example HTTH. How many outcomes have exactly two heads? As many as there are ways to choose two places out of four for the letter H: $\binom{4}{2} = 6$. Group all sixteen outcomes by the number of heads: $1$ outcome with no heads, $4$ with one, $6$ with two, $4$ with three and $1$ with four. That’s row four of the triangle, and the sum $16 = 2^4$ is all the outcomes.
The same row appears when you multiply out $(a + b)^4$, and that’s no coincidence.
For any numbers $a$, $b$ and any natural $n$
$$(a + b)^n = \sum_{k = 0}^{n} \binom{n}{k} a^k b^{n - k} = b^n + \binom{n}{1} a b^{n - 1} + \binom{n}{2} a^2 b^{n - 2} + \ldots + a^n.$$$(a + b)^n$ is a product of $n$ identical brackets. By the distributive law, multiplying out gives the sum of all the products in which one term is taken from each bracket: $a$ or $b$. Write each such product as a word of $n$ letters: for example, $abba$ means $a$ was taken from the first bracket, $b$ from the second, $b$ from the third and $a$ from the fourth. There are $2^n$ words (two options per bracket); in the picture $n = 4$, and there are $16$ words.
The product a word stands for depends only on how many letters $a$ the word has. If there are $k$ of them, there are $n - k$ letters $b$, and the product is $a^k b^{n - k}$: rearranging the factors doesn’t change it. Sort the words into columns so that each column has the same number of letters $a$.
How many words are in the column with $k$ letters $a$? A word is determined by which $k$ of the $n$ places hold the letters $a$, and there are $\binom{n}{k}$ such choices. For $n = 4$ we get $1, 4, 6, 4, 1$: row four of Pascal’s triangle.
Collect like terms: the column with $k$ letters $a$ gives $\binom{n}{k} a^k b^{n - k}$. Adding the columns from $k = 0$ to $k = n$, we get the binomial formula. For $n = 4$: $(a + b)^4 = a^4 + 4a^3b + 6a^2b^2 + 4ab^3 + b^4$.
$\dbinom{n}{0} + \dbinom{n}{1} + \ldots + \dbinom{n}{n} = 2^n$.
Put $a = b = 1$ in the binomial theorem: the left side becomes $(1 + 1)^n = 2^n$, and the right side, since all powers of one equal one, becomes the sum $\binom{n}{0} + \binom{n}{1} + \ldots + \binom{n}{n}$. You can see it without the formula too: both sides count all the outcomes of $n$ coin tosses. The left side counts them all at once, by the rule of product; the right side in groups, by the number of heads, by the rule of sum.
Multiply out $(x + 2)^5$. What is the coefficient of $x^3$?
To get $x^3$, we take $x$ from three brackets and twos from the remaining two. Three brackets out of five can be chosen in $\binom{5}{3} = 10$ ways, and each time the twos give a factor $2^2 = 4$. The coefficient is $10 \cdot 4 = 40$.
Chips and bars
A new game begins with sharing out. The box holds ten identical chips, there are four players, and the chips can be shared any way at all: someone may get none. How many ways are there? The chips are identical, so all that matters is how many each player has. A share-out is a list of four numbers, for example $(3, 0, 5, 2)$, adding up to $10$.
Listing the share-outs one by one takes a long time. The trick is to turn each share-out into a row of chips and bars.
$n$ identical objects can be shared between $k$ recipients (some may get nothing) in exactly $\dbinom{n + k - 1}{k - 1}$ ways.
A share-out is a list of numbers $(x_1, x_2, \ldots, x_k)$: how many objects each recipient got. All $x_i \ge 0$, and their sum is $n$. In the picture $n = 10$, $k = 4$ and the share-out is $(3, 0, 5, 2)$.
Lay the share-out out in a row: the first recipient’s chips, a bar, the second’s chips, a bar, … the last one’s chips. There are $k - 1$ bars and $n$ chips, $n + k - 1$ places in the row altogether. The second player got nothing: in the row that’s two bars in a row.
Conversely, any row of $n$ chips and $k - 1$ bars can be read as a share-out: count the chips before the first bar, between the first and second, and so on to the end. The row gives back exactly the share-out it was made from, and vice versa. So there are exactly as many share-outs as rows.
A row is completely given by which $k - 1$ of the $n + k - 1$ places are taken by bars; the chips stand in the other places. There are $\binom{n + k - 1}{k - 1}$ such choices. In the picture $\binom{13}{3} = 286$.
There are $\binom{n + k - 1}{k - 1}$ share-outs. If everyone is due at least one object, first give one to each and then share the remaining $n - k$ any way at all: by what we’ve proved, that’s $\binom{(n - k) + k - 1}{k - 1} = \binom{n - 1}{k - 1}$ ways.
This formula also closes the story of the dice. How many different “sets of points” do three dice have at all, if the dice aren’t told apart? It’s sharing out three identical “dice” among the six face values: $\binom{3 + 6 - 1}{5} = \binom{8}{5} = 56$. Fifty-six sets against $216$ outcomes. The players who thought in sets were counting in the wrong units: sets aren’t equally likely, outcomes are.
All the techniques we’ve gathered are worth practising. The key question in every problem is the same: does order matter, and can objects repeat? If you meet a problem you just can’t untangle, the solver will take it apart step by step.
Want to bet?
While chips are being shared out at the next table, here people are making bets that can’t be lost. “Bet you that among the thirteen of us two were born in the same month?” There are twelve months and thirteen people. Even if the first twelve were born in different months, the thirteenth has nowhere to go.
This argument is called the pigeonhole principle; in English it’s told about pigeons and holes (some books tell it about rabbits in hutches).
If $n + 1$ pigeons are put into $n$ holes, some hole holds at least two pigeons. In general: if $N$ objects are put into $n$ boxes, some box contains at least $N / n$ of them.
We argue by contradiction. Suppose each hole holds at most one pigeon. In the picture there are $n = 4$ holes and $5$ pigeons.
Then there are no more pigeons than holes: one in each is exactly $n$ pigeons, and if some holes are empty, fewer. But there are $n + 1$ pigeons, one more.
A contradiction: the extra pigeon has nowhere to go and ends up in a hole that’s already taken. So the assumption is false: some hole holds at least two pigeons.
The general form is proved the same way. If each of the $n$ boxes held fewer than $N / n$ objects, there’d be fewer than $n \cdot \frac{N}{n} = N$ in all. But there are exactly $N$: a contradiction.
It sounds trivial, and the proof really is short. The difficulty lies elsewhere: seeing what in a problem are the pigeons and what are the holes. The German mathematician Peter Gustav Lejeune Dirichlet used this argument in number theory in the nineteenth century; in German it’s called the “drawer principle”, and many languages name it after him. It has already been at work in the chapter on fractions: in long division there are fewer remainders than steps, so some remainder repeats and the digits go round in a circle.
A bolder bet: there are certainly two people in London with the same number of hairs on their head. A person has something like a hundred thousand hairs and certainly fewer than a million, and London has close to nine million inhabitants. The boxes are the possible numbers of hairs, from zero to a million, and the objects are Londoners. Who exactly the bet is about, nobody knows, but it’s impossible to lose.
A dark drawer holds ten black and ten white socks, all mixed up. How many socks do you need to pull out without looking to be sure of a pair of the same colour?
The colours are the boxes, and there are two of them. Three socks in two boxes: some box gets two. But to be sure of a black pair specifically, you’d need $12$ socks.
One more bet that will come in handy in the next chapter.
In any group of two or more people there are two who have the same number of acquaintances within the group.
Let there be $n$ people. Each has from $0$ to $n - 1$ acquaintances in the group: that’s $n$ possible numbers, $n$ boxes, exactly as many as there are people, so the pigeonhole principle doesn’t work directly. But the boxes “$0$” and “$n - 1$” can’t both be occupied: if someone knows everyone else, then everyone knows at least that person, and nobody has zero acquaintances. So at most $n - 1$ boxes are occupied, and there are $n$ people. By the pigeonhole principle two of them end up in the same box: they have the same number of acquaintances.
Thirteen
In 1708 the French mathematician Pierre Rémond de Montmort analysed the card game of Thirteen in his book on games of chance. The banker turns over the cards of one suit one at a time and counts aloud: “ace, two, three, …, king”. If even once the card turned over matches the one called, the banker wins. If there’s no match in thirteen cards, the player wins. Whom does the game favour?
The same problem in a cloakroom: $n$ guests hand in their hats, and the attendant gives them back at random. What’s the probability that nobody gets their own hat? To answer, we have to learn to subtract overlaps.
A warm-up first. How many numbers from $1$ to $100$ are divisible by $2$, by $3$ or by $5$? There are $50$ even numbers, $33$ multiples of three and $20$ multiples of five. But in the sum $50 + 33 + 20 = 103$ numbers like $6$ have been counted twice, and the number $30$ even three times. Subtract the multiples of six ($16$), ten ($10$) and fifteen ($6$): we get $71$. However, the multiples of thirty were first added three times and then subtracted three times, so they’ve vanished. Put them back: $71 + 3 = 74$.
The inclusion–exclusion principle counts how many objects fall into at least one of several groups: add the sizes of the groups, subtract the pairwise overlaps, add the triple overlaps, subtract the fourfold ones, and so on, alternating the signs.
For any three finite groups $A$, $B$, $C$
$$|A \cup B \cup C| = |A| + |B| + |C| - |A \cap B| - |A \cap C| - |B \cap C| + |A \cap B \cap C|.$$Here $|X|$ is the number of objects in the group $X$, $A \cup B$ is everyone in at least one of the groups, and $A \cap B$ is those in both at once.
The circles $A$, $B$, $C$ divide everything inside them into seven parts. Let’s count how many times each object is counted in the sum $|A| + |B| + |C|$: an object in one circle once, in two circles twice, in all three three times. These numbers are written in the picture.
Subtract $|A \cap B| + |A \cap C| + |B \cap C|$. An object lying in exactly two circles is in exactly one of these overlaps: it was $2$, it becomes $1$. An object in all three circles is in all three overlaps: it was $3$, it becomes $0$. Objects in a single circle aren’t affected by the subtraction.
Add $|A \cap B \cap C|$. This affects only the central part: it was $0$, it becomes $1$.
Now every object in at least one circle is counted exactly once, and objects outside the circles not at all. So the right-hand side equals $|A \cup B \cup C|$.
Now the hats. We need to count the permutations in which nobody gets their own hat.
A derangement is a permutation in which no object stays in its own place. The number of derangements of $n$ objects is written $D_n$.
$D_n = n! \left(1 - \dfrac{1}{1!} + \dfrac{1}{2!} - \dfrac{1}{3!} + \ldots + \dfrac{(-1)^n}{n!}\right)$.
The idea: check how many times the right-hand side counts each permutation, and see that it counts derangements once each and the other permutations not at all.
Open the bracket: the right-hand side equals $\sum_{j = 0}^{n} (-1)^j \frac{n!}{j!}$, and $\frac{n!}{j!} = \binom{n}{j}(n - j)!$. The number $\binom{n}{j}(n - j)!$ counts pairs “a set of $j$ guests and a permutation in which each of them got their own hat”: the set is chosen in $\binom{n}{j}$ ways, the chosen guests get their own hats, and the other $n - j$ hats are handed out any way at all, in $(n - j)!$ ways.
Take a permutation in which exactly $m$ guests got their own hat. In the $j$th term it’s counted as many times as it has sets of $j$ guests who got their own, that is, $\binom{m}{j}$ times. With the signs it’s counted $\binom{m}{0} - \binom{m}{1} + \binom{m}{2} - \ldots + (-1)^m \binom{m}{m}$ times. By the binomial theorem with $a = -1$, $b = 1$ this sum equals $(1 - 1)^m$, that is, $0$ for $m \ge 1$ and $1$ for $m = 0$. So the right-hand side counts exactly the permutations with no matches, once each: that’s $D_n$.
Divide by $n!$ and we get the probability that nobody gets their own hat: $1 - 1 + \frac{1}{2!} - \frac{1}{3!} + \ldots$ If this series is continued without end, it converges to $\frac{1}{e} \approx 0.3679$, where $e \approx 2.718$ is the very number from the chapter on the exponential. Already with six guests the probability differs from the limit by less than a thousandth. The number of guests hardly changes anything: with six, with thirteen and with a thousand the chance that “nobody gets their own” is about $37\,\%$.
So the game of Thirteen favours the banker: they win with probability $1 - \frac{D_{13}}{13!} \approx 0.632$, almost two times out of three. Montmort found the general answer by 1713, in the second edition of his book, together with Nicolaus Bernoulli.
Brackets and cake
An old calculator has an odd quirk: it can only multiply two numbers at a time. To compute $a \cdot b \cdot c \cdot d$, you have to tell it the order with brackets. There are five ways: $((ab)c)d$, $(a(bc))d$, $(ab)(cd)$, $a((bc)d)$, $a(b(cd))$. For five factors there are $14$ ways, for six $42$.
At the next table a cake in the shape of a regular hexagon is being cut. You may cut only along diagonals, from corner to corner, so that the cuts don’t cross, and in the end there must be nothing but triangles. How many ways are there? $14$ again. The coincidence isn’t an accident.
The Catalan numbers $C_0, C_1, C_2, \ldots = 1, 1, 2, 5, 14, 42, 132, 429, \ldots$ count the ways of bracketing a product of $n + 1$ factors and of cutting a convex $(n + 2)$-gon into triangles. (Here the letter has a single index; don’t confuse it with $C_n^k$.)
There are exactly $\dfrac{1}{n + 1}\dbinom{2n}{n}$ well-formed words of $n$ opening and $n$ closing brackets (in which each bracket closes after it has opened).
Write a word as a zigzag: “(” is a step up, “)” a step down. The word is well formed exactly when the zigzag of $2n$ steps, starting at level $0$, never drops below zero (otherwise some “)” closes something that was never opened) and ends at zero. There are $\binom{2n}{n}$ zigzags with $n$ steps up and $n$ down in all: that’s the number of ways to choose the places for “(”.
A bad zigzag drops below zero at least once, that is, it touches level $-1$. Mark the first such touch.
Reflect the part of the zigzag after the first touch in level $-1$: each step up becomes a step down and vice versa. Before, the zigzag ended $1$ above the line $-1$; now it ends $1$ below, at level $-2$. It now has $n - 1$ steps up and $n + 1$ down.
Conversely, any zigzag with $n - 1$ steps up and $n + 1$ down ends at level $-2$, and so it’s bound to touch level $-1$ on the way. Reflecting its tail after the first touch, we get a bad zigzag, and this operation undoes the previous one. So there are as many bad zigzags as zigzags ending at $-2$: $\binom{2n}{n + 1}$. For $n = 4$ there are $70$ zigzags in all, $56$ bad and $14$ good.
There are $\binom{2n}{n} - \binom{2n}{n + 1}$ good zigzags. Comparing factorials, we see $\binom{2n}{n + 1} = \frac{(2n)!}{(n + 1)!\,(n - 1)!} = \binom{2n}{n} \cdot \frac{n}{n + 1}$, so there are $\binom{2n}{n}\left(1 - \frac{n}{n + 1}\right) = \frac{1}{n + 1}\binom{2n}{n}$ good ones.
There are equally many bracketings of a product of $n + 1$ factors, cuttings of a convex $(n + 2)$-gon into triangles and well-formed words of $n$ pairs of brackets: $C_n$ of each.
The idea: all three families are built from smaller ones by the same rule. Denote their sizes by $P_n$, $T_n$ and $W_n$ and put $P_0 = T_0 = W_0 = 1$: a single factor, a “2-gon” (just a segment) and the empty word can each be built in only one way. Let’s show that each of the three sequences satisfies the rule $X_{n + 1} = X_0 X_n + X_1 X_{n - 1} + \ldots + X_n X_0$. Then they coincide: the starting values are equal, and each next value is computed from the previous ones in the same way.
Brackets. In a product of $n + 2$ factors the last multiplication multiplies a left part of $i + 1$ factors by a right part of $n + 1 - i$, where $i$ runs from $0$ to $n$. The brackets inside the parts are placed independently, so for a given $i$ there are $P_i \cdot P_{n - i}$ options (the rule of product), and in all the sum over $i$ (the rule of sum).
Cuttings. Put one side of the $(n + 3)$-gon at the bottom. Above it stands exactly one triangle of the cutting: the side belongs to exactly one triangle. Its top vertex divides the rest into a left polygon with $i + 2$ vertices and a right one with $n + 2 - i$ vertices, and they’re cut independently: $T_i \cdot T_{n - i}$ options. If the sides other than the bottom one are labelled with letters, this triangle is the last multiplication “(everything on the left) · (everything on the right)”: that’s exactly the correspondence the widget shows.
Words. In a well-formed word of $n + 1$ pairs the first “(” is closed by some “)”. Between them stands a well-formed word $X$ of $i$ pairs, after them a well-formed word $Y$ of $n - i$ pairs: the whole word has the form “( $X$ ) $Y$”. The words $X$ and $Y$ are chosen independently: $W_i \cdot W_{n - i}$ options.
Six guests
The last game of the evening is about the guests themselves. Take any six of them. The claim is that among them there are bound to be three who all know one another, or three who are all strangers to one another. Whichever guests you invite.
Among any six people there are either three who all know one another or three who are mutual strangers. For five people this is no longer true.
Draw the guests as dots and join each pair by a segment: orange if they know each other, blue if they don’t. Take one guest, Ann. Five segments of two colours leave her, and by the pigeonhole principle (five segments, two colours, $5 / 2 > 2$) at least three of them are the same colour. Say these are orange segments to Ben, Cat and Dan; if there are three blue ones, the argument is the same with the colours swapped.
Look at the three segments between Ben, Cat and Dan. If even one of them is orange, say Ben–Cat, then Ann, Ben and Cat all know one another: an orange triangle.
If none of them is orange, all three are blue: Ben, Cat and Dan are mutual strangers, a blue triangle. There’s no third possibility, so a one-colour triangle can always be found.
For five people the statement is false. Seat them at a round table and let only neighbours know each other. The acquaintances form an orange pentagon, the non-acquaintances a blue five-pointed star, and neither figure contains a triangle.
This is a special case of a theorem proved by the English mathematician Frank Ramsey. The paper came out in 1930, the year of his early death: Ramsey was twenty-six.
The Ramsey number $R(m, n)$ is the smallest number of people among whom there are bound to be $m$ who all know one another or $n$ mutual strangers. We’ve just proved that $R(3, 3) = 6$. But why does such a number exist at all for every $m$ and $n$?
For any natural $m$ and $n$ the number $R(m, n)$ exists, and $R(m, n) \le R(m - 1, n) + R(m, n - 1)$.
The idea is the same as with the six guests: pick one person and split the rest into their acquaintances and strangers. We use induction on $m + n$ (see the chapter on sequences). Base: if $m = 1$ or $n = 1$, then $R = 1$, since one person already forms a “group of one”.
Step. Let $m, n \ge 2$, and suppose that for the pairs $(m - 1, n)$ and $(m, n - 1)$ the numbers $A = R(m - 1, n)$ and $B = R(m, n - 1)$ already exist. Take a group of $A + B$ people and pick Ann in it. The other $A + B - 1$ people split into her acquaintances and strangers. She has at least $A$ acquaintances or at least $B$ strangers: otherwise there’d be at most $(A - 1) + (B - 1) = A + B - 2$ people in all (the pigeonhole principle).
If Ann has at least $A$ acquaintances, among them there are $m - 1$ who all know one another (and together with Ann that’s $m$) or $n$ mutual strangers, and in both cases we’re done. If she has at least $B$ strangers, among them there are $m$ who all know one another or $n - 1$ mutual strangers (and together with Ann that’s $n$). So any group of $A + B$ people contains the group we need, and $R(m, n) \le A + B$; taking $A = R(m - 1, n)$ and $B = R(m, n - 1)$, we get the inequality of the theorem. For $m = n = 3$: $R(2, 3) = 3$ (among three people either some two know each other or all three are mutual strangers), so $R(3, 3) \le 3 + 3 = 6$, exactly what the guests problem showed.
Based on this theorem, in 1969 the American cryptographer Gustavus Simmons devised a two-player game he called Sim. Six dots, fifteen segments. The players take turns colouring segments, each in their own colour, and whoever first completes a triangle of their own colour loses. There are no draws: when the segments run out, there’s bound to be a one-colour triangle, which means someone completed it earlier.
In 1974 a computer search showed that with perfect play Sim is always won by the second player. But the strategy is beyond a human memory, so the game stays interesting.
The exact values of Ramsey numbers are known only for very small groups. $R(4, 4) = 18$ was established in 1955. About $R(5, 5)$ all that’s known even now is that it’s at least $43$ and at most $46$; the upper bound was proved in 2024 with a huge computer search. Paul Erdős, as his co-author Joel Spencer tells it, used to joke like this: if aliens demanded the value of $R(5, 5)$ under threat of destroying the Earth, we should put all our computers and all our mathematicians on the problem. But if they demanded $R(6, 6)$, it would be wiser to try to destroy the aliens.
Combinatorics can not only count possibilities but also prove that the possibility you need is bound to occur. A large enough system is never in complete disorder: some order appears in it all by itself.
Where next
After the evening the guests go out for a walk. The eighteenth-century city of Königsberg stood on the river Pregel, which flowed around two islands. The banks and islands were joined by seven bridges. The townspeople loved a puzzle: walk through the city crossing each bridge exactly once.
There are finitely many routes with the bridges in different orders, and they can be checked one by one: we now know how to count. But checking explains nothing, and the problem calls for an explanation: why it can’t be done, and what to do about another city with thirty bridges. Leonhard Euler found an answer that needs no checking at all. To do so he had to forget about distances, the shape of the banks and the width of the river and keep only points and the connections between them, as we did with the six guests. That’s how graphs came about, and they’re the subject of the next chapter.