# Lecture 7: Generating Functions for Catalan Numbers

Source: https://www.youtube.com/watch?v=JNSyyOAeMOc
Recap page: https://rapidrecap.app/video/JNSyyOAeMOc
Generated: 2025-12-17T16:36:48.702+00:00

---
## Quick Overview

The lecture successfully derives the generating function for Catalan numbers, $C(x)$, by first establishing the recurrence relation $C_n = \sum_{j=0}^{n-1} C_j C_{n-j-1}$ based on the structure of binary trees, leading to the quadratic equation $C(x)^2 - C(x) + 1 = 0$, and subsequently solving it using the binomial theorem to find the closed-form formula $C_n = \frac{1}{n+1} \binom{2n}{n}$.

**Key Points:**
- The generating function $C(x)$ for Catalan numbers satisfies the quadratic equation $C(x)^2 - C(x) + 1 = 0$, derived from the recurrence $C_n = \sum_{j=0}^{n-1} C_j C_{n-j-1}$ for binary trees.
- The correct solution chosen from the quadratic formula involved the minus sign, as substituting $x=0$ into $C(x) = \frac{1 \pm \sqrt{1 - 4x}}{2x}$ requires the limit to be 1, which only the minus term yields: $\lim_{x \to 0} \frac{1 - \sqrt{1 - 4x}}{2x} = 1$.
- The formula for Catalan numbers, $C_n$, is derived by applying the binomial theorem to the generating function $C(x) = \frac{1 - \sqrt{1 - 4x}}{2x}$, resulting in $C_n = \frac{1}{n+1} \binom{2n}{n}$.
- An alternative derivation for the generating function uses Dyck paths, relating $C(x)$ to $D(x)$ (the generating function for raised Dyck paths) via $C(x) = 1 / (1 - D(x))$, where $D(x) = x C(x)$, yielding the same equation $C(x) = 1 / (1 - x C(x))$.
- The process of deriving $C(x)$ from Dyck paths relies on a theorem stating that the generating function for sequences of objects is $1 / (1 - A(x))$, where $A(x)$ is the generating function for the objects themselves, provided objects have non-zero size.
- The lecturer illustrates a related generating function technique using tiling problems, showing that if $B(x)$ counts total tilings and $A(x)$ counts fundamental tilings, then $B(x) = 1 / (1 - A(x))$, and a recurrence relation can be read directly from the denominator of the resulting rational function.

**Context:** Professor Peter Shor presents a lecture focused on deriving the formula for Catalan numbers, $C_n$, using the method of generating functions, while also mentioning that the material covered, including Catalan numbers, will inform but likely not be explicitly tested on an upcoming exam. The lecture begins by recalling that Catalan numbers count combinatorial objects like rooted binary trees and Dyck paths, establishing the necessary recurrence relation from the structure of binary trees.

## Detailed Analysis

The core of the lecture is the generation of the Catalan number generating function, $C(x) = \sum_{n=0}^{\infty} C_n x^n$. Shor starts by establishing the recurrence $C_n = \sum_{j=0}^{n-1} C_j C_{n-j-1}$ by analyzing the structure of a binary tree rooted at a single vertex with left subtree $T_a$ (size $j$) and right subtree $T_b$ (size $n-j-1$), which leads to the equation $C(x) = 1 + x C(x)^2$. Rearranging this yields the quadratic equation $x C(x)^2 - C(x) + 1 = 0$. Solving this using the quadratic formula provides two potential solutions, one of which must be discarded because $C(0)$ must equal $C_0 = 1$; this forces the selection of $C(x) = \frac{1 - \sqrt{1 - 4x}}{2x}$. Shor then uses the generalized binomial theorem to expand $\sqrt{1 - 4x} = (1 - 4x)^{1/2}$ and performs term-by-term cancellation with the initial 1, extracting the coefficient of $x^n$ to confirm the known formula $C_n = \frac{1}{n+1} \binom{2n}{n}$. A second method confirms the generating function by relating Dyck paths to raised Dyck paths via the sequence theorem for generating functions, again resulting in $C(x) = 1 / (1 - x C(x))$, which solves to the same quadratic equation. Finally, Shor demonstrates how to extract a recurrence relation, $b_n = b_{n-2} + 2b_{n-3}$, from the denominator of a different generating function $B(x) = \frac{1 - x^2}{1 - x^2 - 2x^3}$ derived from a tiling problem, emphasizing that the numerator dictates the initial conditions.

### Catalan Recurrence and Generating Function Setup

- The recurrence $C_n = \sum_{j=0}^{n-1} C_j C_{n-j-1}$ arises from binary tree decomposition
- This leads to the quadratic equation $x C(x)^2 - C(x) + 1 = 0$
- The initial condition $C_0=1$ selects the solution $C(x) = \frac{1 - \sqrt{1 - 4x}}{2x}$.

### Deriving the Closed Form Formula

- The binomial theorem is applied to $(1 - 4x)^{1/2}$ to find the Taylor expansion of $C(x)$
- The coefficient calculation confirms the Catalan number formula $C_n = \frac{1}{n+1} \binom{2n}{n}$.

### Alternative Derivation via Dyck Paths

- Dyck paths are decomposed into sequences of raised Dyck paths, applying the sequence theorem $C(x) = 1 / (1 - D(x))$
- Raised Dyck paths relate to Dyck paths by adding two steps, so $D(x) = x C(x)$
- This yields $C(x) = 1 / (1 - x C(x))$, confirming the initial quadratic equation.

### Generating Functions and Recurrence Relations (Tiling Example)

- The structure $B(x) = 1 / (1 - A(x))$ applies when objects counted by $A(x)$ form sequences to create objects counted by $B(x)$
- For a tiling problem, $B(x) = \frac{1 - x^2}{1 - x^2 - 2x^3}$ is derived based on fundamental tilings $A(x)$
- The denominator $1 - x^2 - 2x^3$ implies the recurrence $b_n = b_{n-2} + 2b_{n-3}$ for $n$ large enough, while the numerator $1 - x^2$ defines the initial conditions.