本讲要解决的问题

Catalan 数 $C_0,C_1,C_2,\dots=1,1,2,5,14,42,\dots$ 同时数着很多看似无关的对象：满二叉树、Dyck 路径、括号匹配、多边形三角剖分。上一讲用生成函数解了 Fibonacci 的线性递推；这一讲处理一个非线性递推——它的生成函数满足二次方程。

目标有三步：写出 $C(x)$ 满足的方程；解出 $C(x)$ 的闭式；再用二项式定理展开，得到

$$C_n=\frac{1}{n+1}\binom{2n}{n}.$$

时间轴

Catalan 数的两种面孔

本讲反复使用两个模型，它们给出同一个数列：

• 满二叉树：每个内部结点恰有两个孩子。含 $2n+1$ 个结点的满二叉树有 $C_n$ 棵。$n=3$ 时有 $5$ 棵。
• Dyck 路径：从 $0$ 出发，走 $2n$ 步，每步 $+1$ 或 $-1$，始终不低于 $0$，最后回到 $0$。这样的路径也有 $C_n$ 条。

两个模型各给出一条通往 $C(x)$ 的路，最后汇合到同一个二次方程。

从二叉树的递推出发

一棵不是单结点的满二叉树，由一个根和左右两棵子树构成。设整棵树有 $2n+1$ 个结点，左子树有 $2j+1$ 个结点，则右子树有

$$(2n+1)-1-(2j+1)=2(n-j-1)+1$$

个结点。左右子树的形状可以独立选择，于是

$$C_n=\sum_{j=0}^{n-1}C_j\,C_{n-j-1}.$$

验算 $n=3$：

$$C_3=C_0C_2+C_1C_1+C_2C_0=1\cdot2+1\cdot1+2\cdot1=5 .$$

这串卷积正好是乘积的系数形式。设 $C(x)=\sum_{n\ge0}C_nx^n$。乘积 $C(x)^2$ 中 $x^{n-1}$ 的系数是 $\sum_{j=0}^{n-1}C_jC_{n-1-j}$，正是 $C_n$。再乘一个 $x$ 把次数抬到 $n$：

$$C(x)=1+x\,C(x)^2 .$$

常数项 $1$ 对应 $C_0=1$（单结点树，也是空路径）。这一步是整讲的关键：递推被翻译成一个关于未知函数 $C(x)$ 的代数方程。

解二次方程

把方程整理成标准形式：

$$xC(x)^2-C(x)+1=0 .$$

用求根公式（把 $x$ 当作二次项系数）：

$$C(x)=\frac{1\pm\sqrt{1-4x}}{2x}.$$

两个根在代数上都满足方程，必须用初始条件筛掉一个。

令 $x\to0$。分子在 $x=0$ 处等于 $1\pm1$，分母趋于 $0$：

• 取加号：分子趋于 $2$，商发散，不可能等于 $C(0)=1$。
• 取减号：分子趋于 $0$，需要看极限。

对减号用一次洛必达法则，或直接用下一节的展开：

$$\lim_{x\to0}\frac{1-\sqrt{1-4x}}{2x} =\lim_{x\to0}\frac{\frac{2}{\sqrt{1-4x}}}{2}=1 .$$

所以

$$C(x)=\frac{1-\sqrt{1-4x}}{2x}.$$

常数项为 $1$，与 $C_0=1$ 一致。这个检验不是形式上的：生成函数是形式幂级数，$x=0$ 处的值就是常数项，选错根会得到 $1/x$ 型的奇点，级数根本无法展开。

用二项式定理展开

要读出 $x^n$ 的系数，需要 $\sqrt{1-4x}=(1-4x)^{1/2}$ 的展开。广义二项式定理对分数指数同样成立：

$$(1+a)^{1/2}=\sum_{k\ge0}\binom{1/2}{k}a^k .$$

其中

$$\binom{1/2}{k} =\frac{\frac12\left(-\frac12\right)\left(-\frac32\right)\cdots\left(\frac32-k\right)}{k!} =\frac{(-1)^{k-1}(2k-3)!!}{2^k\,k!}\quad(k\ge1),$$

$(2k-3)!!=1\cdot3\cdot5\cdots(2k-3)$ 是双阶乘。代入 $a=-4x$：

$$\binom{1/2}{k}(-4x)^k =\frac{(-1)^{k-1}(2k-3)!!}{2^k\,k!}\cdot(-1)^k4^kx^k =-\frac{(2k-3)!!\,2^k}{k!}x^k .$$

