Skip to content

Catalan Numbers

Introduction

Catalan numbers frequently appear in various counting problems. The Belgian mathematician Eugène Charles Catalan discovered this sequence in 1958 while studying the counting of bracket sequences, hence the name. The Qing dynasty mathematician Ming Antu had already discovered this sequence as early as the 1730s.

Catalan numbers satisfy the following recurrence relation:

\[ C_n = \begin{cases} 1, & n = 0, \\ \sum_{i=0}^{n-1} C_{i}C_{n-1-i}, & n > 0. \end{cases}\tag{1} \]

The first few terms of the sequence are: (OEIS: A000108, index starting from \(0\))

\[ 1,1,2,5,14,42,132,429,1430,\ldots \]

Applications

The recurrence relation of Catalan numbers \(C_n\) has a natural recursive structure: the counting problem \(C_n\) of size \(n\) can be split into two subproblems of sizes \(i\) and \((n-1-i)\) by enumerating the dividing point. This recurrence relation makes Catalan numbers widely appear in various problems with similar recursive structures.

  • Path Counting Problem: There is a grid of size \(n\times n\), with the bottom-left corner at \((0, 0)\) and the top-right corner at \((n, n)\). Starting from the bottom-left corner, each step can only move right or up by one unit. The total number of paths to reach the top-right corner without going above the diagonal \(y=x\) (but touching is allowed) is \(C_n\).

    Proof

    Let the number of such paths be \(T_n\). Consider the case \(n \ge 2\). Let the point where the path first reaches the diagonal \(y=x\) be \((k,k)~(k \in [1,n])\). Consider the paths from \((0,0)\) to \((k,k)\) that do not cross the diagonal (cannot touch) except at the start and end points.

    catalan2

    As shown in the figure, the first step of these paths must be to the right, from \((0,0)\) to \((1,0)\); the last step must be upward, from \((k,k-1)\) to \((k,k)\). Therefore, these paths are exactly the paths from \((1,0)\) to \((k,k-1)\) that do not cross the line \(y=x-1\), and the number of such paths is \(T_{k-1}\). Meanwhile, the number of valid paths from \((k,k)\) to \((n,n)\) is \(T_{n-k}\). By the multiplication principle, the number of paths that first touch the diagonal at \((k,k)\) is \(T_{k-1} T_{n-k}\). Enumerating all possibilities for \(k\), the total number of valid paths is

    \[ T_n = \sum_{k=1}^n T_{k-1}T_{n-k}. \]

    Substituting \(k=i+1\) reveals that this is exactly the recurrence relation for Catalan numbers. Since \(T_0=1\), we have \(T_n = C_n\).

  • Non-intersecting Chords in a Circle Problem: There are \(2n\) points on a circle. The number of ways to pair these points such that the resulting \(n\) chords do not intersect is \(C_n\).

    Proof

    Let the number of ways for \(2n\) points be \(T_n\). Label the \(2n\) points clockwise as \(1,2,\ldots,2n\). Since the chords do not intersect, point \(1\) can only connect to even-numbered points; otherwise, the odd number of points between them cannot be paired without crossing the chord. If point \(1\) is connected to \(2k~(k\in[1,n])\), then there are \(2k-2\) points on the left and \(2n-2k\) points on the right. By the multiplication principle, the number of such pairings is \(T_{k-1}T_{n-k}\). Therefore, enumerating \(k\), we have \(T_n = \sum_{k=1}^n T_{k-1} T_{n-k}\). Setting \(k=i+1\) yields the Catalan recurrence. Since \(T_0=1\), we have \(T_n=C_n\).

  • Triangulation Counting Problem: The number of ways to triangulate a convex \((n+2)\)-gon into triangles without intersecting diagonals is \(C_n\).

    Proof

    Let the number of triangulations of an \((n+2)\)-gon be \(T_n\). First, fix one edge \((1,n+2)\) as the base edge; it must belong to a triangle. Let the third vertex of this triangle be \(k~(k\in[2,n+1])\). Then, the original convex polygon is divided into three parts:

    • Triangle \((1,k,n+2)\).
    • A \(k\)-gon with vertices \(1\sim k\).
    • An \((n+3-k)\)-gon with vertices \(k\sim (n+2)\).

    The latter two parts are subproblems. Thus, we have the recurrence

    \[ T_n = \sum_{k=2}^{n+1} T_{k-2}T_{n+1-k}. \]

    Setting \(k=i+2\) yields the Catalan recurrence. Since \(T_0=T_1=1\), we have \(T_n=C_n\).

  • Binary Tree Counting Problem: The number of distinct full binary trees with \(n\) internal nodes is \(C_n\). Equivalently, the number of distinct full binary trees with \(n\) internal nodes is \(C_{n}\).

    Proof

    Let the number of binary trees with \(n\) nodes be \(T_n\). Choose a root node and enumerate the sizes of the left and right subtrees. Let the left subtree size be \(i\in[0,n-1]\), then the right subtree size is \((n-1-i)\). Both subtrees are subproblems, so we have the recurrence

    \[ T_n = \sum_{i=0}^{n-1}T_iT_{n-1-i}. \]

    This is the Catalan recurrence. Since \(T_0=T_1=1\), we have \(T_n=C_n\).

  • Bracket Sequence Counting Problem: The number of valid bracket sequences consisting of \(n\) pairs of parentheses is \(C_n\).

    Proof

    Relate to the path counting problem. Treat a left parenthesis as moving up and a right parenthesis as moving right. A valid bracket sequence means that at any position, the number of left parentheses is not less than the number of right parentheses. This is equivalent to, at any step in the path, the number of upward moves is not less than the number of rightward moves. Therefore, there is a bijection between valid bracket sequences and valid paths. The number of valid bracket sequences is also \(C_n\).

  • Stack Permutation Counting Problem: For a stack (infinite size) with push sequence \(1,2,3, \ldots ,n\), the number of valid pop sequences is \(C_n\).

    Proof

    Relate to the bracket sequence counting problem. Treat a push as a left parenthesis and a pop as a right parenthesis. At any moment, the number of pushes is not less than the number of pops. Therefore, there is a bijection between valid pop sequences and valid bracket sequences. The number of valid pop sequences is also \(C_n\).

  • Sequence Counting Problem: For a sequence \(a_1,a_2, \ldots ,a_{2n}\) consisting of \(n\) \(+1\)s and \(n\) \(-1\)s, the number of sequences such that the partial sums satisfy \(a_1+a_2+ \ldots +a_k \geq 0~(k=1,2,3, \ldots ,2n)\) is \(C_n\).

    Proof

    Relate to the bracket sequence counting problem. Treat \(+1\) as a left parenthesis and \(-1\) as a right parenthesis. At any moment, the number of \(+1\)s is not less than the number of \(-1\)s. Therefore, there is a bijection between valid sequences and valid bracket sequences. The number of valid sequences is also \(C_n\).

