AIOJ

Introduction

Catalan numbers frequently occur in various counting problems. The Belgian mathematician Eugène Charles Catalan discovered this sequence in 1958 while studying the counting of parenthesis sequences, and it was named after him. The Qing mathematician Ming Antu had already discovered this sequence in the 1730s.

Catalan numbers satisfy the following recurrence:

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, with the index starting from $0$ ):

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

Applications

The recurrence for Catalan numbers $C_n$ has a natural recursive structure: a counting problem of size $n$ , counted by $C_n$ , can be split by enumerating a dividing point into two subproblems of sizes $i$ and $(n-1-i)$ . This recurrence causes Catalan numbers to occur widely in problems with similar recursive structures.

Path-counting problem: Consider an $n\times n$ grid with lower-left corner $(0, 0)$ and upper-right corner $(n, n)$ . Starting from the lower-left corner, at each step one may move one unit right or one unit up. The number of paths that reach the upper-right corner without going above the diagonal $y=x$ (touching it is allowed) is $C_n$ .

??? note "Proof" Let the number of solutions be $T_n$ . Consider the case $n \ge 2$ . Let the first point where the path reaches the diagonal $y=x$ be $(k,k)~(k \in [1,n])$ . Consider paths from $(0,0)$ to $(k,k)$ whose intermediate points, excluding the start and end points, do not pass through the diagonal (and cannot touch it).

![catalan2](/knowledge-assets/oi-wiki/1e04537ab249066c5de28231df13a49b61857429/math/combinatorics/images/catalan-2.svg)

As shown in the figure, the first step of such a path must be to the right, from $(0,0)$ to $(1,0)$, and the last step must be upward, from $(k,k-1)$ to $(k,k)$. Therefore, these paths are exactly paths from $(1,0)$ to $(k,k-1)$ that do not cross the line $y=x-1$, so their number is $T_{k-1}$. At the same time, the number of legal 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 possible values of $k$, the total number of legal 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 for Catalan numbers. Since $T_0=1$, we have $T_n = C_n$.

Counting nonintersecting chords in a circle: On a circle, connect $2n$ points in pairs so that the resulting $n$ line segments are pairwise disjoint. The number of possible configurations is $C_n$ .

??? note "Proof" Let the number of configurations for $2n$ points be $T_n$ . Label the $2n$ points clockwise as $1,2,\ldots,2n$ . Since the chords are pairwise disjoint, point $1$ can only be connected to an even-numbered point; otherwise, the odd number of points between the two endpoints could not be paired without crossing the chord connecting them. If $1$ is connected to $2k~(k\in[1,n])$ , there are $2k-2$ points on the left and $2n-2k$ points on the right. By the multiplication principle, the number of configurations is $T_{k-1}T_{n-k}$ . Thus, enumerating $k$ gives $T_n = \sum_{k=1}^n T_{k-1} T_{n-k}$ . Setting $k=i+1$ yields the recurrence for Catalan numbers. Since $T_0=1$ , we have $T_n=C_n$ .
Counting triangulations: The number of ways to divide a convex $(n+2)$ -gon into triangular regions with nonintersecting diagonals is $C_n$ .

??? note "Proof" Let the number of triangulations of an $(n+2)$ -gon be $T_n$ . First choose an edge $(1,n+2)$ as the base edge. It must belong to a triangle; let the third vertex of that triangle be $k~(k\in[2,n+1])$ . The original convex polygon is then 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, so the recurrence is

$$
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$.
```
Counting binary trees: The number of structurally distinct binary trees with $n$ nodes is $C_n$ . Equivalently, the number of structurally distinct full binary trees with $n$ non-leaf nodes is $C_{n}$ .

??? note "Proof" Let the number of binary trees with $n$ nodes be $T_n$ . Choose an arbitrary root node and enumerate the sizes of the left and right subtrees. If the left subtree has size $i\in[0,n-1]$ , the right subtree has size $(n-1-i)$ . Both subtrees are subproblems, so the recurrence is
```
$$
T_n = \sum_{i=0}^{n-1}T_iT_{n-1-i}.
$$