负号两两抵消，每一项都是负的，于是

$$1-\sqrt{1-4x} =\sum_{k\ge1}\frac{(2k-3)!!\,2^k}{k!}x^k .$$

再除以 $2x$，$x^k$ 变成 $x^{k-1}$：

$$C(x)=\sum_{k\ge1}\frac{(2k-3)!!\,2^{k-1}}{k!}x^{k-1}.$$

令 $n=k-1$，即 $k=n+1$：

$$C_n=\frac{(2n-1)!!\,2^{n}}{(n+1)!}.$$

化成组合数

用双阶乘与阶乘的关系

$$(2n-1)!!=\frac{(2n)!}{2^n\,n!}$$

（分子是所有 $1$ 到 $2n$ 的乘积，除去其中的偶数因子 $2^n n!$，剩下奇数因子），代入：

$$C_n=\frac{(2n)!}{2^n n!}\cdot\frac{2^n}{(n+1)!} =\frac{(2n)!}{n!\,(n+1)!} =\frac{1}{n+1}\binom{2n}{n}.$$

验算 $n=3$ 时 $\frac{1}{4}\binom63=\frac{20}{4}=5$ ✓；用双阶乘形式验算：$5!!\cdot2^3/4!=15\cdot8/24=5$ ✓。

课程在黑板上逐项展开到 $x^4$ 时，中间系数出现过口误；以统一公式为准，$C_4=\frac65\binom84=\frac{70}{5}=14$，与枚举一致。

第二条路：Dyck 路径的首次回零分解

Dyck 路径有一个天然的分解：在第一次回到 $0$ 的地方切开。

每个非空 Dyck 路径唯一地写成

$$\text{（上步）}+\text{（一个 Dyck 路径）}+\text{（下步）}+\text{（另一个 Dyck 路径）}.$$

前半段「上步 + Dyck 路径 + 下步」称为一个抬升路径：它从 $0$ 出发，第一步向上，最后一步向下，中间始终不低于 $1$，且只在终点回到 $0$。去掉首尾两步，剩下的正是一条 Dyck 路径，只是整体上移了一层。

于是：

• 抬升路径的生成函数 $D(x)=x\,C(x)$：$x$ 记录多出的两步，$C(x)$ 记录中间那段。
• 任意 Dyck 路径是若干抬升路径的序列（可以为空），由序列公式

$$C(x)=\frac{1}{1-D(x)}=\frac{1}{1-xC(x)} .$$

两边乘以 $1-xC(x)$：

$$C(x)-xC(x)^2=1,$$

即

$$xC(x)^2-C(x)+1=0 .$$

与二叉树得到的是同一个二次方程。两条完全不同的组合分解，落到同一个代数方程上，这是生成函数方法最漂亮的地方之一。

序列定理

上面用到的定理值得单独写出。

设 $A$ 中的对象大小至少为 $1$，$A(x)=\sum_{n\ge1}a_nx^n$。由 $A$ 的对象排成的有限序列（含空序列）的生成函数是

$$\frac{1}{1-A(x)} .$$

为什么要求大小至少为 $1$？ 若存在大小为 $0$ 的对象，就能在任意位置插入任意多个而不改变总大小，于是每个大小都有无穷多个序列，系数不再是有限数，生成函数失去意义。

在 Dyck 路径里，被排成序列的对象是抬升路径，最短长度为 $2$、大小记为 $1$，满足条件；空序列对应空路径，贡献常数项 $1$。

应用：$2\times n$ 条带的铺砖

用两种可翻转的骨牌铺 $2\times n$ 条带。先数不可再分的块：不存在一条竖线把它切成两段各自可铺。

• $a_3=2$：最短的基本块长度为 $3$，沿水平线翻转得到另一种。
• $a_4=0$：长度为 $4$ 无法由基本块拼成。
• $a_5=2$、$a_6=0$、$a_7=2$，依此类推。

一般地，

$$a_{2k}=0,\qquad a_{2k+1}=2\quad(k\ge1).$$

直观上，要让一条竖线无处可切，必须用两个「L」形块夹住中间任意多个「Z」形块，因此基本块只能取奇数长度，且只有两种镜像。

于是

$$A(x)=\sum_{k\ge1}2x^{2k+1}=2x^3\left(1+x^2+x^4+\cdots\right)=\frac{2x^3}{1-x^2}.$$