Although this recurrence relation is widely applicable, direct computation has high complexity, so simpler formulas are needed.

Common Forms

Catalan numbers have the following common expressions:

\[ C_n = \frac{1}{n+1}\binom{2n}{n} = \dfrac{(2n)!}{n!(n+1)!},~ n\ge 0. \tag{2} \]
\[ C_n = \binom{2n}{n} - \binom{2n}{n+1},~n \ge 0. \tag{3} \]
\[ C_n = \frac{(4n-2)}{n+1}C_{n-1},~ n > 0,~ C_0 = 1. \tag{4} \]

These forms of Catalan numbers can be computed efficiently: the first two forms reduce the problem to computing factorials and binomial coefficients, while the third form provides a recurrence for sequential computation.

For these three common forms, this article provides two proof methods.

Algebraic Derivation

Deriving the above expressions for Catalan numbers algebraically involves two steps. First, verify that the three forms are equivalent.

Proof of equivalence of expressions \((2)\sim(4)\)

It suffices to show that expression \((3)\) can be transformed into the factorial form in expression \((2)\):

\[ \begin{aligned} C_n &= \binom{2n}{n} - \binom{2n}{n+1} \\ &= \frac{(2n)!}{n!n!} - \frac{(2n)!}{(n-1)!(n+1)!} \\ &= \frac{(2n)!}{n!n!}\left(1 - \frac{n!}{(n-1)!(n+1)}\right) \\ &= \frac{(2n)!}{n!n!}\left(1- \frac{n}{n+1}\right) \\ &= \dfrac{(2n)!}{n!(n+1)!}. \end{aligned} \]

Also, expression \((4)\) can be transformed into the factorial form in expression \((2)\):

\[ C_n = \prod_{i=1}^n\frac{(4i-2)}{i+1} = \prod_{i=1}^n\frac{2i(2i-1)}{i(i+1)} = \dfrac{(2n)!}{n!(n+1)!}. \]

Therefore, the three expressions are equivalent.

Next, verify that these forms indeed satisfy the Catalan recurrence \((1)\). To do this, consider using generating functions to directly solve recurrence \((1)\).

Solving recurrence \((1)\) using generating functions

Consider the ordinary generating function \(C(x)=\sum_{n=0}^{\infty}C_nx^n\) for Catalan numbers. Since the Catalan recurrence resembles a convolution, we construct an equation for \(C(x)\) using convolution:

