Catalan Numbers

Introduction

In this chapter, we study Catalan numbers, one of the most important sequences in combinatorics.

They appear in many counting problems involving recursive structures, balanced objects, and non-crossing configurations.

The first few Catalan numbers are:

1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786, 208012, 742900, 2674440, 9694845, \ldots

Solve these external problems (e.g., from Codeforces) to reinforce the lesson material:

2674440

9694845

…

The Catalan number $C_n$ counts many different combinatorial objects. Some of the most famous interpretations are:

the number of correct bracket sequences with $n$ opening and $n$ closing brackets;
the number of rooted full binary trees with $n+1$ leaves;
the number of ways to fully parenthesize $n+1$ factors;
the number of triangulations of a convex polygon with $n+2$ sides;
the number of ways to connect $2n$ points on a circle using $n$ non-intersecting chords;
the number of monotone lattice paths from $(0,0)$ to $(n,n)$ that never go above the main diagonal;
the number of non-crossing partitions of a set of $n$ elements.

These are very different problems, but they all lead to the same sequence.

Catalan numbers are defined recursively by:

C_0 = 1

and for $n \geq 1$ ,

C_n = \sum_{k=0}^{n-1} C_k \cdot C_{n-1-k}

Catalan numbers also have a closed formula:

C_n = \frac{1}{n+1} \binom{2n}{n}, \quad n \geq 0