任意铺法是基本块的序列：

$$B(x)=\frac{1}{1-A(x)} =\frac{1}{1-\dfrac{2x^3}{1-x^2}} =\frac{1-x^2}{1-x^2-2x^3}.$$

读出递推

比较 $B(x)(1-x^2-2x^3)=1-x^2$ 两端系数：

$$b_n=b_{n-2}+2b_{n-3}\quad(n\ge3),$$

初值为

$$b_0=1,\ b_1=0,\ b_2=0,\ b_3=2,\ b_4=0,\ b_5=2,\ b_6=4,\ b_7=2,\ b_8=8 .$$

$b_2=0$ 而不是 $1$，原因是：空铺法加上一个长度 $2$ 的块并不能得到长度 $2$ 的铺法——最短的基本块长度是 $3$。分母给出递推，分子给出初值，这一点与上一讲的铺砖例子完全一致。

递推也可以直接看出来：任何非空铺法，要么在末尾接一个长度 $2$ 的竖块（$b_{n-2}$ 种），要么接一个长度 $3$ 的基本块（两种朝向，$2b_{n-3}$ 种）。

本节结论

• Catalan 数 $1,1,2,5,14,\dots$ 满足 $C_n=\sum_{j=0}^{n-1}C_jC_{n-j-1}$。
• 生成函数满足 $C(x)=1+xC(x)^2$，解为 $C(x)=\dfrac{1-\sqrt{1-4x}}{2x}$，取减号由 $C(0)=1$ 决定。
• 二项式展开给出 $C_n=\dfrac{(2n-1)!!\,2^n}{(n+1)!}=\dfrac{1}{n+1}\dbinom{2n}{n}$。
• Dyck 路径按首次回零分解，得到 $C(x)=\dfrac{1}{1-xC(x)}$，与二叉树给出同一方程。
• 序列定理：对象大小至少为 $1$ 时，序列的生成函数是 $1/(1-A(x))$。
• 铺砖问题：$A(x)=\dfrac{2x^3}{1-x^2}$，$B(x)=\dfrac{1-x^2}{1-x^2-2x^3}$，递推 $b_n=b_{n-2}+2b_{n-3}$。

理解检验

1. 用二叉树的结点数解释 $C_n=\sum_{j=0}^{n-1}C_jC_{n-j-1}$。

参考答案：一棵有 $2n+1$ 个结点的满二叉树由根、左子树、右子树组成。若左子树有 $2j+1$ 个结点，则右子树有 $(2n+1)-1-(2j+1)=2(n-j-1)+1$ 个结点。左子树有 $C_j$ 种形状，右子树有 $C_{n-j-1}$ 种，二者独立，乘起来即得。$j$ 从 $0$ 取到 $n-1$，对应左子树从最小到最大。

2. 解出 $C(x)$ 时为什么要取减号？请给出严格理由。

参考答案：方程 $xC^2-C+1=0$ 的两根为 $(1\pm\sqrt{1-4x})/(2x)$。生成函数的常数项必须是 $C_0=1$，即 $\lim_{x\to0}C(x)=1$。取加号时分子趋于 $2$，商发散；取减号时用洛必达： $\lim_{x\to0}\frac{1-\sqrt{1-4x}}{2x}=\lim_{x\to0}\frac{2/\sqrt{1-4x}}{2}=1$。 因此只有减号给出有限的常数项，加号对应的级数含 $1/x$ 项，不是形式幂级数。

3. 从 $C(x)=\frac{1-\sqrt{1-4x}}{2x}$ 推出 $C_n=\frac{1}{n+1}\binom{2n}{n}$，写出双阶乘那一步。

参考答案：由 $(1+a)^{1/2}=\sum_k\binom{1/2}{k}a^k$，且 $\binom{1/2}{k}=(-1)^{k-1}(2k-3)!!/(2^kk!)$，取 $a=-4x$ 得 $\binom{1/2}{k}(-4x)^k=-(2k-3)!!2^k x^k/k!$。于是 $1-\sqrt{1-4x}=\sum_{k\ge1}(2k-3)!!2^kx^k/k!$，除以 $2x$ 后 $C_n=(2n-1)!!2^n/(n+1)!$。 再用 $(2n-1)!!=(2n)!/(2^nn!)$，约去 $2^n$ 得 $C_n=(2n)!/(n!(n+1)!)=\frac{1}{n+1}\binom{2n}{n}$。

