Lemma › Guides › Catalan numbers in competition math: what they count
Guide

Catalan numbers in competition math: what they count

Catalan numbers show up in problems that never mention them. A problem asks how many ways to do something. You compute the answers for 11, 22, 33 and 44 objects, and the list reads 1,2,5,141, 2, 5, 14. 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 nnth Catalan number is

Cn=1n+1(2nn).C_n = \frac{1}{n+1}\binom{2n}{n}.

The first values, starting at n=0n = 0, are 1,1,2,5,14,42,132,4291, 1, 2, 5, 14, 42, 132, 429. They obey the recursion

Cn+1=C0Cn+C1Cn−1+⋯+CnC0.C_{n+1} = C_0 C_n + C_1 C_{n-1} + \cdots + C_n C_0.

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 CnC_n objects, and the fact that they are the same count is the point.

Watch the shift of 22 on triangulations. A polygon with n+2n + 2 sides has CnC_n triangulations.

Why the recursion works: brackets

Take a valid bracket string of length 2n+22n + 2. It starts with an opening bracket. Find the closing bracket that matches it. Everything inside is a valid string of some length 2i2i, counted by CiC_i, and everything after is a valid string of length 2(n−i)2(n - i), counted by Cn−iC_{n-i}. So the string looks like (( inside )) after, and the pair of smaller strings determines it. Summing over ii from 00 to nn 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 11 shakes hands with.

Why the formula works: reflection

There are (2nn)\binom{2n}{n} walks from (0,0)(0,0) to (n,n)(n,n) with right and up steps. Some of them go above the line y=xy = x, which means they touch the line y=x+1y = x + 1. Take a bad walk, find the first time it touches y=x+1y = x + 1, and flip every step after that point, swapping right with up. The flipped walk ends at (n−1,n+1)(n - 1, n + 1) instead. This is a bijection between bad walks and all walks ending at (n−1,n+1)(n - 1, n + 1), and there are (2nn−1)\binom{2n}{n-1} of those. So

Cn=(2nn)−(2nn−1).C_n = \binom{2n}{n} - \binom{2n}{n-1}.

Two facts make this work. Every walk to (n−1,n+1)(n-1, n+1) touches y=x+1y = x + 1, because y−xy - x changes by 11 at each step, starts at 00 and ends at 22. And the flip is its own inverse, since the first touching point does not move, so it matches bad walks to walks ending at (n−1,n+1)(n-1, n+1) one to one. For the algebra, (2nn−1)=nn+1(2nn)\binom{2n}{n-1} = \frac{n}{n+1}\binom{2n}{n}, so Cn=(2nn)(1−nn+1)=1n+1(2nn)C_n = \binom{2n}{n}\left(1 - \frac{n}{n+1}\right) = \frac{1}{n+1}\binom{2n}{n}. The flip is the idea. It is a bijection, the same kind of argument as the one that proves (nk)=(nn−k)\binom{n}{k} = \binom{n}{n-k}.

A worked example: the cinema queue

Count the queues of 33 people with a 55-coin and 33 people with a 1010-coin, in which the seller never runs short.

Write FF for a person with a 55 and TT for a person with a 1010. The condition is that in every prefix there are at least as many FF as TT. The valid strings are FFFTTTFFFTTT, FFTFTTFFTFTT, FFTTFTFFTTFT, FTFFTTFTFFTT and FTFTFTFTFTFT. That is 55, which is C3C_3. Total arrangements are (63)=20\binom{6}{3} = 20. Using the reflection count, the bad ones number (62)=15\binom{6}{2} = 15, and 20−15=520 - 15 = 5.

Now take five people with a 55-coin and five with a 1010-coin. There are (105)=252\binom{10}{5} = 252 arrangements, and (104)=210\binom{10}{4} = 210 of them are bad, so 4242 are valid. The same as the 1010 people at the round table.

How to spot a Catalan problem

One surprising fact

CnC_n is odd exactly when nn is one less than a power of 22. So C0=1C_0 = 1, C1=1C_1 = 1, C3=5C_3 = 5 and C7=429C_7 = 429 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 nn read 1,2,5,141, 2, 5, 14, 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 n=1n = 1 to 44 by hand, and see whether the list matches. The problem archive holds the counting problems that go with this.

Related guides

Techniques in this guide

Competitions this guide helps with

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