Combinatorics · The Lumenary

Lens

MotivationH

Three questions

Choosing. A cricket coach in Lahore has a squad of $15$ and must name a team of $11$ . How many different teams are possible? Listing them is hopeless — but, as we will see, the answer is exactly $1365$ , and it can be found in a few seconds.

Expanding. Multiply out $(x + y)^5$ . You could grind through five brackets — or notice that the coefficients $1, 5, 10, 10, 5, 1$ are already written in a triangle of numbers that was known in India, Persia, North Africa and China centuries before Blaise Pascal wrote about it — though in English it carries his name, Pascal's triangle.

Guaranteeing. In any group of $13$ people, two were born in the same month. Not "probably" — certainly. Yet the argument does not tell us which two.

These are the three faces of combinatorics, the mathematics of finite arrangements: counting exactly, recognising the same count in different disguises, and proving that something must exist. Its favourite method is to count the same set in two different ways — and then the two answers must agree.

IntuitionH

When does order matter?

From five friends — Amina, Bao, Carlos, Divya and Emeka — we choose two.

If we are choosing a captain and a vice-captain, order matters: (Amina, Bao) is different from (Bao, Amina). There are $5$ choices for the captain and then $4$ for the vice-captain, so $5 \times 4 = 20$ ordered pairs, by the multiplication principle from counting principles.

If we are choosing two people to carry the drinks, order does not matter: $\{\text{Amina}, \text{Bao}\}$ is one pair, however we list it. Each unordered pair appears twice among the $20$ ordered pairs, so there are $20 / 2 = 10$ unordered pairs:

\begin{aligned} &\{A, B\}, \{A, C\}, \{A, D\}, \{A, E\}, \{B, C\},\\ &\{B, D\}, \{B, E\}, \{C, D\}, \{C, E\}, \{D, E\}. \end{aligned}

This is the division principle: if a list counts every object of interest exactly $m$ times, divide by $m$ . Choosing $3$ of the $5$ , there are $5 \times 4 \times 3 = 60$ ordered lists, and each set of three appears in $3! = 6$ orders, so there are $60 / 6 = 10$ sets of three.

DefinitionsH

Definitions

Recall $n! = n \times (n - 1) \times \cdots \times 2 \times 1$ , with $0! = 1$ , and that the number of ordered selections of $k$ different objects from $n$ is $n(n - 1)\cdots(n - k + 1) = \dfrac{n!}{(n - k)!}$ .

Definition— binomial coefficient

For whole numbers $n$ and $k$ , the binomial coefficient $\binom{n}{k}$ , read " $n$ choose $k$ ", is the number of $k$ -element subsets of an $n$ -element set. In particular $\binom{n}{k} = 0$ when $k > n$ (there are no such subsets), and $\binom{n}{0} = \binom{n}{n} = 1$ .

So $\binom{5}{2} = 10$ by the list above. Notice that the definition is a counting definition; the formula comes next, as a theorem.

Definition— pigeonhole principle

If more than $n$ objects are placed in $n$ boxes, then some box contains at least two objects.

Definition— inclusion–exclusion (two sets)

For finite sets $A$ and $B$ : $\;|A \cup B| = |A| + |B| - |A \cap B|$ .

Here $|A|$ is the number of elements of $A$ , as in the lesson on sets. The pigeonhole principle and inclusion–exclusion are both proved below.

Worked examplesH

Worked examples

Example— The cricket team

Choosing the $11$ players who play is the same as choosing the $4$ who sit out, so the number of teams is $\binom{15}{11} = \binom{15}{4} = \dfrac{15 \times 14 \times 13 \times 12}{4 \times 3 \times 2 \times 1} = 1365$ .

Example— Routes through a grid

In a city laid out in blocks, a courier cycles from a corner to the corner $4$ blocks east and $3$ blocks north, always heading east or north. Every route is a word of $7$ letters with $4$ E's and $3$ N's, such as ENNEENE. A route is decided by which $3$ of the $7$ steps are north, so there are $\binom{7}{3} = 35$ routes.

Example— Card hands

A five-card hand from a pack of $52$ is a $5$ -element subset: there are $\binom{52}{5} = 2\,598\,960$ hands.
A full house (three cards of one rank, two of another): choose the rank of the three ( $13$ ways), which three suits ( $\binom{4}{3} = 4$ ), the rank of the pair ( $12$ ways), and which two suits ( $\binom{4}{2} = 6$ ). Multiplication principle: $13 \times 4 \times 12 \times 6 = 3744$ hands.
Hands with at least one ace: count the complement. Hands with no ace choose all $5$ cards from the $48$ others, so the answer is $\binom{52}{5} - \binom{48}{5} = 2\,598\,960 - 1\,712\,304 = 886\,656$ .

