In this section, we learn one of many special integer sequences and its connections to combinatorics and generating functions.
Definition (Catalan numbers).
The numbers in the Catalan sequence \(\{C_n\}\) are called the Catalan numbers where the \(n\)th Catalan number is
\[C_n=\frac{1}{n+1} \binom{2n}{n},\;n\geq 0.\]
The Catalan numbers are named after mathematician Eugene Catalan (1814-1894). They can be found in the OEIS sequence A000108: \(1,1,2,5,14,42,\ldots.\)
Alternative expressions:
- \[C_n=\frac{(2n)!}{(n+1)!n!}=\binom{2n}{n}-\binom{2n}{n+1}=\frac{1}{2n+1} \binom{2n+1}{n}\]
- Recursive definition:
\[C_n=\frac{2(2n-1)}{n+1} C_{n-1},\; n\geq 1, \; C_0=1\]
Some applications in combinatorics:
- Convex polygon:
The number of triangulations of a convex \((n+2)\)-gon is \(C_n\). For \(n=4\), we consider a convex hexagon. The number of triangulations of a hexagon is \(C_4 = 14\). Below are six of fourteen distinct triangulations of a hexagon.
- Lattice paths:
A North-East lattice path is a sequence of distinct ordered pairs of integers that moves one step of unit length at a time towards North or East in the two-dimensional integer lattice \(\mathbb Z^2\). The number of North-East lattice paths from \((0,0)\) to \((n,n)\) that do not cross the diagonal \(y=x\) is \(C_n\). For \(n=4\), see the following North-East lattice path (in blue) from \((0,0)\) to \((4,4)\) that does not cross the diagonal \(y=x\):
- Parentheses:
The number of correctly matched \(n\) pairs of parentheses is \(C_n\). For \(n=3\), correctly matched pairs of parentheses are:
\[ ((())), \quad (()()), \quad (())(), \quad ()(()), \quad ()()().\]
Thus \(C_3 = 5\). To find a recurrence relation for \(C_n\), consider the first pair of parentheses and the number of ways to arrange the rest \(n-1\) pairs of parentheses. There are \(C_k\) ways to arrange \(k\) pairs of parentheses within the first pair for \(k=0,1,\ldots,n-1\) and \(C_{n-1-k}\) ways to arrange the rest \(n-1-k\) pairs of parentheses after the first pair. So for a fixed \(k=0,1,\ldots,n-1\), there are \(C_k C_{n-1-k}\) ways to arrange \(n\) pairs of parentheses. Thus
\[
C_n = \sum_{k=0}^{n-1} C_k C_{n-1-k}.
\]
We solve the above recurrence relation of the Catalan numbers using a generating function. First we need the Generalized binomial theorem:
Theorem (The generalized binomial theorem).
For any \(\alpha \in \mathbb{R}\),
\[
(1+x)^\alpha = \sum_{n=0}^\infty \binom{\alpha}{n} x^n, \quad |x| < 1,
\]
where
\[
\binom{\alpha}{n} = \frac{\alpha(\alpha-1)(\alpha-2)\cdots(\alpha-n+1)}{n!}.
\]
For \(\alpha = \frac{1}{2}\),
\[
\binom{1/2}{n} = \frac{\frac{1}{2}\left(\frac{1}{2}-1\right)\cdots\left(\frac{1}{2}-(n-1)\right)}{n!}.
\]
This simplifies to
\[
\binom{1/2}{n}
= \frac{(-1)^{n-1}}{4^n} \frac{(2n-3)!}{(n-1)! \, n!}
= \frac{(-1)^{n+1}}{4^n} \frac{1}{2n-1} \binom{2n}{n}.
\]
Hence
\[
\sqrt{1+x}
= \sum_{n=0}^\infty \binom{1/2}{n} x^n
= \sum_{n=0}^\infty \frac{(-1)^{n+1}}{4^n(2n-1)} \binom{2n}{n} x^n, \quad |x|<1.
\]
Solving the Catalan recurrence:
Recall the recurrence:
\[
C_n = \sum_{k=0}^{n-1} C_k C_{n-1-k} = \sum_{k=1}^{n} C_{k-1} C_{n-k}.
\]
Let
\[
f(x) = \sum_{n=0}^\infty C_n x^n.
\]
Multiply both sides by \(x^n\) and sum over \(n\):
\[
\sum_{n=1}^\infty C_n x^n
= \sum_{n=1}^\infty \left( \sum_{k=1}^n C_{k-1} C_{n-k} \right) x^n.
\]
The left-hand side is
\[
f(x) - C_0 = f(x) - 1.
\]
The right-hand side becomes
\[
x \sum_{n=0}^\infty \left( \sum_{k=0}^n C_k C_{n-k} \right) x^n
= x [f(x)]^2.
\]
Thus
\[
f(x) - 1 = x [f(x)]^2.
\]
Rewriting,
\[
x f(x)^2 - f(x) + 1 = 0.
\]
Solving the quadratic equation,
\[
f(x) = \frac{1 \pm \sqrt{1-4x}}{2x}.
\]
We choose the negative branch so that \(\lim_{x\to 0}f(x)=1\) for the condition \(f(0)=C_0=1\):
\[
f(x) = \frac{1 - \sqrt{1-4x}}{2x}.
\]
By the generalized binomial theorem,
\[
\sqrt{1-4x}
= \sum_{n=0}^\infty \binom{1/2}{n} (-4x)^n= \sum_{n=0}^\infty \frac{(-1)^{n+1}}{4^n(2n-1)} \binom{2n}{n} (-1)^n4^n x^n, \quad |-4x|<1.
\]
After simplifying, we get
\[
\sqrt{1-4x}
=\sum_{n=0}^\infty \frac{-1}{(2n-1)} \binom{2n}{n} x^n, \quad |x|<\frac{1}{4}.
\]
Thus
\[
f(x) = \frac{1}{2x} \left(1 - \sqrt{1-4x}\right)
= \frac{1}{2x} \sum_{n=1}^\infty \frac{1}{2n-1} \binom{2n}{n} x^n
= \sum_{n=1}^\infty \frac{1}{2(2n-1)} \binom{2n}{n} x^{n-1}.
\]
After reindexing (\(n \mapsto n+1\)) and simplifying, we get
\[
f(x)
= \sum_{n=0}^\infty \frac{1}{2(2n+1)} \binom{2n+2}{n+1} x^n
= \sum_{n=0}^\infty \frac{1}{n+1} \binom{2n}{n} x^n.
\]
Thus
\[
C_n = \frac{1}{n+1} \binom{2n}{n}.
\]
Problem.
Use a generating function to solve the following nonlinear recurrence relation:
\[C_n=\frac{2(2n-1)}{n+1} C_{n-1},\; n\geq 1, \; C_0=1\]
Hint. It will require solving the the following differential equation:
\[y'+\frac{2x-1}{x(4x-1)} y+\frac{1}{x(4x-1)}=0\]
Last edited