4. 为什么抬升路径的生成函数是 $D(x)=xC(x)$？

参考答案：一条抬升路径从 $0$ 出发，第一步必为上步，最后一步必为下步，且中间始终不低于 $1$，只在终点回到 $0$。去掉首尾两步，剩余部分整体下移一层后是一条长度任意、始终非负的 Dyck 路径。因此抬升路径与「Dyck 路径 + 两次额外步」一一对应。按本讲的大小约定（大小为步数的一半），额外两步贡献因子 $x$，所以 $D(x)=xC(x)$。

5. 铺砖问题中，为什么 $a_{2k}=0$ 而 $a_{2k+1}=2$？为什么 $b_2=0$？

参考答案：基本块要求不存在一条竖线把它切成两段各自可铺。两种骨牌的形状使得只有奇数长度的条带能被「不可分」地铺满：最短是长度 $3$，之后每加一对「Z」形块长度加 $2$，两端必须用互为镜像的「L」形块封口，因此长度只能是 $2k+1$，且每种长度恰有两种镜像，故 $a_{2k+1}=2$，偶数长度无法构成基本块，$a_{2k}=0$。$b_2=0$ 是因为空铺法无法通过添加基本块得到长度 $2$——最短的基本块长度是 $3$；这不违反递推，递推从 $n=3$ 起才适用。

6. 序列定理为什么要求每个对象大小至少为 $1$？如果允许大小为 $0$ 的对象会怎样？

参考答案：序列的生成函数是 $1+A+A^2+\cdots=1/(1-A)$，这个等式作为形式幂级数成立的前提是每一项对 $x^n$ 只贡献有限多次。若存在大小 $0$ 的对象，它在 $A(x)$ 中贡献常数项 $c_0>0$，那么 $A(x)^k$ 对每个 $n$ 都贡献 $c_0^k$ 量级的项，取所有 $k$ 之和后系数发散，级数不再有定义。直观上，可以往序列里塞任意多个零大小对象而总大小不变，因此每个大小都有无穷多个序列。

与前后课的关系

上一讲用生成函数处理线性递推，得到 Binet 公式；这一讲处理二次方程，得到 Catalan 公式。两者的共同套路是：组合分解 $\to$ 函数方程 $\to$ 解方程 $\to$ 展开系数。

下一讲转入概率。不过生成函数不会退场：概率里的矩母函数 $\mathbb E[e^{bX}]$ 与这里的生成函数是同一套技术，只是把「计数」换成了「矩」。再往后讲 Catalan 数还会在二叉树、括号匹配与算法分析中反复出现。

What this lecture is for

The Catalan numbers $C_0,C_1,C_2,\dots=1,1,2,5,14,42,\dots$ count many objects that look unrelated: full binary trees, Dyck paths, balanced bracketings, triangulations of polygons. The previous lecture solved a linear recurrence with generating functions; this one takes on a nonlinear recurrence whose generating function satisfies a quadratic equation.

Three steps: write the equation for $C(x)$; solve it in closed form; expand by the binomial theorem to obtain

$$C_n=\frac{1}{n+1}\binom{2n}{n}.$$

Timeline

Two faces of the Catalan numbers

Two models recur throughout the lecture and give the same sequence.

• Full binary trees: every internal vertex has exactly two children. Trees with $2n+1$ vertices number $C_n$; for $n=3$ there are $5$.
• Dyck paths: walks of $2n$ steps from $0$, each step $+1$ or $-1$, never below $0$, ending at $0$. There are $C_n$ of these.

Each model supplies a route to $C(x)$, and both routes meet at the same quadratic equation.

The recurrence from binary trees

A full binary tree that is not a single vertex consists of a root and two subtrees. Suppose the whole tree has $2n+1$ vertices and the left subtree has $2j+1$; then the right subtree has

$$(2n+1)-1-(2j+1)=2(n-j-1)+1$$

vertices. The two shapes are chosen independently, so

$$C_n=\sum_{j=0}^{n-1}C_j\,C_{n-j-1}.$$

Check $n=3$:

$$C_3=C_0C_2+C_1C_1+C_2C_0=1\cdot2+1\cdot1+2\cdot1=5 .$$