Example— A word with repeated letters

How many different arrangements are there of the letters of BANANA? If the six letters were all different there would be $6! = 720$ . But swapping the three A's among themselves ( $3! = 6$ ways) or the two N's ( $2! = 2$ ways) gives the same word. Each word is counted $6 \times 2 = 12$ times, so there are $720 / 12 = 60$ words.

Example— A non-example: overcounting

"Hands with at least one ace: choose an ace ( $4$ ways), then any $4$ of the other $51$ cards: $4 \times \binom{51}{4} = 999\,600$ ." This is wrong — it is larger than the correct $886\,656$ . A hand with two aces, say the ace of hearts and the ace of spades, is counted twice: once when the hearts ace is "the chosen ace" and once when the spades ace is. Every counting argument must produce each object exactly once (or exactly $m$ times, and then we divide).

ProofH

Theorems, proved by counting

Theorem— Theorem 1 (the factorial formula)

For $0 \le k \le n$ : $\displaystyle \binom{n}{k} = \frac{n!}{k!\,(n - k)!}$ .

Proof

Count the ordered selections of $k$ different objects from $n$ in two ways. Directly, there are $\dfrac{n!}{(n - k)!}$ of them. Alternatively, first choose the set of $k$ objects ( $\binom{n}{k}$ ways) and then put it in order ( $k!$ ways): so there are $\binom{n}{k} \cdot k!$ of them. Hence $\binom{n}{k} \cdot k! = \dfrac{n!}{(n - k)!}$ ; divide by $k!$ .

∎

Theorem— Theorem 2 (symmetry)

For $0 \le k \le n$ : $\displaystyle \binom{n}{k} = \binom{n}{n - k}$ .

Proof

Sending each $k$ -element subset $S$ of an $n$ -element set $X$ to its complement $X \setminus S$ , which has $n - k$ elements, is a one-to-one correspondence: it is its own inverse, since the complement of the complement is $S$ again. So the two collections have the same size.

∎

