Catalan numbers show up in problems that never mention them. A problem asks how many ways to do something. You compute the answers for , , and objects, and the list reads . That sequence is the sign. This guide gives the formula, one proof you can reproduce, and the situations that turn out to be Catalan.
The numbers
The th Catalan number is
The first values, starting at , are . They obey the recursion
The recursion is the thing to recognise. If you split an object at its first piece, and the two sides are smaller objects of the same kind, you are probably counting Catalan numbers.
What they count
All of these have objects, and the fact that they are the same count is the point.
- Balanced brackets. Strings of opening and closing brackets in which every prefix has at least as many openings as closings. For there are : , , , and .
- Paths below a diagonal. Walks from to with steps right and up that never go above the line .
- Triangulations. The number of ways to cut a convex polygon with sides into triangles using non-crossing diagonals. A hexagon has triangulations and an octagon has .
- Non-crossing handshakes. people sit round a table and shake hands in pairs so that no two handshakes cross. For people there are ways.
- Ticket queues. A cinema sells tickets for coins, and people pay with a coin and with a coin, one at a time. The seller starts with no change and must always be able to give it. The number of valid orders of arrival is . For that is .
Watch the shift of on triangulations. A polygon with sides has triangulations.
Why the recursion works: brackets
Take a valid bracket string of length . It starts with an opening bracket. Find the closing bracket that matches it. Everything inside is a valid string of some length , counted by , and everything after is a valid string of length , counted by . So the string looks like inside after, and the pair of smaller strings determines it. Summing over from to gives the recursion. The same split works on triangulations if you fix one side and look at the triangle on it, and on handshakes if you look at who person number shakes hands with.
Why the formula works: reflection
There are walks from to with right and up steps. Some of them go above the line , which means they touch the line . Take a bad walk, find the first time it touches , and flip every step after that point, swapping right with up. The flipped walk ends at instead. This is a bijection between bad walks and all walks ending at , and there are of those. So
Two facts make this work. Every walk to touches , because changes by at each step, starts at and ends at . And the flip is its own inverse, since the first touching point does not move, so it matches bad walks to walks ending at one to one. For the algebra, , so . The flip is the idea. It is a bijection, the same kind of argument as the one that proves .
A worked example: the cinema queue
Count the queues of people with a -coin and people with a -coin, in which the seller never runs short.
Write for a person with a and for a person with a . The condition is that in every prefix there are at least as many as . The valid strings are , , , and . That is , which is . Total arrangements are . Using the reflection count, the bad ones number , and .
Now take five people with a -coin and five with a -coin. There are arrangements, and of them are bad, so are valid. The same as the people at the round table.
How to spot a Catalan problem
- The counts go 1, 2, 5, 14. Compute small cases first. This sequence is a strong clue, and or are different problems.
- A prefix condition. "At every point, there are at least as many of one thing as the other." That is a ballot-style condition and the reflection argument counts it.
- Non-crossing. Handshakes or chords that must not cross, and any bracketing of a product with a fixed order.
- A recursion that splits at the first piece. Two smaller copies, sizes adding up to one less.
One surprising fact
is odd exactly when is one less than a power of . So , , and are odd, and every Catalan number in between is even. If a problem asks about the parity of a count, compare it with this list before doing any work.
What to do with it
In a contest you will mostly notice that your answers for small read , and then prove that your problem obeys the recursion. That gives you the formula. The first-piece split and the reflection count are two different ways of counting the same set, which is the heart of double counting.
Try it on a problem you can state yourself. Pick a family of objects, count it for to by hand, and see whether the list matches. The problem archive holds the counting problems that go with this.
Related guides
- Constructive vs complementary counting: which one to reach forTwo ways to count the same set, and one question that tells you which is cheaper. The signals, the worked pair, and the trap where the obvious tell lies to you.
- EGMO 2026 Problem 1: solution, and four rectangles that isolate a cellA full solution to EGMO 2026 Problem 1: the four-cell construction, the parity proof that every board beats it, and the signal in the statement.
- How to build a problem-solving notebook that actually worksMost problem notebooks are copied solutions nobody reopens. Index yours by the clue in the statement, not by topic, and test it from the clue side.
- How a double counting proof is actually builtDouble counting proofs are always the same three steps, and only one of them is hard. The skeleton, five worked examples, and where they go wrong.
- Generating functions: turning a counting problem into a productGenerating functions explained as a method: one factor per constraint, multiply, read the coefficient. The dictionary, and how to extract by hand.
Techniques in this guide
- Double CountingCount it twice, set the answers equal.
Competitions this guide helps with
- MATHCOUNTSfour rounds: Sprint (30 problems), Target (8 problems in four pairs), Team (10 problems) and the oral Countdown · Sprint 40 minutes; Target 6 minutes a pair; Team 20 minutes
- Pascal, Cayley and Fermat25 questions: multiple choice in Parts A and B, and a whole number from 0 to 99 in Part C · 60 minutes
- UKMT Intermediate Challenge25 multiple-choice questions · 60 minutes
- Australian Mathematics Competition30 questions: 25 multiple choice, then 5 with a whole-number answer · 75 minutes for the secondary divisions, 60 for primary
- SMO JuniorRound 1: multiple-choice and short-answer questions of equal weight. Round 2: full written solutions · 2.5 hours for Round 1, 3 hours for Round 2
Train it on Lemma
Every technique here is taught explicitly, in order. 128 lessons, 1237 curated problems and unlimited generated practice at six difficulties. Free to start, no card, and the paid plan opens with 3 free days.
Find your level