This convolution has exactly the shape of a product coefficient. Let $C(x)=\sum_{n\ge0}C_nx^n$. The coefficient of $x^{n-1}$ in $C(x)^2$ is $\sum_{j=0}^{n-1}C_jC_{n-1-j}$, which is $C_n$; multiplying by $x$ raises the degree to $n$:

$$C(x)=1+x\,C(x)^2 .$$

The constant $1$ accounts for $C_0=1$ (the single-vertex tree, and also the empty path). This is the key step: the recurrence becomes an algebraic equation for the unknown function $C(x)$.

Solving the quadratic

Rewrite in standard form:

$$xC(x)^2-C(x)+1=0 .$$

With $x$ as the quadratic coefficient, the roots are

$$C(x)=\frac{1\pm\sqrt{1-4x}}{2x}.$$

Both roots satisfy the equation algebraically; the initial condition must eliminate one.

Let $x\to0$. The numerator tends to $1\pm1$ while the denominator tends to $0$:

• With the plus sign the numerator tends to $2$ and the quotient diverges, so it cannot equal $C(0)=1$.
• With the minus sign the numerator tends to $0$ and a limit must be taken.

One application of L'Hôpital (or the expansion in the next section) gives

$$\lim_{x\to0}\frac{1-\sqrt{1-4x}}{2x} =\lim_{x\to0}\frac{\frac{2}{\sqrt{1-4x}}}{2}=1 .$$

Hence

$$C(x)=\frac{1-\sqrt{1-4x}}{2x}.$$

The constant term is $1$, matching $C_0$. This check is not cosmetic: a generating function is a formal power series, its value at $x=0$ is its constant term, and the wrong root produces a $1/x$ singularity that prevents expansion altogether.

Expanding with the binomial theorem

To read off the coefficient of $x^n$ we need the expansion of $\sqrt{1-4x}=(1-4x)^{1/2}$. The generalized binomial theorem applies to fractional exponents:

$$(1+a)^{1/2}=\sum_{k\ge0}\binom{1/2}{k}a^k ,$$

where

$$\binom{1/2}{k} =\frac{\frac12\left(-\frac12\right)\left(-\frac32\right)\cdots\left(\frac32-k\right)}{k!} =\frac{(-1)^{k-1}(2k-3)!!}{2^k\,k!}\quad(k\ge1),$$

and $(2k-3)!!=1\cdot3\cdot5\cdots(2k-3)$ is the double factorial. Substituting $a=-4x$:

$$\binom{1/2}{k}(-4x)^k =\frac{(-1)^{k-1}(2k-3)!!}{2^k\,k!}\cdot(-1)^k4^kx^k =-\frac{(2k-3)!!\,2^k}{k!}x^k .$$

The signs cancel pairwise and every term is negative, so

$$1-\sqrt{1-4x} =\sum_{k\ge1}\frac{(2k-3)!!\,2^k}{k!}x^k .$$

Dividing by $2x$ shifts $x^k$ to $x^{k-1}$:

$$C(x)=\sum_{k\ge1}\frac{(2k-3)!!\,2^{k-1}}{k!}x^{k-1}.$$

Set $n=k-1$, i.e. $k=n+1$:

$$C_n=\frac{(2n-1)!!\,2^{n}}{(n+1)!}.$$

Converting to a binomial coefficient

Use

$$(2n-1)!!=\frac{(2n)!}{2^n\,n!},$$

since the product of all integers from $1$ to $2n$ divided by the even factors $2^n n!$ leaves the odd factors. Substituting:

$$C_n=\frac{(2n)!}{2^n n!}\cdot\frac{2^n}{(n+1)!} =\frac{(2n)!}{n!\,(n+1)!} =\frac{1}{n+1}\binom{2n}{n}.$$

Check: $n=3$ gives $\frac14\binom63=20/4=5$, and $5!!\cdot2^3/4!=15\cdot8/24=5$. Also $C_4=\frac15\binom84=70/5=14$, matching the enumeration.

A second route: decomposing Dyck paths

Every Dyck path admits a canonical decomposition: cut it at its first return to $0$.

Each nonempty path is uniquely

$$\text{(up step)}+\text{(a Dyck path)}+\text{(down step)}+\text{(another Dyck path)}.$$

The leading block "up step, Dyck path, down step" is called a raised Dyck path: it starts at $0$, begins with an up step, ends with a down step, stays at least $1$ in between, and returns to $0$ only at the end. Removing the first and last steps leaves an ordinary Dyck path lifted one level.

Therefore:

