PrevNext
Rare
 0/4

Catalan Numbers

Author: Mihnea Brebenel

Edit This Page
Resources
cp-algo

Well documented article.

The Catalan numbers are a sequence of positive integers that can be very useful in counting problems in combinatorics. The nn-th Catalan can be expressed as follows using binomial coeffiecients:

Cn=1n+1(2nn)=(2n)!(n+1)!n!C_n=\frac{1}{n+1}\cdot \binom{2n}{n}=\frac{(2n)!}{(n+1)!\,n!}

They also have the recurrence formula

Cn+1=i=0nCiCni for n0C_{n+1}= \sum^{n}_{i=0}{C_i \cdot C_{n-i}} \,\,\, \text{ for } n \ge 0 \\

which can also be expressed as

Cn=2(2n1)n+1Cn1C_n=\frac{2(2n-1)}{n+1} \cdot C_{n-1}

The first 55 Catalan numbers are

n012345
CnC_n11251442

Applications

The Catalan numbers can be used to represent a wide variety of things.

For example, CnC_n is equal to the number of valid parenthesis expressions of length 2n2n. Take, for instance, C3=5C_3=5:

  • ()()()
  • (())()
  • ()(())
  • ((()))
  • (()())

It's also equal to the number of full binary trees with n+1n+1 leaves. The following image shows the 55 binary trees with 44 leaves:

binary-trees

CnC_n is also the number of monotonic lattice paths along the edges of a n×nn \times n grid that don't pass above the diagonal. The paths start in the lower left corner and ends in the upper right corner.

For example, there are C4=14C_4=14 paths in a 4×44 \times 4 grid:

lattice points

The next two examples are a bit more niche, but they're still interesting to think about.

Consider a convex polygon with n+2n+2 sides divided into nn triangles by connecting vertices with non-intersecting lines. The number of different ways to divide the polygon in this way is equal to CnC_n.

Here's the particular case for n=3n=3 in which we have C3=5C_3=5:

polygons

CnC_n is also equal to the number of mountain ranges of length 2n2n consisting of nn upstrokes and nn downstrokes.

mountains

Bracket Sequences I

Focus Problem – try your best to solve this problem before continuing!

Explanation

The problem is a direct application of Catalan numbers. The answer for NN is the N/2N/2 Catalan Number.

Implementation

Time Complexity: O(N)\mathcal{O}(N)

C++

#include <iostream>
using namespace std;
const int MOD = 1e9 + 7;
const int MAXN = 1e6;
long long fac[MAXN + 1];
long long inv[MAXN + 1];

Python

MAXN = 10**6
MOD = 10**9 + 7
fac = [0] * (MAXN + 1)
inv = [0] * (MAXN + 1)
Code Snippet: Combinatorics Functions (from the module) (Click to expand)
n = int(input())

Problems

StatusSourceProblem NameDifficultyTags
LCEasy
Show TagsCatalan, Combinatorics
SPOJNormal
Show TagsCatalan, Combinatorics
CSESHard
Show TagsCatalan, Combinatorics

Module Progress:

Join the USACO Forum!

Stuck on a problem, or don't understand a module? Join the USACO Forum and get help from other competitive programmers!

PrevNext