Combinatorics Course Guide: Basic to Advanced
Counting is taught as formula selection and practised as pattern matching, which is exactly why students find real counting problems impossible.
A combinatorics course has to undo something before it can teach anything: the belief that counting means choosing between two formulas. That belief gets students through school exercises and defeats them on anything real.
Counting is an argument
Any combinatorics course has to start here. Most students meet the subject as permutations and combinations plus a decision about which applies. The approach works on textbook questions, which are written to be matched, and collapses on genuine problems, which are not.
The actual skill is constructing an argument: count in stages, count the complement instead, or build a correspondence with something you already know how to count. A good combinatorics course teaches that from the first week, and the formulas arrive as consequences rather than as the subject.
Bijections: the technique nobody is shown
If one idea justifies a dedicated 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.
The Erdos-Szekeres theorem is the standard worked example and repays careful study, because it shows the principle doing something genuinely non-obvious.
Inclusion-exclusion and complement counting
The principle for two, three and n sets; derangements; counting surjections; Euler's totient derived combinatorially.
The practical lesson underneath is that counting what you do not want is often far easier than counting what you do. Students resist this because it feels indirect, and then discover that the direct count has twelve cases and the complement has two.
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. They appear in the Integral Cup analysis track for recurrence problems and are standard in undergraduate combinatorics. The algebra they need comes from our algebra course.
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.
These appear constantly in RMO and INMO and are among the most satisfying techniques in the subject, because a well-chosen invariant makes an apparently hopeless problem trivial.
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 the series, and that is the honest warning to give before starting.
A student finishing a 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. Those who keep working find that somewhere in the advanced units the subject stops feeling arbitrary.
How to practise so the repertoire builds
Because a combinatorics course rewards recognition rather than procedure, how a student practises matters more here than elsewhere.
Working a problem and reading the solution builds very little. The productive routine is to attempt a problem, fail, leave it for a day, and attempt it again before looking at anything. The second attempt is where the repertoire forms, because it forces a student to try a different opening rather than the one that already failed.
Keeping a short record of techniques that worked, in the student's own words, is also unusually effective in combinatorics. The list grows slowly and becomes the thing they reach for when a problem looks unfamiliar.
Who this suits
Students from Class 9 upward through undergraduate study, with school algebra and no prior combinatorics.
Who this suits
Students from Class 9 upward through undergraduate study, with school algebra and no prior combinatorics. It pairs particularly well with our probability course, since counting is where most probability errors actually originate.
For competition students a combinatorics course is probably the highest-return single choice in the series: counting decides more AMC, IOQM and olympiad marks than any other area and is the one school teaching covers worst.
Questions people ask
Why do students find counting so hard?
Because it is taught as formula selection and practised as pattern matching. A student learns permutation and combination formulas and then tries to decide which one a problem is. Real counting problems rarely announce themselves, and the skill is constructing an argument instead.
What is a bijection argument?
Showing that the thing you want to count is in exact correspondence with something you can count easily, which gives the answer without computing it directly. It is the most elegant technique in the subject and reliably the one students have never been shown.
Is the pigeonhole principle really that useful?
Its power is out of all proportion to its statement, which is why a whole unit goes to it. The statement is obvious; the difficulty is entirely in choosing what the pigeons and holes should be, and that choice is where the mathematics lives.
Are generating functions worth the effort?
Yes, for anyone going beyond introductory competitions. They convert a counting problem into an algebra problem, so a systematic method replaces ingenuity. They are standard in undergraduate combinatorics and appear directly in competition recurrence problems.
How does combinatorics connect to the other courses?
Closely. Probability needs counting constantly, graph theory is largely combinatorics on a particular structure, number theory borrows pigeonhole and double counting, and algebra supplies the generating function machinery.
Get a study plan for this
Tell us the class and what they are working towards, and we will send a plan built around it, plus the next free trial class. No cost, and we will not pass your details on.
