NOTE & BLOG

Catalan Numbers

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

1. 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?
2. 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$?
3. 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?
4. Without intersecting diagonals, how many ways are there to divide a convex polygon area into triangular regions?
5. If the stack (infinite) has a push sequence of $1,2,3, \cdots ,n$, how many different pop sequences are there?
6. How many different binary trees can be constructed with $n$ nodes?
7. 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:

Recurrence Relation

The solution to this recurrence relation is:

Common formulas for Catalan numbers are:

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

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:

Solving this equation, we get

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

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:

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}$:

Note that

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

Substitute back into the original expression, we get

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.

1. 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}$.

2. 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}$.

3. 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.