This is the recurrence for Catalan numbers. Since $T_0=T_1=1$, we have $T_n=C_n$.
```
Counting parenthesis sequences: The number of valid parenthesis sequences formed by $n$ pairs of parentheses is $C_n$ .

??? note "Proof" Relate this to the path-counting problem. Regard a left parenthesis as a move upward and a right parenthesis as a move to the right. A valid parenthesis sequence is one in which, at every position, the number of left parentheses is no less than the number of right parentheses. This is equivalent to the path-counting problem in which, at every moment, the number of upward moves is no less than the number of rightward moves. Therefore, valid parenthesis sequences and valid paths are in bijection. The number of valid parenthesis sequences is also $C_n$ .
Counting pop sequences: Suppose a stack of unbounded size receives the push sequence $1,2,3, \ldots ,n$ . The number of valid pop sequences is $C_n$ .

??? note "Proof" Relate this to the parenthesis-sequence counting problem. Regard a push as a left parenthesis and a pop as a right parenthesis. At every moment, the number of pushes is no less than the number of pops. Therefore, valid pop sequences and valid parenthesis sequences are in bijection. The number of valid pop sequences is also $C_n$ .
Counting sequences: Among sequences formed from $n$ copies of $+1$ and $n$ copies of $-1$ , the sequences $a_1,a_2, \ldots ,a_{2n}$ , the number of sequences whose partial sums satisfy $a_1+a_2+ \ldots +a_k \geq 0~(k=1,2,3, \ldots ,2n)$ is $C_n$ .

??? note "Proof" Relate this to the parenthesis-sequence counting problem. Regard $+1$ as a left parenthesis and $-1$ as a right parenthesis. At every moment, the number of $+1$ terms is no less than the number of $-1$ terms. Therefore, valid sequences and valid parenthesis sequences are in bijection. The number of valid sequences is also $C_n$ .

Although this recurrence has many applications, its direct computation is relatively expensive, so a simpler formula is 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}

All of these forms of Catalan numbers can be computed efficiently: the first two turn the problem into computing factorials and binomial coefficients, while the third provides a recurrence for sequential computation.

This article provides two proofs for these three common forms.

Algebraic Derivation

There are two steps to deriving the above expressions for Catalan numbers algebraically. First, verify that the three forms are equivalent.

Proof that expressions

(2)\sim(4)

are equivalent

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}

Likewise, 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 are indeed solutions to the Catalan recurrence. To do so, 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$ of the Catalan numbers. Since the Catalan recurrence is very similar to a convolution, consider constructing an equation for $C(x)$ using a 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}

In the penultimate equality, the order of summation is exchanged and $j=n-1-i$ is substituted. Thus:

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

From the initial condition $C_0=1$ , we know that $C(0)=1$ . Substitution shows that the only feasible solution is

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

Next, this must be expanded as a power series. Using the power-series expansion of $(1+x)^a$ , we obtain

\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 a 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 this into the expression for $C(x)$ gives

\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}

This gives $C_n$ in expression $(2)$ .

Combinatorial Meaning

Since Catalan numbers have clear combinatorial meanings, the forms can also be proved using only combinatorial counting. This section gives one combinatorial proof for each of the three expressions.

Proof of expression

(2)

Consider the sequence-counting problem. For any sequence consisting of $\pm 1$ , $\{a_i\}_{i=1}^{2n}$ , define its partial sum as $S_i = \sum_{j=1}^{i}a_i$ , and define its exceedance as the number of indices satisfying $S_i < 0$ and $a_i = -1$ . An exceedance of $0$ is equivalent to a valid sequence. The exceedance can take values in $[0,n]$ , giving $(n+1)$ possible values in total. It remains to prove that the numbers of sequences for different exceedances are actually equal.

To this end, construct a mapping from sequences with exceedance $e > 0$ to sequences with exceedance $(e-1)$ , denoted by $f$ . For a sequence with exceedance $e > 0$ , represented as $\{a_i\}$ , choose the smallest index $k$ such that $S_i = 0$ and $a_i = +1$ . Exchange the sequences on the two sides of $a_k$ to obtain the following 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 sums corresponding to the part to the right of $a_k$ in the original sequence are unchanged by the exchange, its contribution to the exceedance is also unchanged. For the part to the left of $a_k$ in the original sequence, all corresponding partial sums increase by $1$ after the exchange. Therefore, its contribution to the exceedance decreases, and the amount of the decrease is exactly the number of indices in the part to the left of $a_k$ in the original sequence satisfying $S_i=-1$ and $a_i=-1$ . Because of the choice of $a_k$ , there is exactly one such index, so the exceedance of $\{a'_i\}$ is $(e-1)$ . In other words, the mapping $f$ decreases the exceedance of a sequence by exactly $1$ .

The mapping $f$ is invertible. Notice that in the sequence $\{a'_i\}$ , the position corresponding to $a_k$ is exactly the largest index satisfying $S'_k=+1$ and $a'_i = +1$ . This is because, after the exchange, these partial sums are exactly $1$ greater than the corresponding partial sums before the exchange, so the current partial sum $+1$ corresponds to a partial sum of $0$ before the exchange. However, by the choice of $k$ , the part before this position after the exchange (that is, the part to the left of $a_k$ in the original sequence) contains no index satisfying $S_i = 0$ and $a_i = +1$ .

Thus, $f$ is a bijection between sequences with exceedance $e>0$ and sequences with exceedance $(e-1)$ . This shows that the numbers of sequences for different exceedances are equal. Since the total number of sequences is $\dbinom{2n}{n}$ , the number of valid sequences (that is, sequences 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 and can be solved using the reflection principle. For this problem, subtract the number of invalid paths from the total number of paths. A total path takes $2n$ steps, $n$ of them to the right, so the number of configurations is $\dbinom{2n}{n}$ . A path is invalid if and only if it touches the line $y = x+1$ . For any invalid path, find its first intersection with the line $y = x+1$ and reflect the portion after that point across the line $y=x+1$ . It can then be seen that an invalid path from $(0,0)$ to $(n,n)$ becomes a path from $(0,0)$ to $(n-1,n+1)$ .

$catalan1$

catalan1

Since every path from $(0,0)$ to $(n-1,n+1)$ must cross the line $y = x+1$ , every such path corresponds to an invalid path from $(0,0)$ to $(n,n)$ . As in the calculation of the total number of paths, 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 every triangulation of polygon $P$ , choose one of its non-base edges (including edges newly added during triangulation), mark it, and orient it. There are $(4n+2)C_n$ ways to triangulate and mark it. Now let $Q$ be a convex $(n+3)$ -gon, again with one edge fixed as the base edge. For polygon $Q$ , choose one of its non-base edges, mark it, and then triangulate it. There are $(n+2)C_{n+1}$ ways to mark and triangulate it.

$Figure: catalan triangulation$

As shown in the figure, the results of these two sets of operations are clearly in bijection. Given a triangulation and marked edge of $P$ , extend its marked edge to a triangle, extend the endpoint indicated by the orientation into a new edge, and mark this new edge. This gives a marked triangulation of $Q$ . Conversely, given a marked triangulation of $Q$ , contract its marked edge into a point, mark the diagonal created by the contraction, and orient it toward the resulting vertex. This gives a triangulation and marked edge of $P$ . Therefore,

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

Rearranging and using $C_0=1$ gives expression $(4)$ for Catalan numbers.

Example

Luogu P1044 Stack

Given the push order $1,2,\ldots ,n$ , find the total number of possible pop orders.

Reference code

C++

#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);
  // This uses common form 4
  cout << f[n] << endl;
  return 0;
}

Python

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)
    # This uses common form 4
print(f[n])

Exercises

References and Notes

Catalan number - Wikipedia

Catalan Numbers

Introduction

Applications

Common Forms

Algebraic Derivation

Combinatorial Meaning

Example

Exercises

References and Notes