\[ \begin{aligned} C(x)&=\sum_{n=0}^{\infty}C_nx^n\\ &=1+\sum_{n=1}^{\infty}\left(\sum_{i=0}^{n-1}C_iC_{n-i-1}\right)x^{n}\\ &=1+x\sum_{n=1}^{\infty}\sum_{i=0}^{n-1}C_ix^iC_{n-i-1}x^{n-i-1}\\ &=1+x\sum_{i=0}^{\infty}C_ix^i\sum_{j=0}^{\infty}C_jx^j\\ &=1+xC^2(x). \end{aligned} \]

Here, the second-to-last equality swaps the order of summation and sets \(j=n-1-i\). Solving, we get:

\[ C(x)=\dfrac{1\pm \sqrt{1-4x}}{2x} = \frac{2}{1\mp \sqrt{1-4x}}. \]

The initial condition \(C_0=1\) implies \(C(0)=1\). Substituting and checking shows that the only feasible solution is

\[ C(x) = \dfrac{1- \sqrt{1-4x}}{2x}. \]

Next, expand this into a power series. Using the power series expansion of \((1+x)^a\):

\[ \sqrt{1-4x} = \sum_{n=0}^{\infty} \dfrac{\left(\frac{1}{2}\right)_{-n}}{n!}(-4x)^n, \]

where \(\left(\dfrac{1}{2}\right)_{-n}\) is the falling factorial power:

\[ \begin{aligned} \left(\frac{1}{2}\right)_{-n} &= \prod_{k=0}^{n-1}\left(\dfrac{1}{2}-k\right) = \dfrac{1}{2^n}\prod_{k=1}^{n-1}(1-2k) = \dfrac{(-1)^{n-1}}{2^n}\prod_{k=1}^{n-1}(2k-1)\\ &= \dfrac{(-1)^{n-1}}{2^{2n-1}}\prod_{k=1}^{n-1}\dfrac{(2k-1)2k}{k} = \dfrac{(-1)^{n-1}}{2^{2n-1}}\dfrac{(2n-2)!}{(n-1)!}. \end{aligned} \]

Substituting into the expression for \(C(x)\):

\[ \begin{aligned} C(x) &= \dfrac{1}{2x}\left(1-\sum_{n=0}^{\infty} \dfrac{\left(\frac{1}{2}\right)_{-n}}{n!}(-4x)^n\right)\\ &= -\dfrac{1}{2x}\sum_{n=1}^\infty \dfrac{(-4x)^n}{n!}\left(\frac{1}{2}\right)_{-n} \\ &= -\dfrac{1}{2x}\sum_{n=1}^\infty \dfrac{(-4x)^n}{n!}\dfrac{(-1)^{n-1}}{2^{2n-1}}\dfrac{(2n-2)!}{(n-1)!} \\ &= \sum_{n=1}^{\infty}\dfrac{(2n-2)!}{(n-1)!n!}x^{n-1}\\ &= \sum_{n=0}^{\infty}\dfrac{(2n)!}{n!(n+1)!}x^n. \end{aligned} \]

Thus, we obtain expression \((2)\) for \(C_n\).

Combinatorial Interpretation

Since Catalan numbers have clear combinatorial meanings, these forms can also be proven using purely combinatorial counting. This section provides combinatorial proofs for each of the three expressions.

Proof of expression \((2)\)

Consider the sequence counting problem. For any sequence \(\{a_i\}_{i=1}^{2n}\) consisting of \(\pm 1\), define its partial sums \(S_i = \sum_{j=1}^{i}a_i\), and define its exceedance as the number of indices where \(S_i < 0\) and \(a_i = -1\). An exceedance of \(0\) is equivalent to the sequence being valid; the exceedance can range from \([0,n]\), giving \((n+1)\) possible values. We need to prove that the number of sequences with different exceedances is actually the same.