• Raised paths have generating function $D(x)=x\,C(x)$: the factor $x$ records the two extra steps, $C(x)$ the path in between.
• Every Dyck path is a sequence of raised paths (possibly empty), so the sequence theorem gives

$$C(x)=\frac{1}{1-D(x)}=\frac{1}{1-xC(x)} .$$

Multiplying by $1-xC(x)$:

$$C(x)-xC(x)^2=1,$$

that is,

$$xC(x)^2-C(x)+1=0 .$$

This is the same quadratic equation obtained from binary trees. Two entirely different combinatorial decompositions landing on one algebraic equation is one of the most attractive features of the method.

The sequence theorem

The theorem used above deserves a standalone statement.

Let every object of $A$ have size at least $1$, and let $A(x)=\sum_{n\ge1}a_nx^n$. Then finite sequences of $A$-objects, including the empty sequence, have generating function

$$\frac{1}{1-A(x)} .$$

Why must sizes be at least $1$? If an object of size $0$ existed, any number of copies could be inserted without changing the total size, so every size would admit infinitely many sequences, the coefficients would not be finite numbers, and the generating function would be meaningless.

For Dyck paths the objects being sequenced are raised paths, whose shortest length is $2$ and whose size we take to be $1$, so the hypothesis holds; the empty sequence corresponds to the empty path and contributes the constant term $1$.

Application: tiling a $2\times n$ strip

Tile a $2\times n$ strip with two shapes that may be reflected. First count indecomposable pieces: tilings that no vertical line can split into two separately tileable strips.

• $a_3=2$: the shortest indecomposable piece has length $3$, and reflecting it horizontally gives the second.
• $a_4=0$: length $4$ cannot be built indecomposably.
• $a_5=2$, $a_6=0$, $a_7=2$, and so on.

In general,

$$a_{2k}=0,\qquad a_{2k+1}=2\quad(k\ge1).$$

Intuitively, to leave no vertical cut, an "L" piece must cap each end with any number of "Z" pieces between them, so indecomposable pieces have odd length and come in two mirror images.

Hence

$$A(x)=\sum_{k\ge1}2x^{2k+1}=2x^3\left(1+x^2+x^4+\cdots\right)=\frac{2x^3}{1-x^2}.$$

Every tiling is a sequence of indecomposable pieces:

$$B(x)=\frac{1}{1-A(x)} =\frac{1}{1-\dfrac{2x^3}{1-x^2}} =\frac{1-x^2}{1-x^2-2x^3}.$$

Reading off the recurrence

Comparing coefficients in $B(x)(1-x^2-2x^3)=1-x^2$:

$$b_n=b_{n-2}+2b_{n-3}\quad(n\ge3),$$

with initial values

$$b_0=1,\ b_1=0,\ b_2=0,\ b_3=2,\ b_4=0,\ b_5=2,\ b_6=4,\ b_7=2,\ b_8=8 .$$

That $b_2=0$ rather than $1$ reflects the fact that adding a piece of length $2$ to the empty tiling is not allowed — the shortest indecomposable piece has length $3$. As in the previous lecture's tiling example, the denominator encodes the recurrence and the numerator encodes the initial conditions.

The recurrence is also visible directly: any nonempty tiling ends either with a vertical piece of length $2$ ($b_{n-2}$ ways) or with a length-$3$ indecomposable piece in one of two orientations ($2b_{n-3}$ ways).

What this lecture establishes

• $1,1,2,5,14,\dots$ satisfy $C_n=\sum_{j=0}^{n-1}C_jC_{n-j-1}$.
• The generating function satisfies $C(x)=1+xC(x)^2$, with solution $C(x)=\dfrac{1-\sqrt{1-4x}}{2x}$; the minus sign is forced by $C(0)=1$.
• Binomial expansion gives $C_n=\dfrac{(2n-1)!!\,2^n}{(n+1)!}=\dfrac{1}{n+1}\dbinom{2n}{n}$.
• Decomposing Dyck paths at the first return gives $C(x)=\dfrac{1}{1-xC(x)}$, the same equation as for trees.
• Sequence theorem: with all sizes at least $1$, sequences have generating function $1/(1-A(x))$.
• Tiling: $A(x)=\dfrac{2x^3}{1-x^2}$, $B(x)=\dfrac{1-x^2}{1-x^2-2x^3}$, so $b_n=b_{n-2}+2b_{n-3}$.

Comprehension check

