The Catalan Series

Mar 2, 2024

The article discusses Catalan numbers, a sequence used in combinatorial problems. It covers their recurrence relation, closed form, and applications in path counting. It provides insights into problem-solving using Catalan numbers.

Catalan Numbers

Catalan numbers $H_n$ can be applied to the following problems:

There are $2n$ people queuing up to enter a theater. The entrance fee is 5 yuan. Among them, only $n$ people have a 5 yuan bill, while the other $n$ people only have a 10 yuan bill. The theater has no other bills. How many ways are there to ensure that whenever a person with a 10 yuan bill buys a ticket, the ticket office has a 5 yuan bill for change?
There is a grid of size $n\times n$ with the lower left corner at $(0, 0)$ and the upper right corner at $(n, n)$ . Starting from the lower left corner, you can only move one unit to the right or up each time, without going above the diagonal line $y=x$ . How many possible paths are there to reach the upper right corner without crossing the line $y=x$ ?
Choose $2n$ points on a circle and connect these points pairwise to obtain $n$ line segments. How many ways are there to ensure that the $n$ line segments obtained do not intersect?
Without intersecting diagonals, how many ways are there to divide a convex polygon area into triangular regions?
If the stack (infinite) has a push sequence of $1,2,3, \cdots ,n$ , how many different pop sequences are there?
How many different binary trees can be constructed with $n$ nodes?
Given $2n$ numbers consisting of $n$ $+1$ s and $n$ $-1$ s, denoted as $a_1,a_2, \cdots ,a_{2n}$ , such that the partial sum satisfies $a_1+a_2+ \cdots +a_k \geq 0~(k=1,2,3, \cdots ,2n)$ , how many sequences satisfy this condition?

The corresponding sequence is:

$H_0$	$H_1$	$H_2$	$H_3$	$H_4$	$H_5$	$H_6$	...
1	1	2	5	14	42	132	...

Recurrence Relation

The solution to this recurrence relation is:

H_n = \frac{\binom{2n}{n}}{n+1}(n \geq 2, n \in \mathbf{N_{+}})

Common formulas for Catalan numbers are:

H_n = \begin{cases} \sum_{i=1}^{n} H_{i-1} H_{n-i} & n \geq 2, n \in \mathbf{N_{+}}\\ 1 & n = 0, 1 \end{cases}

H_n = \frac{H_{n-1} (4n-2)}{n+1}

H_n = \binom{2n}{n} - \binom{2n}{n-1}

A common application: for a stack, the push sequence is $1,2, \ldots ,n$ , find the total number of possible pop sequences.

#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);
  // Here, formula 2 is used
  cout << f[n] << endl;
  return 0;
}

Closed Form

The recurrence relation of Catalan numbers is

H_n=\sum_{i=0}^{n-1}H_{i}H_{n-i-1} \quad (n\ge 2)

where $H_0=1$ and $H_1=1$ . Let its ordinary generating function be $H(x)$ .

We find that the recurrence relation of Catalan numbers is similar to the form of convolution. Therefore, we construct an equation about $H(x)$ using convolution:

\begin{aligned} H(x)&=\sum_{n\ge 0}H_nx^n\\ &=1+\sum_{n\ge 1}\sum_{i=0}^{n-1}H_ix^iH_{n-i-1}x^{n-i-1}x\\ &=1+x\sum_{i\ge 0}H_{i}x^i\sum_{n\ge 0}H_{n}x^{n}\\ &=1+xH^2(x) \end{aligned}

Solving this equation, we get

H(x)=\frac{1\pm \sqrt{1-4x}}{2x}

Now, we have a question: which root should we take? Rationalizing the numerator, we get

H(x)=\frac{2}{1\mp \sqrt{1-4x}}

Substituting $x=0$ , we obtain the constant term of $H(x)$ , which is $H_0$ . When $H(x)=\dfrac{2}{1+\sqrt{1-4x}}$ , we have $H(0)=1$ , satisfying the requirement. The other root leads to the denominator being $0$ (non-convergence), so it is discarded.

Therefore, we obtain the closed form of the generating function of Catalan numbers:

