Catalan Numbers - Algorithms for Competitive Programming 2/23/24, 2:36 PM
Last update: August 20, 2023 Translated From: [Link]
Catalan Numbers
Catalan numbers is a number sequence, which is found useful in a number of combinatorial problems, often
involving recursively-deAned objects.
This sequence was named after the Belgian mathematician Catalan, who lived in the 19th century. (In fact it
was known before to Euler, who lived a century before Catalan).
The Arst few Catalan numbers C n (starting from zero):
1, 1, 2, 5, 14, 42, 132, 429, 1430, …
Application in some combinatorial problems
The Catalan number C n is the solution for
Number of correct bracket sequence consisting of n opening and n closing brackets.
The number of rooted full binary trees with n + 1 leaves (vertices are not numbered). A rooted binary
tree is full if every vertex has either two children or no children.
The number of ways to completely parenthesize n + 1 factors.
The number of triangulations of a convex polygon with n + 2 sides (i.e. the number of partitions of
polygon into disjoint triangles by using the diagonals).
The number of ways to connect the 2n points on a circle to form n disjoint chords.
The number of non-isomorphic full binary trees with n internal nodes (i.e. nodes having at least one
son).
The number of monotonic lattice paths from point (0, 0) to point (n, n) in a square lattice of
size n × n , which do not pass above the main diagonal (i.e. connecting (0, 0) to (n, n)
).
Number of permutations of length n that can be stack sorted (i.e. it can be shown that the
rearrangement is stack sorted if and only if there is no such index i < j < k , such that
ak < ai < aj ).
The number of non-crossing partitions of a set of n elements.
[Link] Page 1 of 4
Catalan Numbers - Algorithms for Competitive Programming 2/23/24, 2:36 PM
The number of ways to cover the ladder 1 … n using n rectangles (The ladder consists of n
columns, where i th column has a height i ).
Calculations
There are two formulas for the Catalan numbers: Recursive and Analytical. Since, we believe that all the
mentioned above problems are equivalent (have the same solution), for the proof of the formulas below we will
choose the task which it is easiest to do.
Recursive formula
C0 = C1 = 1
n−1
C n = ∑ C k C n−1−k , n ≥ 2
k=0
The recurrence formula can be easily deduced from the problem of the correct bracket sequence.
The leftmost opening parenthesis l corresponds to certain closing bracket r , which divides the sequence
into 2 parts which in turn should be a correct sequence of brackets. Thus formula is also divided into 2 parts. If
we denote k = r − l − 1 , then for Axed r , there will be exactly C k C n−1−k such
′
bracket sequences. Summing this over all admissible k s , we get the recurrence relation on C n .
You can also think it in this manner. By deAnition, C n denotes number of correct bracket sequences. Now,
the sequence may be divided into 2 parts of length k and n − k , each of which should be a correct
bracket sequence. Example :
()(()) can be divided into () and (()) , but cannot be divided into ()( and ()) . Again
′
summing over all admissible k s , we get the recurrence relation on C n .
C++ implementation
const int MOD = ....
const int MAX = ....
int catalan[MAX];
void init() {
catalan[0] = catalan[1] = 1;
for (int i=2; i<=n; i++) {
catalan[i] = 0;
for (int j=0; j < i; j++) {
catalan[i] += (catalan[j] * catalan[i-j-1]) % MOD;
[Link] Page 2 of 4
Catalan Numbers - Algorithms for Competitive Programming 2/23/24, 2:36 PM
if (catalan[i] >= MOD) {
catalan[i] -= MOD;
}
}
}
}
Analytical formula
1 2n
Cn = ( )
n+1 n
n
(here ( k ) denotes the usual binomial coeScient, i.e. number of ways to select k objects from
set of n objects).
The above formula can be easily concluded from the problem of the monotonic paths in square grid. The total
2n
number of monotonic paths in the lattice size of n × n is given by ( n ) .
Now we count the number of monotonic paths which cross the main diagonal. Consider such paths crossing
the main diagonal and And the Arst edge in it which is above the diagonal. ReTect the path about the diagonal
all the way, going after this edge. The result is always a monotonic path in the grid (n − 1) × (n + 1)
. On the other hand, any monotonic path in the lattice (n − 1) × (n + 1) must
intersect the diagonal. Hence, we enumerated all monotonic paths crossing the main diagonal in the lattice
n×n .
2n
The number of monotonic paths in the lattice (n − 1) × (n + 1) are (n−1) .
Let us call such paths as "bad" paths. As a result, to obtain the number of monotonic paths which do not cross
the main diagonal, we subtract the above "bad" paths, obtaining the formula:
2n 2n 1 2n
Cn = ( )−( )= ( ), n ≥ 0
n n−1 n+1 n
Reference
Catalan Number by Tom Davis
Practice Problems
[Link] Page 3 of 4
Catalan Numbers - Algorithms for Competitive Programming 2/23/24, 2:36 PM
Codechef - PANSTACK
Spoj - Skyline
UVA - Safe Salutations
Codeforces - How many trees?
SPOJ - FUNPROB
LOJ - 1170 - Counting Perfect BST
UVA - 12887 - The Soldier's Dilemma
Contributors:
likecs (58.95%) jakobkogler (9.47%) turfaa (8.42%) adamant-pwn (7.37%) madhur4127 (4.21%)
gabrielsimoes (4.21%) deji725 (2.11%) Morass (2.11%) dufferzafar (1.05%) sureyeaah (1.05%)
pulkit-singhal (1.05%)
[Link] Page 4 of 4