1. Explain $C_n=\sum_{j=0}^{n-1}C_jC_{n-j-1}$ using vertex counts.

Reference answer: A full binary tree with $2n+1$ vertices consists of a root, a left subtree and a right subtree. If the left subtree has $2j+1$ vertices, the right has $(2n+1)-1-(2j+1)=2(n-j-1)+1$. There are $C_j$ shapes on the left and $C_{n-j-1}$ on the right, independently, so the count multiplies. Summing $j$ from $0$ to $n-1$ covers all left-subtree sizes.

2. Why is the minus sign chosen when solving for $C(x)$? Give a rigorous reason.

Reference answer: The two roots are $(1\pm\sqrt{1-4x})/(2x)$. A generating function must have constant term $C_0=1$, i.e. $\lim_{x\to0}C(x)=1$. The plus sign has numerator tending to $2$ and a vanishing denominator, so the quotient diverges. The minus sign gives, by L'Hôpital, $\lim_{x\to0}\frac{1-\sqrt{1-4x}}{2x}=\lim_{x\to0}\frac{2/\sqrt{1-4x}}{2}=1$. Only the minus sign yields a finite constant term; the plus sign produces a $1/x$ term and is not a formal power series.

3. Derive $C_n=\frac{1}{n+1}\binom{2n}{n}$ from $C(x)=\frac{1-\sqrt{1-4x}}{2x}$, showing the double-factorial step.

Reference answer: Using $(1+a)^{1/2}=\sum_k\binom{1/2}{k}a^k$ and $\binom{1/2}{k}=(-1)^{k-1}(2k-3)!!/(2^kk!)$, with $a=-4x$ we get $\binom{1/2}{k}(-4x)^k=-(2k-3)!!2^kx^k/k!$. Hence $1-\sqrt{1-4x}=\sum_{k\ge1}(2k-3)!!2^kx^k/k!$, and dividing by $2x$ gives $C_n=(2n-1)!!2^n/(n+1)!$. Then $(2n-1)!!=(2n)!/(2^nn!)$, so the $2^n$ cancels and $C_n=(2n)!/(n!(n+1)!)=\frac{1}{n+1}\binom{2n}{n}$.

4. Why is the generating function of raised Dyck paths $D(x)=xC(x)$?

Reference answer: A raised path starts at $0$, its first step is up and its last is down, it stays at least $1$ in between, and it returns to $0$ only at the end. Removing the first and last steps and shifting down by one level leaves an arbitrary Dyck path. So raised paths correspond bijectively to "a Dyck path plus two extra steps". With the lecture's size convention (half the number of steps), the two extra steps contribute a factor $x$, hence $D(x)=xC(x)$.

5. In the tiling problem, why is $a_{2k}=0$ but $a_{2k+1}=2$? Why is $b_2=0$?

Reference answer: An indecomposable piece admits no vertical cut into two tileable strips. The two tile shapes force odd length: the shortest case has length $3$, and each extra pair of "Z" pieces adds $2$ while the ends must be capped by mirror-image "L" pieces. So only lengths $2k+1$ occur, each in exactly two mirror forms, giving $a_{2k+1}=2$ and $a_{2k}=0$. $b_2=0$ because the empty tiling cannot be extended to length $2$ by adding an indecomposable piece — the shortest has length $3$; the recurrence itself only starts at $n=3$.

6. Why does the sequence theorem require objects of size at least $1$? What goes wrong otherwise?

Reference answer: The sequence generating function is $1+A+A^2+\cdots=1/(1-A)$, and this identity holds as a formal power series only if each $x^n$ receives finitely many contributions. A size-zero object adds a positive constant term $c_0$ to $A(x)$; then $A(x)^k$ contributes on the order of $c_0^k$ at every degree, and summing over all $k$ makes the coefficients diverge. Intuitively, arbitrarily many zero-size objects can be inserted without changing the total size, so every size has infinitely many sequences.

Relation to neighbouring lectures

The previous lecture used generating functions on a linear recurrence to obtain Binet's formula; this one solves a quadratic to obtain the Catalan formula. Both follow the same pattern: combinatorial decomposition $\to$ functional equation $\to$ solve $\to$ expand.

The next lecture turns to probability, but generating functions do not disappear: the moment-generating function $\mathbb E[e^{bX}]$ is the same technique with counting replaced by moments. Catalan numbers reappear later in binary trees, bracketings and the analysis of algorithms.