Combinatorics: Basic to Advanced

Counting is an argument, not a formula choice

Most students meet combinatorics as two formulas and a decision about which to apply. That approach works on textbook exercises and collapses on anything real, because genuine counting problems do not announce which formula they are.

The actual skill is constructing an argument: count in stages, count the complement instead, build a correspondence with something you already know how to count. This course teaches that from the first week, and the formulas arrive as consequences.

Bijections: the technique nobody is shown

If one idea justifies this course, it is this one.

A bijection shows that the set you want to count is in exact correspondence with a set you can count easily. You then know the answer without ever computing the original directly. Lattice paths, Catalan numbers, balanced bracket sequences, triangulations of a polygon — a surprising number of apparently unrelated problems turn out to be the same problem wearing different clothes.

Students find this genuinely delightful, and almost none have encountered it before.

Pigeonhole: trivial statement, enormous reach

If you put more objects than boxes, some box holds two. That is the whole theorem, and an entire unit is devoted to it.

The reason is that the statement is not the difficulty — choosing the pigeons and the holes is, and that choice is the entire mathematical content. A problem about any five points in a square, or about remainders, or about a sequence containing a monotone subsequence, becomes short once you see what to count and where to put it. Erdos-Szekeres is the standard example and repays careful study.

From recursion to generating functions

Recursion is the workhorse: decompose a configuration into smaller ones, write the recurrence, solve it. Most students can learn to set up a recurrence reliably, and that alone handles a large class of problems.

Generating functions are the systematic version. They convert a counting problem into algebra, so that ingenuity is replaced by method — multiply the right series, read off a coefficient. They are not easy and they repay the effort: the Integral Cup analysis track uses them directly for recurrence problems, and they are standard in undergraduate combinatorics.

Invariants: answering "is this possible?"

A distinct class of problem asks not how many but whether a configuration can be reached at all. These resist counting entirely.

The standard approach is to find an invariant: a quantity unchanged by every permitted move. If the start and target differ in that quantity, the task is impossible, and the proof is often three lines. Colouring arguments and parity are the usual sources. Monovariants — quantities that only ever move one way — answer the companion question of whether a process must terminate.

The hardest material, and the most rewarding

Double counting, the extremal principle, Ramsey-type arguments and an introduction to the probabilistic method.

Double counting — computing one quantity in two different ways and equating the results — produces identities that would be painful to prove any other way. The probabilistic method is stranger still: proving an object exists by showing a random one has a positive chance of working, without ever constructing it. Students meeting that for the first time usually object that it cannot be legitimate, which is the right instinct and the right moment to examine the argument closely.

Why this course rewards persistence

Combinatorics has the least transferable technique of any subject in this series, and that is the honest warning to give before starting.

A student finishing the number theory course can attack an unfamiliar number theory problem with a short list of standard moves. Combinatorics offers fewer such guarantees: each problem can require seeing the particular structure in front of you. What builds is a repertoire of recognitions rather than a procedure, and repertoire accumulates slowly and then quite suddenly becomes useful.

Students who expect steady weekly progress tend to be discouraged around the middle of the course. Those who keep working problems find that somewhere in the advanced units the subject stops feeling arbitrary.

Who this suits

Students from Class 9 upward through undergraduate study, with school algebra and no prior combinatorics. It pairs particularly well with the probability course, since counting is where most probability errors actually originate.

Classes are live and online in groups of at most eight, with written work corrected individually.