Lecture 7: Generating Functions for Catalan Numbers

Quick Overview

The lecture successfully derives the generating function for Catalan numbers, $C(x)$, by first establishing the recurrence relation $Cn = \sum{j=0}^{n-1} Cj 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 $Cn = \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 $Cn = \sum{j=0}^{n-1} Cj 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, $Cn$, is derived by applying the binomial theorem to the generating function $C(x) = \frac{1 - \sqrt{1 - 4x}}{2x}$, resulting in $Cn = \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, $Cn$, 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.