Combinatorics

Problems first

Attempt these before you open a book or a video. Write the argument in the work box and the conclusion in the answer box. Check counts the problem only when both pass, and it does not open the solution. The solution stays locked for twenty minutes after you start the timer.

Prerequisites

• Proof and Logic

What this actually is

Combinatorics on this page means counting, bijections, generating functions, and the first graph-theoretic facts you need in order to not be helpless on an olympiad or a Putnam A1. The binomial theorem, inclusion–exclusion, pigeonhole, and recurrence relations are the whole elementary theory. Ordinary generating functions turn linear recurrences into algebra. A graph is a set of vertices and edges; trees, bipartite graphs, and the handshake lemma are the part you must be able to prove in a paragraph.

Lehman, Leighton, and Meyer’s Mathematics for Computer Science is free and contains a serious counting and graph section. It is the working text. Wilf’s generatingfunctionology is the right specialized book; the Penn URL that used to host it did not return a stable copy in this check, so it is not linked. Use the generating-function chapters of the MIT notes instead. AIME and Putnam counting problems are the ceiling.

A counting argument that does not say what is being counted, and in what order, is a guess with binomial coefficients glued on.

Core results

Statements only. Write the argument before you reveal it. A revealed proof you did not attempt is a paragraph you will not be able to rebuild at 2am.

1. Binomial theorem. \((x+y)^n=\sum_{k=0}^n\binom{n}{k}x^{n-k}y^k\). Pascal’s recurrence \(\binom{n}{k}=\binom{n-1}{k}+\binom{n-1}{k-1}\) has a bijective proof.

   I wrote a proof. Reveal.

2. Inclusion–exclusion and pigeonhole. The size of a union is the alternating sum of the sizes of intersections. If more than \(kn\) pigeons sit in \(n\) holes, some hole has at least \(k+1\) pigeons.

   I wrote a proof. Reveal.

3. Recurrences and generating functions. The ordinary generating function of a sequence turns a linear recurrence into a rational function. The Fibonacci generating function is \(x/(1-x-x^2)\). Partial fractions extract coefficients.

   I wrote a proof. Reveal.

4. Graphs. Handshake lemma. A tree on \(n\) vertices has \(n-1\) edges and is connected and acyclic; any two of those properties imply the third, among the usual list. A graph is bipartite if and only if it has no odd cycle.

   I wrote a proof. Reveal.

5. Double counting. If you count a set of pairs in two ways, you get an identity. This is the source of the handshake lemma, of \(\sum k\binom{n}{k}=n2^{n-1}\), and of most olympiad counting proofs that look like magic.

   I wrote a proof. Reveal.

The ladder

Four rungs, in order. Do not skip a rung because the next one looks more serious.

Tier 0 / First contact

Watch or read once. Do not study from this.

Lehman, Leighton, Meyer, the contents page of the PDF
Read once, do not study from this. Find the counting and graph chapters. Then work those chapters and skip the rest until you want it.

Tier 1 / Main text

The thing you work through.

Mathematics for Computer Science, Lehman, Leighton, Meyer
Free. The counting, induction, and graph chapters are the main text. Better than a paid combinatorics survey you will not finish, because the problems are inline and the book is complete.

Tier 2 / Hard problems

The problem book.

AIME counting problems
The hard-problem layer. Filter by combinatorics using the AoPS index or Po-Shen Loh: https://live.poshenloh.com/

Tier 3 / The ceiling

The hardest questions that exist at this level.

Putnam combinatorics, Borisov’s list
The ceiling at this level. Generatingfunctionology is the right extra book if you find a legal copy you can verify yourself; a stable free URL was not confirmed here.

• Tier 0 done once, then closed.
• Main text worked, exercises written.
• Hard-problem set written up.
• Ceiling problems attempted under the timer.
• Mastery gate passed.

Hardest questions

Names and links. The problem text stays on the source site. Copyrighted contest problems are not copied here. What follows is where they are and why they hurt.

1. AIME counting, problems 10–15
   Overcounting is the entire difficulty. The arithmetic is nothing.
2. Po-Shen Loh, combinatorics at the top rating
   Sorted, so you cannot hide in algebra.
3. Borisov, combinatorics
   Putnam counting problems are proofs, not three-digit answers.
4. Handshake lemma and the tree theorem, blank page
   If these are not instant, the later problems will be folklore you cannot use.
5. Fibonacci generating function, derived
   One derivation teaches the method. A memorized Binet formula does not.

Mastery gate

Pass: handshake lemma, binomial theorem, and inclusion–exclusion for three sets, from memory, plus five AIME counting problems numbered 8 or higher and two Putnam combinatorics problems with full proofs. Fail if a count does not name the set being counted.

I passed this gate with written solutions.

Diagrams

Escalating sets

Five sets. Finish a set before you touch the next. Full sentences, not a circled answer.

Set 1. Counts

1. Derive \(\binom{n}{2}\).
2. Pascal’s identity, bijectively.
3. Binomial theorem for \(n=3\), expanded by hand, then the general proof.
4. How many subsets does an \(n\)-set have? Two proofs.
5. \(\sum k\binom{n}{k}=n2^{n-1}\), by double counting.

Set 2. Inclusion and pigeons

1. Integers from 1 to 100 divisible by 2, 3, or 5.
2. Derangements of 3 items, by inclusion–exclusion.
3. Pigeonhole: among 5 integers, two have the same remainder mod 4.
4. Five points in a square of side 1; two are at most \(\sqrt{2}/2\) apart. Prove it.
5. State inclusion–exclusion for three sets from memory.

Set 3. Recurrences

1. Fibonacci recurrence, first ten terms, and the generating function.
2. Number of binary strings of length \(n\) with no two consecutive 1s. Find the recurrence.
3. Solve \(a_n=3a_{n-1}\), \(a_0=2\).
4. A linear recurrence of order 2, characteristic polynomial, one example.
5. Partial fractions of \(x/(1-x-x^2)\), as far as you are willing to go.

Set 4. Graphs

1. Handshake lemma.
2. A tree has \(n-1\) edges.
3. Prove bipartite iff no odd cycle.
4. Draw a connected graph with exactly one cycle and count its edges.
5. Euler’s formula \(V-E+F=2\) for a connected plane graph, proved by induction or clearly cited as not yet proved.

Set 5. Ceiling

1. Five AIME counting problems.
2. Two Putnam combinatorics proofs.
3. Generating function of the no-consecutive-1s strings.
4. Oral handshake lemma.
5. One double-counting identity you invent and then prove.

Return bank

Ten problems to meet again. Logging a writeup schedules them at 1 day, 7 days, and 30 days in this browser.

1. \(\binom{n}{2}\) derived. Log a writeup
2. Handshake lemma. Log a writeup
3. Inclusion–exclusion, 2, 3, 5 up to 100. Log a writeup
4. Pascal’s identity. Log a writeup
5. Fibonacci generating function. Log a writeup
6. No two consecutive ones. Log a writeup
7. Bipartite iff no odd cycle. Log a writeup
8. Tree edge count. Log a writeup
9. \(\sum k\binom{n}{k}\). Log a writeup
10. One Putnam counting problem. Log a writeup

Oral pass

Derive the binomial coefficient, prove the handshake lemma, and state inclusion–exclusion for three sets. No notes.

I explained this from a blank page, out loud, with no notes.