Theorem— Theorem 3 (Pascal's rule)

For $n \ge 1$ and $k \ge 1$ : $\displaystyle \binom{n}{k} = \binom{n - 1}{k - 1} + \binom{n - 1}{k}$ .

Proof

Count the $k$ -person committees chosen from $n$ people, one of whom is Amina. Every committee either contains Amina or it does not, and not both.

Committees containing Amina: removing her leaves $k - 1$ members chosen from the other $n - 1$ people, and putting her back undoes this. So there are $\binom{n - 1}{k - 1}$ of them.
Committees not containing Amina: all $k$ members come from the other $n - 1$ people. There are $\binom{n - 1}{k}$ of them.

Adding the two disjoint kinds counts every committee exactly once.

∎

Pascal's rule says that each entry of the triangle is the sum of the two entries above it. Starting from the $1$ s down the edges, it generates all the binomial coefficients without a single multiplication.

Rows $0$ to $6$ of Pascal's triangle. Row $n$ lists $\binom{n}{0}, \binom{n}{1}, \dots, \binom{n}{n}$. Highlighted: Pascal's rule $\binom{5}{2} = \binom{4}{1} + \binom{4}{2}$, that is $10 = 4 + 6$.

Theorem— Theorem 4 (the binomial theorem)

For every whole number $n$ and all numbers $x, y$ :

(x + y)^n = \sum_{k=0}^{n} \binom{n}{k} x^k y^{n-k} = y^n + \binom{n}{1} x y^{n-1} + \binom{n}{2} x^2 y^{n-2} + \cdots + x^n.

Proof

Write $(x + y)^n = (x + y)(x + y)\cdots(x + y)$ with $n$ brackets. Multiplying out, we get one term for each way of choosing either $x$ or $y$ from every bracket, and the term is the product of the choices. A choice that takes $x$ from exactly $k$ brackets (and $y$ from the other $n - k$ ) gives $x^k y^{n-k}$ . The number of such choices is the number of ways to pick which $k$ of the $n$ brackets supply an $x$ : that is $\binom{n}{k}$ . Collecting equal terms (multiplication of numbers is commutative) gives the formula.

∎

There is also a proof by induction on $n$ , which is the one Lean checks below for $(1 + x)^n$ : multiply $(1 + x)^n = \sum_k \binom{n}{k} x^k$ by $1 + x$ , and the coefficient of $x^{k+1}$ in the product is $\binom{n}{k+1} + \binom{n}{k}$ — which is $\binom{n+1}{k+1}$ by Pascal's rule. The induction proof and the counting proof are two views of the same fact, which links this lesson to proof by induction and to polynomials.

Example— Using the theorem

$(2x - 1)^4 = \sum_k \binom{4}{k} (2x)^k (-1)^{4-k} = 16x^4 - 32x^3 + 24x^2 - 8x + 1$ . Check: putting $x = 1$ gives $1 = 16 - 32 + 24 - 8 + 1$ .

Theorem— Corollary 5 (row sums)

For every $n$ : $\displaystyle \sum_{k=0}^{n} \binom{n}{k} = 2^n$ , and for $n \ge 1$ : $\displaystyle \sum_{k=0}^{n} (-1)^k \binom{n}{k} = 0$ .

Proof

Put $x = y = 1$ in the binomial theorem for the first identity, and $x = -1$ , $y = 1$ for the second: $(1 + 1)^n = 2^n$ and $(-1 + 1)^n = 0^n = 0$ when $n \ge 1$ .

A counting proof of the first: both sides count all subsets of an $n$ -element set. On the left, they are sorted by size; on the right, each of the $n$ elements is either in or out — $2^n$ possibilities. The second identity says that a non-empty set has as many subsets of even size as of odd size.

∎

The pigeonhole principle

Theorem— Theorem 6 (pigeonhole principle)

If more than $n$ objects are placed in $n$ boxes, some box contains at least two objects. More generally, if $m$ objects are placed in $n$ boxes, some box contains at least $\lceil m/n \rceil$ objects.

Proof

Suppose instead that every box contained at most $\lceil m/n \rceil - 1$ objects. Since $\lceil m/n \rceil - 1 < m/n$ , the total number of objects would be less than $n \cdot \dfrac{m}{n} = m$ — a contradiction. With $m > n$ we have $\lceil m/n \rceil \ge 2$ , which is the first statement.

∎

The principle is almost too obvious to state — its power lies in choosing the objects and the boxes cleverly.

Example— Birth months

$13$ people, $12$ months as boxes: two people share a birth month.

Example— Remainders

Among any $n + 1$ integers, two differ by a multiple of $n$ . Boxes: the $n$ possible remainders $0, 1, \dots, n - 1$ on division by $n$ . Two of the $n + 1$ integers land in the same box, and two numbers with the same remainder differ by a multiple of $n$ .

Example— Points in a square

Place $5$ points anywhere in a square of side $2$ . Then some two are at distance at most $\sqrt{2}$ . Boxes: cut the square into four unit squares (a point on a dividing line goes into either neighbouring square). Two points share a unit square, and no two points of a unit square are further apart than its diagonal, $\sqrt{2}$ .

Example— Acquaintances at a party

At any gathering of $n \ge 2$ people, two of them have the same number of acquaintances present (acquaintance being mutual). Each person knows between $0$ and $n - 1$ others: $n$ possible numbers. But $0$ and $n - 1$ cannot both occur — if someone knows everybody, nobody knows nobody. So the $n$ people have at most $n - 1$ possible numbers between them, and two share a number. (In the language of graphs: every finite simple graph with at least two vertices has two vertices of the same degree.)

Inclusion–exclusion

Theorem— Theorem 7 (inclusion–exclusion for two and three sets)

For finite sets $A$ , $B$ , $C$ :

|A \cup B| = |A| + |B| - |A \cap B|,

|A \cup B \cup C| = |A| + |B| + |C| - |A \cap B| - |A \cap C| - |B \cap C| + |A \cap B \cap C|.

Proof

Two sets. $|A| + |B|$ counts every element of $A \cup B$ once, except the elements of $A \cap B$ , which are counted twice; subtracting $|A \cap B|$ corrects this.

Three sets. Apply the two-set rule to $A \cup B$ and $C$ : $|A \cup B \cup C| = |A \cup B| + |C| - |(A \cup B) \cap C|$ . Now $|A \cup B| = |A| + |B| - |A \cap B|$ , and $(A \cup B) \cap C = (A \cap C) \cup (B \cap C)$ , whose size by the two-set rule is $|A \cap C| + |B \cap C| - |A \cap B \cap C|$ , because $(A \cap C) \cap (B \cap C) = A \cap B \cap C$ . Substituting gives the formula.

∎

Example— Divisible by 2, 3 or 5

How many of $1, 2, \dots, 100$ are divisible by $2$ , $3$ or $5$ ? Let $A_d$ be the multiples of $d$ ; then $|A_d| = \lfloor 100/d \rfloor$ and, for instance, $A_2 \cap A_3 = A_6$ . So the answer is

50 + 33 + 20 - 16 - 10 - 6 + 3 = 74.

The same pattern works for any number of sets: add the sizes of the sets, subtract the sizes of all pairwise intersections, add all triple intersections, and so on, with alternating signs. Here is why — and the binomial theorem returns to help.

Theorem— Theorem 8 (inclusion–exclusion, general)

For finite sets $A_1, \dots, A_n$ ,

|A_1 \cup \cdots \cup A_n| = \sum_{\varnothing \ne S \subseteq \{1, \dots, n\}} (-1)^{|S|+1} \Big| \bigcap_{i \in S} A_i \Big|.

Proof

Take an element $x$ that lies in exactly $m \ge 1$ of the sets. It is counted in $\big|\bigcap_{i \in S} A_i\big|$ exactly when $S$ is a non-empty set of indices of sets containing $x$ , and there are $\binom{m}{k}$ such $S$ of size $k$ . So the right-hand side counts $x$ exactly

\sum_{k=1}^{m} (-1)^{k+1} \binom{m}{k} = 1 - \sum_{k=0}^{m} (-1)^{k} \binom{m}{k} = 1 - 0 = 1

time, by the alternating row sum (Corollary 5). An element in none of the sets is counted $0$ times on both sides.

∎

Example— Derangements: the hat-check problem

Guests at a wedding in Addis Ababa leave $n$ hats at the door, and the hats are handed back at random. In how many of the $n!$ ways does nobody get their own hat? Such an arrangement is a derangement; call their number $D_n$ .

Let $A_i$ be the arrangements in which guest $i$ gets the right hat. If the guests in a set $S$ of size $k$ all get their own hats, the other $n - k$ hats can be arranged in $(n - k)!$ ways, and there are $\binom{n}{k}$ sets $S$ of size $k$ . By inclusion–exclusion,

|A_1 \cup \cdots \cup A_n| = \sum_{k=1}^{n} (-1)^{k+1} \binom{n}{k} (n - k)! = \sum_{k=1}^{n} (-1)^{k+1} \frac{n!}{k!},

and $D_n = n! - |A_1 \cup \cdots \cup A_n|$ , so

D_n = n! \left( 1 - \frac{1}{1!} + \frac{1}{2!} - \frac{1}{3!} + \cdots + \frac{(-1)^n}{n!} \right).

For example $D_4 = 24 \left(1 - 1 + \tfrac12 - \tfrac16 + \tfrac{1}{24}\right) = 9$ . The bracket is a partial sum of the series $\sum_k (-1)^k / k!$ , which (as you may learn with sequences and series) converges to $1/e \approx 0.3679$ , and very quickly: with eight or more guests, the fraction of arrangements that are derangements is $0.3679$ to four decimal places.

Formal mathematicsF

The proofs, checked by Lean

In Mathlib, Finset.powersetCard k s is the finite set of $k$ -element subsets of s, #s is the number of elements of s, and Nat.choose n k is $\binom{n}{k}$ . Interestingly, Mathlib defines Nat.choose by Pascal's rule — $\binom{n}{0} = 1$ , $\binom{0}{k+1} = 0$ , $\binom{n+1}{k+1} = \binom{n}{k} + \binom{n}{k+1}$ — so our counting definition becomes a theorem. First, Pascal's rule for subsets, proved exactly like the committee argument (avoid $a$ , or contain $a$ ):

pascal_subsetsLean 4Proved here from basic factsFormally verified

/-- **Pascal's rule, by counting.** Let `a` be a new element, not in `s`. A `(k + 1)`-element
subset of `insert a s` either avoids `a` — then it is a `(k + 1)`-element subset of `s` — or
contains `a` — then it is `insert a t` for exactly one `k`-element subset `t` of `s`. The two
kinds do not overlap, so their numbers add up. -/
theorem pascal_subsets {α : Type*} [DecidableEq α] {a : α} {s : Finset α} (ha : a ∉ s)
    (k : ℕ) :
    #(powersetCard (k + 1) (insert a s)) = #(powersetCard (k + 1) s) + #(powersetCard k s) := by
  rw [powersetCard_succ_insert ha, card_union_of_disjoint]
  · -- putting `a` back is one-to-one on the subsets of `s`, since none of them contains `a`
    congr 1
    apply card_image_of_injOn
    intro t ht u hu htu
    have hat : a ∉ t := fun h => ha ((mem_powersetCard.1 ht).1 h)
    have hau : a ∉ u := fun h => ha ((mem_powersetCard.1 hu).1 h)
    have := congrArg (fun v => v.erase a) htu
    simpa [erase_insert hat, erase_insert hau] using this
  · -- no subset of `s` contains `a`, so the two kinds are disjoint
    rw [disjoint_left]
    intro t ht ht'
    obtain ⟨u, -, rfl⟩ := mem_image.1 ht'
    exact ha ((mem_powersetCard.1 ht).1 (mem_insert_self a u))