To do this, construct a mapping \(f\) from sequences with exceedance \(e > 0\) to sequences with exceedance \((e-1)\). For a sequence \(\{a_i\}\) with exceedance \(e > 0\), let index \(k\) be the smallest index such that \(S_i = 0\) and \(a_i = +1\). Swap the subsequences to the left and right of \(a_k\) to obtain the sequence \(\{a'_i\}\):

\[ a_{k+1},a_{k+2},\cdots,a_{2n},a_k,a_{1},a_{2},\cdots,a_{k-1}. \]

Since the partial sum sequence corresponding to the part to the right of \(a_k\) in the original sequence remains unchanged after swapping, its contribution to the exceedance also remains unchanged. For the part to the left of \(a_k\) in the original sequence, their corresponding partial sums all increase by \(1\) after swapping. Therefore, their contribution to the exceedance decreases, and the decrease is exactly equal to the number of indices in the original left part where \(S_i=-1\) and \(a_i=-1\). Because the choice of \(a_k\) ensures there is exactly one such index, the exceedance of sequence \(\{a'_i\}\) is exactly \((e-1)\). That is, mapping \(f\) reduces the exceedance of a sequence by exactly \(1\).

Mapping \(f\) is invertible. Note that in sequence \(\{a'_i\}\), the position corresponding to \(a_k\) is precisely the largest index where \(S'_k=+1\) and \(a'_i = +1\). This is because after swapping, these partial sums are exactly \(1\) greater than the corresponding partial sums before swapping, so a partial sum of \(+1\) now corresponds to a partial sum of \(0\) before swapping. However, by the choice of \(k\), there were no indices in this part (the original left part of \(a_k\)) where \(S_i = 0\) and \(a_i = +1\).

Thus, mapping \(f\) establishes a bijection between sequences with exceedance \(e>0\) and sequences with exceedance \((e-1)\). This shows that the number of sequences with different exceedances is the same. Since the total number of sequences is \(\dbinom{2n}{n}\), the number of valid sequences (i.e., those with exceedance \(0\)) is

\[ C_n = \dfrac{1}{n+1}\dbinom{2n}{n}. \]

This proves expression \((2)\) for Catalan numbers.

Proof of expression \((3)\)

Consider the path counting problem. This is a typical lattice path counting problem that can be solved using the reflection principle. Specifically for this problem, consider subtracting the number of invalid paths from the total number of paths. The total number of paths requires \(2n\) steps, with \(n\) steps to the right, so the number is \(\dbinom{2n}{n}\). A path is invalid if it touches the line \(y = x+1\). For any invalid path, find the first position where it touches the line \(y = x+1\), and reflect the portion of the path after that point about the line \(y=x+1\). It can be observed that an invalid path from \((0,0)\) to \((n,n)\) becomes a path from \((0,0)\) to \((n-1,n+1)\).

catalan1

Since a path from \((0,0)\) to \((n-1,n+1)\) must cross the line \(y = x+1\), each such path corresponds to an invalid path from \((0,0)\) to \((n,n)\). Similar to the total path count, the total number of invalid paths is \(\dbinom{2n}{n+1}\). Therefore, the total number of valid paths is

\[ C_n = \binom{2n}{n} - \binom{2n}{n+1}. \]

This is expression \((3)\) for Catalan numbers.

Proof of expression \((4)\)

Consider the triangulation counting problem. Let \(P\) be a convex \((n+2)\)-gon, and fix one of its edges as the base edge. For each triangulation of polygon \(P\), we can choose a non-base edge (including edges added during triangulation) to mark and orient. This gives \((4n+2)C_n\) ways of triangulation plus marking. Now let \(Q\) be a convex \((n+3)\)-gon, also fix one of its edges as the base edge. For polygon \(Q\), we can choose a non-base edge to mark, and then perform a triangulation. This gives \((n+2)C_{n+1}\) ways of marking plus triangulation.

As shown in the figure, there is a clear bijection between the results of these two sets of operations. For a triangulation and marking of \(P\), we can extend the marked edge into a triangle, extend the endpoint pointed by the orientation into a new edge, and mark this new edge. This yields a marking and triangulation of \(Q\). For a marking and triangulation of \(Q\), we can contract the marked edge into a point, mark the resulting diagonal, and orient it toward the contracted vertex. This yields a triangulation and marking of \(P\). Therefore,

\[ (4n+2)C_n = (n+2)C_{n+1}. \]

Rearranging and using \(C_0=1\), we obtain expression \((4)\) for Catalan numbers.

Example Problems

Luogu P1044 Stack

The push sequence is \(1,2,\ldots ,n\). Find the total number of all possible pop sequences.

Reference Code 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
#include <iostream>
using namespace std;

int n;
long long f[25];

int main() {
  f[0] = 1;
  cin >> n;
  for (int i = 1; i <= n; i++) f[i] = f[i - 1] * (4 * i - 2) / (i + 1);
  // Using the common form 4 here
  cout << f[n] << endl;
  return 0;
}

1
2
3
4
5
6
7
f = [0] * 25
f[0] = 1
n = int(input())
for i in range(1, n + 1):
    f[i] = f[i - 1] * (4 * i - 2) // (i + 1)
    # Using the common form 4 here
print(f[n])

Exercises

References and Notes

本页面最近更新：，更新历史
发现错误？想一起完善？ 在 GitHub 上编辑此页！
本页面贡献者：OI-wiki
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用