H(x)=\frac{1- \sqrt{1-4x}}{2x}

Next, we need to expand it. But note that its denominator is not in the form of a polynomial like the Fibonacci sequence, so it is not convenient to use the expansion form of geometric sequences. Here we need to use Newton's binomial theorem. Let's first expand $\sqrt{1-4x}$ :

\begin{aligned} (1-4x)^{\frac{1}{2}} &=\sum_{n\ge 0}\binom{\frac{1}{2}}{n}(-4x)^n\\ &=1+\sum_{n\ge 1}\frac{\left(\frac{1}{2}\right)^{\underline{n}}}{n!}(-4x)^n \end{aligned} \tag{1}

Note that

\begin{aligned} \left(\frac{1}{2}\right)^{\underline{n}} &=\frac{1}{2}\frac{-1}{2}\frac{-3}{2}\cdots\frac{-(2n-3)}{2}\\ &=\frac{(-1)^{n-1}(2n-3 )!!}{2^n}\\ &=\frac{(-1)^{n-1}(2n-2)!}{2^n(2n-2)!!}\\ &=\frac{(-1)^{n-1}(2n-2)!}{2^{2n-1}(n-1)!} \end{aligned}

Here, we use the simplification technique of double factorials. Then, substitute into $(1)$ , we get

\begin{aligned} (1-4x)^{\frac{1}{2}} &=1+\sum_{n\ge 1}\frac{(-1)^{n-1}(2n-2)!}{2^{2n-1}(n-1)!n!}(-4x)^n\\ &=1-\sum_{n\ge 1}\frac{(2n-2)!}{(n-1)!n!}2x^n\\ &=1-\sum_{n\ge 1}\binom{2n-1}{n}\frac{1}{(2n-1)}2x^n \end{aligned}

Substitute back into the original expression, we get

\begin{aligned} H(x)&=\frac{1- \sqrt{1-4x}}{2x}\\ &=\frac{1}{2x}\sum_{n\ge 1}\binom{2n-1}{n}\frac{1}{(2n-1)}2x^n\\ &=\sum_{n\ge 1}\binom{2n-1}{n}\frac{1}{(2n-1)}x^{n-1}\\ &=\sum_{n\ge 0}\binom{2n+1}{n+1}\frac{1}{(2n+1)}x^{n}\\ &=\sum_{n\ge 0}\binom{2n}{n}\frac{1}{n+1}x^{n}\\ \end{aligned}

Thus, we obtain the general formula for Catalan numbers.

Path Counting Problem

Non-decreasing paths refer to paths that can only move upwards or to the right.

The number of non-decreasing paths from $(0,0)$ to $(m,n)$ is equal to the number of permutations of $m$ $x$ and $n$ $y$ , i.e., $\dbinom{n + m}{m}$ .
The number of non-decreasing paths from $(0,0)$ to $(n,n)$ that do not touch the line $y=x$ except at endpoints:

First, consider the paths below the line $y=x$ , which all start from $(0, 0)$ , pass through $(1, 0)$ and $(n, n-1)$ , and reach $(n,n)$ . This can be seen as the number of non-decreasing paths from $(1,0)$ to $(n,n-1)$ without touching $y=x$ .

All non-decreasing paths total $\dbinom{2n-2}{n-1}$ . For any path that touches $y=x$ , we can symmetrically transform the part from the point where it leaves this line to $(1,0)$ , obtaining a non-decreasing path from $(0,1)$ to $(n,n-1)$ . The reverse is also true. Hence, the number of non-decreasing paths below $y=x$ is $\dbinom{2n-2}{n-1} - \dbinom{2n-2}{n}$ . Due to symmetry, the answer is $2\dbinom{2n-2}{n-1} - 2\dbinom{2n-2}{n}$ .
The number of non-decreasing paths from $(0,0)$ to $(n,n)$ that do not cross the line $y=x$ : Similarly, we can obtain $\dfrac{2}{n+1}\dbinom{2n}{n}$ using similar methods.

NOTE: This article is rewritten by OI WIKI.

NOTE & BLOG

Catalan Numbers

Recurrence Relation

Closed Form

Path Counting Problem