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 problemsolving 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:
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_{i1} H_{ni} & n \geq 2, n \in \mathbf{N_{+}}\\ 1 & n = 0, 1 \end{cases}$ $H_n = \frac{H_{n1} (4n2)}{n+1}$ $H_n = \binom{2n}{n}  \binom{2n}{n1}$A common application: for a stack, the push sequence is $1,2, \ldots ,n$, find the total number of possible pop sequences.
Closed Form
The recurrence relation of Catalan numbers is
$H_n=\sum_{i=0}^{n1}H_{i}H_{ni1} \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}^{n1}H_ix^iH_{ni1}x^{ni1}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{14x}}{2x}$Now, we have a question: which root should we take? Rationalizing the numerator, we get
$H(x)=\frac{2}{1\mp \sqrt{14x}}$Substituting $x=0$, we obtain the constant term of $H(x)$, which is $H_0$. When $H(x)=\dfrac{2}{1+\sqrt{14x}}$, we have $H(0)=1$, satisfying the requirement. The other root leads to the denominator being $0$ (nonconvergence), so it is discarded.
Therefore, we obtain the closed form of the generating function of Catalan numbers:
$H(x)=\frac{1 \sqrt{14x}}{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{14x}$:
$\begin{aligned} (14x)^{\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{(2n3)}{2}\\ &=\frac{(1)^{n1}(2n3 )!!}{2^n}\\ &=\frac{(1)^{n1}(2n2)!}{2^n(2n2)!!}\\ &=\frac{(1)^{n1}(2n2)!}{2^{2n1}(n1)!} \end{aligned}$Here, we use the simplification technique of double factorials. Then, substitute into $(1)$, we get
$\begin{aligned} (14x)^{\frac{1}{2}} &=1+\sum_{n\ge 1}\frac{(1)^{n1}(2n2)!}{2^{2n1}(n1)!n!}(4x)^n\\ &=1\sum_{n\ge 1}\frac{(2n2)!}{(n1)!n!}2x^n\\ &=1\sum_{n\ge 1}\binom{2n1}{n}\frac{1}{(2n1)}2x^n \end{aligned}$Substitute back into the original expression, we get
$\begin{aligned} H(x)&=\frac{1 \sqrt{14x}}{2x}\\ &=\frac{1}{2x}\sum_{n\ge 1}\binom{2n1}{n}\frac{1}{(2n1)}2x^n\\ &=\sum_{n\ge 1}\binom{2n1}{n}\frac{1}{(2n1)}x^{n1}\\ &=\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
Nondecreasing paths refer to paths that can only move upwards or to the right.

The number of nondecreasing 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 nondecreasing 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, n1)$, and reach $(n,n)$. This can be seen as the number of nondecreasing paths from $(1,0)$ to $(n,n1)$ without touching $y=x$.
All nondecreasing paths total $\dbinom{2n2}{n1}$. 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 nondecreasing path from $(0,1)$ to $(n,n1)$. The reverse is also true. Hence, the number of nondecreasing paths below $y=x$ is $\dbinom{2n2}{n1}  \dbinom{2n2}{n}$. Due to symmetry, the answer is $2\dbinom{2n2}{n1}  2\dbinom{2n2}{n}$.

The number of nondecreasing 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.
凡有所学，皆成性格