计数的两条路线

这一讲只做一件事：数清楚有多少种可能。工具只有两个。

第一个是直接算：把选择过程拆成有序的步骤，每一步乘上选择数，最后修正重复。二项式系数就是这样来的。

第二个是双射：如果能构造一个一一对应，把陌生的对象换成熟悉的对象，计数就自动相等。卡特兰数的公式正是靠一个巧妙的反射对应证明的——那个证明很难凭空想到，但理解之后极为漂亮。

时间轴

二项式系数

先按顺序选，再除以重复

从 $n$ 个对象中选 $k$ 个，最自然的做法是一个一个选：

$$n\ \cdot\ (n-1)\ \cdot\ (n-2)\ \cdots\ (n-k+1).$$

第一个有 $n$ 种选法，第二个剩 $n-1$ 种，依此类推，共 $k$ 个因子。

但这个乘积数多了：选 $\{3,4\}$ 与选 $\{4,3\}$ 被当成了两种。同一组 $k$ 个对象可以用 $k!$ 种顺序被选出，所以除以 $k!$：

$$\binom nk=\frac{n(n-1)\cdots(n-k+1)}{k!}=\frac{n!}{k!\,(n-k)!}.$$

分子分母同乘 $(n-k)!$ 就得到最常用的阶乘形式。

双重计数：帕斯卡恒等式

命题。 $\binom nk=\binom{n-1}{k-1}+\binom{n-1}{k}$。

证明（双重计数）。 数「从 $n$ 个对象中选 $k$ 个」的方法数，换一种分类方式：固定其中一个对象（比如第 $n$ 个），按它是否被选中分成两类。

• 选中它：还要从其余 $n-1$ 个中选 $k-1$ 个，有 $\binom{n-1}{k-1}$ 种。
• 不选它：要从其余 $n-1$ 个中选 $k$ 个，有 $\binom{n-1}{k}$ 种。

两类互斥且穷尽，所以总数是两者之和。而这批对象的总数本来记作 $\binom nk$，两边相等。$\square$

这个证明没有展开任何阶乘，只做了一件事：把同一批对象按两种方式分类并计数。双重计数之所以强大，就在于它绕开了代数运算，直接把组合意义翻译成等式。

帕斯卡三角与对称性

把 $\binom nk$ 按 $n$ 排成行，就得到帕斯卡三角：

$$\begin{array}{ccccccc} & & 1 & & & &\\ & 1 & & 1 & & &\\ 1 & & 2 & & 1 & &\\ 1 & & 3 & & 3 & & 1\\ 1 & & 4 & & 6 & & 4 & & 1 \end{array}$$

每个数等于它上方两个数之和，这正是帕斯卡恒等式。三角形左右对称，给出

$$\binom nk=\binom n{n-k}.$$

代数上也一眼可见：$\frac{n!}{k!(n-k)!}$ 在把 $k$ 换成 $n-k$ 时形式不变。组合意义是：选 $k$ 个等价于决定「不选哪 $n-k$ 个」。

多项式系数

把 $n$ 个对象分成三组，大小分别为 $a,b,c$，且 $a+b+c=n$，组是有标签的（第一组、第二组、第三组），组内无序。方法数是

$$\binom{n}{a,b,c}=\frac{n!}{a!\,b!\,c!}.$$

证明。 先选第一组：$\binom na$ 种；再从剩下的 $n-a$ 个里选第二组：$\binom{n-a}{b}$ 种；剩下的自动是第三组。相乘：

$$\binom na\binom{n-a}{b} =\frac{n!}{a!\,(n-a)!}\cdot\frac{(n-a)!}{b!\,(n-a-b)!} =\frac{n!}{a!\,b!\,c!},$$

因为 $n-a-b=c$。$\square$

这个「先选一组、再选下一组」的乘法结构可以推广到任意多组：

$$\binom{n}{a_1,\dots,a_k}=\frac{n!}{a_1!\,a_2!\cdots a_k!}, \qquad a_1+\cdots+a_k=n .$$

也可以按「最后一个对象落在哪一组」做双重计数，得到与帕斯卡恒等式同型的递推。

双射：把陌生的计数换成熟悉的计数

定义

设 $f:A\to B$。

• 单射：$a_1\ne a_2\Rightarrow f(a_1)\ne f(a_2)$，不同对象不会撞到同一个像。
• 满射：对每个 $b\in B$，存在 $a\in A$ 使 $f(a)=b$，$B$ 中每个元素都被取到。
• 双射：既是单射又是满射。

等价地，$f$ 是双射当且仅当存在逆映射 $g:B\to A$，满足

$$g(f(a))=a\quad\text{对一切 }a\in A, \qquad f(g(b))=b\quad\text{对一切 }b\in B .$$

为什么有逆映射就一定是双射。 先证单射：若 $f(a_1)=f(a_2)$，两边作用 $g$ 得

$$a_1=g(f(a_1))=g(f(a_2))=a_2 .$$

再证满射：对任意 $b\in B$，取 $a=g(b)$，则

$$f(a)=f(g(b))=b .$$

所以 $B$ 中每个元素都有原像。$\square$

双射为什么能用来计数

若存在双射 $f:A\to B$，则 $|A|=|B|$。于是要数清 $A$，只需构造一个到已知大小的 $B$ 的双射。难点从来不是验证双射，而是想到该往哪里映射。

星线法：给球染色

问题

有 $n$ 个球、$j$ 种颜色。只关心每种颜色用了几个，不关心具体哪个球是什么颜色。问有多少种染色方案？

例子：$n=4$、$j=3$

把方案按「各颜色的球数」分类（红、蓝、绿）：

• $(4,0,0)$：3 种（选一种颜色涂 4 个球）。
• $(3,1,0)$：$3\times2=6$ 种（选 3 个的那色有 3 种，选 1 个的那色剩 2 种）。
• $(2,2,0)$：3 种（选不用的颜色有 3 种）。
• $(2,1,1)$：3 种（选涂 2 个的颜色有 3 种）。

合计

$$3+6+3+3=15=\binom62 .$$

注意 $\binom62=15$，而不是 $\binom52=10$——课程在这里特意纠正了一次口误。

双射：球与隔板

把每个球画成一颗星，把颜色之间用隔板分开：$j$ 种颜色需要 $j-1$ 块隔板。

以 $(2,1,1)$ 为例：

$$\star\star\mid\star\mid\star$$

读法：第一块隔板前是红色，两块隔板之间是蓝色，最后一块之后是绿色。某种颜色一个球都没有时，就让对应隔板相邻或贴在端点，例如

$$\mid\star\star\star\star\mid$$

表示红色 $0$ 个、蓝色 $4$ 个、绿色 $0$ 个。

这是双射。 正向：给定染色方案，按颜色顺序排好球并插入隔板。反向：给定星与隔板的排列，按隔板位置读出各颜色的球数。两个方向都唯一，所以方案数等于

$$\text{在 } n+(j-1) \text{ 个位置中选 } j-1 \text{ 个放隔板} =\binom{n+j-1}{j-1}.$$

取 $n=4$、$j=3$：$\binom{4+2}{2}=\binom62=15$，与枚举一致。

等价地，这也是非负整数解 $x_1+\cdots+x_j=n$ 的个数：每个 $x_i$ 是第 $i$ 种颜色的球数。

Dyck 路径与卡特兰数

定义

Dyck 路径是从 $(0,0)$ 走到 $(2n,0)$ 的路径，每一步是 $(1,+1)$ 或 $(1,-1)$，并且全程不低于横轴。

由起点与终点可知，路径恰有 $n$ 步向上、$n$ 步向下。第一步必向上，最后一步必向下。

长度 $2n$ 的 Dyck 路径的条数记作 $c_n$，称为第 $n$ 个卡特兰数。

小值：

• $c_1=1$：只有「上、下」。
• $c_2=2$：「上下上下」与「上上下下」。
• $c_3=5$。

序列开头是

$$1,\ 1,\ 2,\ 5,\ 14,\ 42,\ 132,\dots$$

（第一位 $c_0=1$ 对应空路径。）课程提到，Richard Stanley 曾整理出约两百种被卡特兰数计数的对象——它出现在数学的许多角落。

另外两种被计数的对象

• 平面树（plane tree，带根、左右子树有区别）：$n$ 条边的平面树有 $c_n$ 棵。$n=3$ 时有 $5$ 棵，左右镜像算作不同的两棵。
• 满二叉树（每个内部节点恰有两个孩子）：$n$ 个内部节点时有 $c_n$ 棵。

对树有一个基本事实：满二叉树的叶子数总比内部节点数多 $1$。证明用归纳：只有一个内部节点（两个叶子）时成立；把某个叶子替换成「内部节点 + 两个叶子」，叶子数加 $1$、内部节点数加 $1$，差值不变。等价地，任何树都满足「顶点数 = 边数 + 1」。

卡特兰公式

定理。 $c_n=\dfrac{1}{n+1}\dbinom{2n}{n}$。

先验证 $n=2$：

$$c_2=\frac13\binom42=\frac13\cdot6=2,$$

与枚举一致。

证明：数坏路径

所有从 $(0,0)$ 到 $(2n,0)$ 的路径（允许低于横轴）共有

$$\binom{2n}{n}$$

条：在 $2n$ 步中选 $n$ 步向上。Dyck 路径就是其中不碰横轴下方的那些，所以

$$c_n=\binom{2n}{n}-\#\{\text{坏路径}\}.$$

反射双射：坏路径 ↔ 到 $-2$ 的路径

一条坏路径必然在某个时刻首次到达高度 $-1$。把从该点起的整段路径关于直线 $y=-1$ 反射，得到一条新路径。

反射后：

• 起点仍是 $(0,0)$，终点从 $(2n,0)$ 变成 $(2n,-2)$；
• 每一步仍是 $(1,\pm1)$；
• 这条新路径必然低于横轴，因此一定不是 Dyck 路径。

反向操作：对任意一条从 $(0,0)$ 到 $(2n,-2)$ 的路径，它必然在某个时刻首次到达 $-1$；把该点之后的部分再关于 $y=-1$ 反射回去，就唯一还原出一条坏路径。

两个方向互逆，所以这是一个双射。于是

$$\#\{\text{坏路径}\}=\#\{\text{从 }(0,0)\text{ 到 }(2n,-2)\text{ 的路径}\}.$$

后者需要终点高度为 $-2$，即向下比向上多 $2$ 步：设向上 $u$ 步、向下 $d$ 步，

$$u+d=2n,\qquad u-d=-2 \;\Longrightarrow\; u=n-1,\quad d=n+1 .$$

所以

$$\#\{\text{坏路径}\}=\binom{2n}{n-1}.$$

化简

$$\begin{aligned} c_n &=\binom{2n}{n}-\binom{2n}{n-1}\\ &=\frac{(2n)!}{n!\,n!}-\frac{(2n)!}{(n-1)!\,(n+1)!}\\ &=\frac{(2n)!}{n!\,n!}\left(1-\frac{n}{n+1}\right)\\ &=\frac{1}{n+1}\binom{2n}{n}. \end{aligned}$$

中间用到了 $\binom{2n}{n-1}=\binom{2n}{n}\cdot\frac{n}{n+1}$。$\square$

课程坦言：这个反射想法很难凭空想到。几周后用生成函数可以机械地推出同一个公式，只是计算更长、美感稍逊。

二叉树 ↔ Dyck 路径

从树到路径

对满二叉树做一次「绕树一周」的遍历（先序遍历），每个节点第一次被访问时记一次。把内部节点记为 $+1$，叶子记为 $-1$，按访问顺序读出序列，再把它画成上下步。

• 满二叉树有 $n$ 个内部节点、$n+1$ 个叶子，共 $2n+1$ 步；
• 第一步与最后一步都是叶子（$-1$）；
• 因为叶子总比内部节点多 $1$，全程高度不低于 $0$。

去掉最后一步，就得到一条长度 $2n$ 的 Dyck 路径。

从路径到树

反向：从左到右读路径，遇到向上步就新建一个内部节点，并把新的两个叶子挂上；遇到向下步就结束当前这条分支。路径结束且内部节点数为 $n$ 时，恰好得到一棵满二叉树。

两个方向互逆，所以满二叉树与 Dyck 路径一一对应，二者都由卡特兰数计数。

这个双射的价值不只是「又一种卡特兰对象」，它把递归结构（树）与线性序列（路径）连接起来——后面用生成函数时，这种连接正是把递归方程变成代数方程的关键。

斯特林公式与渐近

斯特林公式。

$$n!\approx\sqrt{2\pi n}\left(\frac ne\right)^{n}.$$

用它估计中心二项式系数：把 $2n$ 与 $n$ 代入并相除，

$$\binom{2n}{n}=\frac{(2n)!}{(n!)^2} \approx\frac{\sqrt{4\pi n}\,(2n/e)^{2n}}{2\pi n\,(n/e)^{2n}} =\frac{4^n}{\sqrt{\pi n}} .$$

于是卡特兰数的增长阶为

$$c_n=\frac{1}{n+1}\binom{2n}{n} \approx\frac{4^n}{\sqrt{\pi}\,n^{3/2}} .$$

也就是说，$c_n$ 以 $4^n$ 的速度指数增长，再被 $n^{3/2}$ 压低。课程没有证明斯特林公式，只指出：除了常数 $\sqrt\pi$ 之外的部分都能用初等微积分或初等概率推出，而那个常数才是真正棘手的部分。

本节结论

• $\binom nk=\frac{n!}{k!(n-k)!}$：先有序选取，再除以 $k!$ 修正顺序。
• 帕斯卡恒等式 $\binom nk=\binom{n-1}{k-1}+\binom{n-1}{k}$ 由双重计数得到：按某个固定元素选不选分类。
• $\binom nk=\binom n{n-k}$：对称性。
• 多项式系数 $\binom{n}{a_1,\dots,a_k}=\frac{n!}{a_1!\cdots a_k!}$，由「逐组选取」相乘得到。
• 双射 $f:A\to B$ 给出 $|A|=|B|$；等价条件是存在逆映射。
• 星线法：$n$ 个球染 $j$ 色的方案数是 $\binom{n+j-1}{j-1}$。
• 卡特兰数 $c_n=1,2,5,14,42,\dots$ 计数 Dyck 路径、平面树与满二叉树。
• 卡特兰公式 $c_n=\frac{1}{n+1}\binom{2n}{n}$，由反射双射把坏路径对应到终点为 $-2$ 的路径。
• 渐近：$\binom{2n}{n}\approx\frac{4^n}{\sqrt{\pi n}}$，$c_n\approx\frac{4^n}{\sqrt\pi\,n^{3/2}}$。

理解检验

1. 从 $n$ 个里选 $k$ 个，为什么要除以 $k!$？如果只选 $1$ 个，这个修正还需要吗？

参考答案：逐步选取的乘积 $n(n-1)\cdots(n-k+1)$ 把「同一组对象的 $k!$ 种选取顺序」都数成了不同的结果。例如从 $\{1,2,3,4,5\}$ 中选 $3$ 个，选 $\{1,2,3\}$ 可以按 $123,132,213,231,312,321$ 六种顺序发生，但它们是同一个集合。每组集合被数了 $k!$ 次，所以除以 $k!$。当 $k=1$ 时 $1!=1$，修正项不起作用——只选一个元素时不存在顺序问题。

2. 用双重计数证明帕斯卡恒等式，并说明两种分类为什么互斥且穷尽。

参考答案：要数「从 $n$ 个对象中选 $k$ 个」的方案数 $\binom nk$。固定第 $n$ 个对象，按它是否被选中分成两类：

• 选中：还需从其余 $n-1$ 个中选 $k-1$ 个，共 $\binom{n-1}{k-1}$ 种；
• 不选：需从其余 $n-1$ 个中选 $k$ 个，共 $\binom{n-1}{k}$ 种。 任何一个 $k$ 元子集要么包含第 $n$ 个对象、要么不包含，两者不可能同时成立（互斥），且没有第三种情形（穷尽）。所以总数等于两类之和：

$$\binom nk=\binom{n-1}{k-1}+\binom{n-1}{k}.$$

3. 用星线法计算：$5$ 个球染 $3$ 种颜色，只区分每种颜色的球数，有多少种方案？

参考答案：需要 $j-1=2$ 块隔板，总位置数为 $n+j-1=5+2=7$，从中选 $2$ 个放隔板：

$$\binom{7}{2}=21 .$$

也可以看成非负整数解 $x_1+x_2+x_3=5$ 的个数，由星线法同样是 $\binom{5+3-1}{3-1}=21$。枚举核对：把 $5$ 分成三部分（含 $0$）的个数是 $21$。

4. 计算 $c_3$，并说明反射双射把什么样的路径映射成什么样的路径。

参考答案：$\binom63=20$，坏路径数为 $\binom62=15$，故 $c_3=20-15=5$。反射双射把「从 $(0,0)$ 到 $(6,0)$ 且曾经低于横轴的路径」映射为「从 $(0,0)$ 到 $(6,-2)$ 的任意路径」：找到路径首次到达高度 $-1$ 的位置，把该点之后的部分关于直线 $y=-1$ 反射。反向操作是对到 $(6,-2)$ 的路径找首次到达 $-1$ 的位置，再把之后的部分反射回去。两个方向互逆，所以坏路径的条数等于到 $(6,-2)$ 的路径条数，而后者需要 $2$ 步向上、$4$ 步向下，共 $\binom62$ 条。

5. 为什么满二叉树的叶子数总比内部节点数多 $1$？这个事实在树到 Dyck 路径的双射中起什么作用？

参考答案：对内部节点数归纳。$n=1$ 时树根加两个叶子，叶子 $2$、内部节点 $1$，差为 $1$。归纳步：把任意一个叶子换成「一个内部节点 + 两个叶子」，内部节点数 $+1$、叶子数从 $1$ 变成 $2$ 即 $+1$，差值不变。所以恒有「叶子数 − 内部节点数 = 1」。在双射中它保证：$n$ 个内部节点、$n+1$ 个叶子的遍历序列共 $2n+1$ 项，且部分和始终非负（每个叶子的 $-1$ 之前必有对应的内部节点 $+1$ 支撑），于是去掉最后一步后恰得到一条长度 $2n$ 的 Dyck 路径。

6. 用斯特林公式估计 $\binom{20}{10}$，并与真值比较。

参考答案：由 $\binom{2n}{n}\approx4^n/\sqrt{\pi n}$，取 $n=10$：

$$\binom{20}{10}\approx\frac{4^{10}}{\sqrt{10\pi}}=\frac{1\,048\,576}{\sqrt{31.416}}\approx\frac{1\,048\,576}{5.605}\approx187\,100 .$$

真值是 $184\,756$，相对误差约 $1.3\%$。这说明斯特林近似在中等 $n$ 时已经相当准，而且它揭示了中心二项式系数的指数增长底数为 $4$、多项式因子为 $n^{-1/2}$。

与前后课的关系

这一讲建立了计数的两套语言：代数式的直接计算与双射的意义翻译。二项式系数与多项式系数会在概率、编码理论中反复出现；星线法直接对应「非负整数解」的计数；卡特兰数则在下一讲以生成函数的形式再次登场——届时 $c_n=\frac{1}{n+1}\binom{2n}{n}$ 会从一个关于 $C(x)$ 的二次方程里自然解出。

一句话概括：数不清的时候，先找一个能一一对应的东西；找得到，计数就变成了同一件事的两种说法。

Two routes through counting

This lecture does one thing: count how many possibilities exist. There are only two tools.

The first is direct computation: break a choice into ordered steps, multiply the numbers of options, then correct for over-counting. Binomial coefficients arise this way.

The second is bijection: if a one-to-one correspondence can be built between unfamiliar objects and familiar ones, the counts are equal. The Catalan formula is proved by exactly such a trick — a reflection that is hard to invent from scratch but beautiful once understood.

Timeline

Binomial coefficients

Choose in order, then divide by $k!$

To choose $k$ objects out of $n$, do it one at a time:

$$n\ \cdot\ (n-1)\ \cdot\ (n-2)\ \cdots\ (n-k+1).$$

The first choice has $n$ options, the second has $n-1$, and so on, for $k$ factors.

But this product over-counts: choosing $\{3,4\}$ and choosing $\{4,3\}$ are recorded as different. Each $k$-element set can be produced in $k!$ orders, so divide by $k!$:

$$\binom nk=\frac{n(n-1)\cdots(n-k+1)}{k!}=\frac{n!}{k!\,(n-k)!}.$$

Multiplying numerator and denominator by $(n-k)!$ gives the factorial form on the right.

Double counting: Pascal's identity

Claim. $\binom nk=\binom{n-1}{k-1}+\binom{n-1}{k}$.

Proof (double counting). Count the $k$-element subsets of $n$ objects again, but classify differently: fix one object (say the $n$-th) and split according to whether it is chosen.

• Chosen: choose the remaining $k-1$ from the other $n-1$, giving $\binom{n-1}{k-1}$ subsets.
• Not chosen: choose all $k$ from the other $n-1$, giving $\binom{n-1}{k}$ subsets.

The two classes are disjoint and exhaustive, so their sum counts the same collection whose size is $\binom nk$. Hence the identity. $\square$

No factorials were expanded; the proof only classifies the same objects two ways and counts each. That is why double counting is powerful: it replaces algebra with meaning.

Pascal's triangle and symmetry

Arranging $\binom nk$ by rows gives Pascal's triangle:

$$\begin{array}{ccccccc} & & 1 & & & &\\ & 1 & & 1 & & &\\ 1 & & 2 & & 1 & &\\ 1 & & 3 & & 3 & & 1\\ 1 & & 4 & & 6 & & 4 & & 1 \end{array}$$

Each entry is the sum of the two above it — exactly Pascal's identity. The symmetry of each row gives

$$\binom nk=\binom n{n-k},$$

which is also immediate from $\frac{n!}{k!(n-k)!}$, unchanged when $k$ becomes $n-k$. Combinatorially: choosing $k$ is the same as deciding which $n-k$ to leave out.

Multinomial coefficients

Split $n$ objects into three labelled groups of sizes $a,b,c$ with $a+b+c=n$; order inside a group is irrelevant. The number of ways is

$$\binom{n}{a,b,c}=\frac{n!}{a!\,b!\,c!}.$$

Proof. Choose the first group: $\binom na$. Then choose the second from the remaining $n-a$: $\binom{n-a}{b}$. Whatever remains forms the third. Multiplying,

$$\binom na\binom{n-a}{b} =\frac{n!}{a!\,(n-a)!}\cdot\frac{(n-a)!}{b!\,(n-a-b)!} =\frac{n!}{a!\,b!\,c!},$$

since $n-a-b=c$. $\square$

The "choose one group, then the next" structure extends to any number of groups:

$$\binom{n}{a_1,\dots,a_k}=\frac{n!}{a_1!\,a_2!\cdots a_k!}, \qquad a_1+\cdots+a_k=n .$$

One can also double-count by asking which group the last object fell into, recovering the same type of recurrence as Pascal's identity.

Bijections: replacing one count by another

Definitions

Let $f:A\to B$.

• Injective: $a_1\ne a_2\Rightarrow f(a_1)\ne f(a_2)$; distinct objects never collide.
• Surjective: for every $b\in B$ there is $a\in A$ with $f(a)=b$; every element of $B$ is hit.
• Bijective: both injective and surjective.

Equivalently, $f$ is a bijection exactly when there is an inverse $g:B\to A$ with

$$g(f(a))=a\quad\text{for all }a\in A, \qquad f(g(b))=b\quad\text{for all }b\in B .$$

Having an inverse forces bijectivity. Injectivity: if $f(a_1)=f(a_2)$, apply $g$:

$$a_1=g(f(a_1))=g(f(a_2))=a_2 .$$

Surjectivity: for any $b\in B$, take $a=g(b)$; then

$$f(a)=f(g(b))=b .$$

So every $b$ has a preimage. $\square$

Why bijections count

If a bijection $f:A\to B$ exists, then $|A|=|B|$. To count $A$, it suffices to build a bijection onto a set $B$ whose size is known. The difficulty is never verifying the bijection; it is thinking of where to map.

Stars and bars: colouring balls

The question

There are $n$ balls and $j$ colours. Only the number of balls of each colour matters, not which ball got which colour. How many colourings are there?

Example: $n=4$, $j=3$

Classify by the count vector (red, blue, green):

• $(4,0,0)$: $3$ ways (choose the colour used for all four).
• $(3,1,0)$: $3\times2=6$ ways (choose the colour used three times, then the colour used once).
• $(2,2,0)$: $3$ ways (choose the unused colour).
• $(2,1,1)$: $3$ ways (choose the colour used twice).

Total:

$$3+6+3+3=15=\binom62 .$$

Note $\binom62=15$, not $\binom52=10$ — the lecture corrects this slip mid-stream.

The bijection: stars and bars

Draw each ball as a star and separate colours with bars: $j$ colours need $j-1$ bars.

For $(2,1,1)$:

$$\star\star\mid\star\mid\star$$

Read off: everything before the first bar is red, between the bars is blue, after the last bar is green. A colour with zero balls corresponds to adjacent bars or a bar at an end, e.g.

$$\mid\star\star\star\star\mid$$

means red $0$, blue $4$, green $0$.

This is a bijection. Forward: given a colouring, order the balls by colour and insert the bars. Backward: given an arrangement of stars and bars, read the colour counts off the bar positions. Both directions are unique, so the number of colourings is

$$\text{choose } j-1 \text{ positions for bars among } n+(j-1) =\binom{n+j-1}{j-1}.$$

For $n=4$, $j=3$: $\binom{6}{2}=15$, matching the enumeration.

Equivalently, this counts non-negative integer solutions of $x_1+\cdots+x_j=n$, where $x_i$ is the number of balls of colour $i$.

Dyck paths and Catalan numbers

Definition

A Dyck path runs from $(0,0)$ to $(2n,0)$ using steps $(1,+1)$ and $(1,-1)$, and never goes below the horizontal axis.

Start and end force exactly $n$ up-steps and $n$ down-steps. The first step must go up and the last must go down.

The number of Dyck paths of length $2n$ is $c_n$, the $n$-th Catalan number.

Small values:

• $c_1=1$: only "up, down".
• $c_2=2$: "up, down, up, down" and "up, up, down, down".
• $c_3=5$.

The sequence begins

$$1,\ 1,\ 2,\ 5,\ 14,\ 42,\ 132,\dots$$

(with $c_0=1$ for the empty path). The lecture notes that Richard Stanley compiled roughly two hundred objects counted by Catalan numbers — they appear all over mathematics.

Two more Catalan families

• Plane trees (rooted, left and right children distinguished): $n$ edges give $c_n$ trees. For $n=3$ there are $5$, and mirror images count as different trees.
• Full binary trees (every internal node has exactly two children): $n$ internal nodes give $c_n$ trees.

A basic fact about trees: a full binary tree always has one more leaf than internal node. Induction: a single internal node with two leaves satisfies it; replacing a leaf by "one internal node plus two leaves" increases both counts by one, so the difference is preserved. Equivalently, every tree has one more vertex than edge.

The Catalan formula

Theorem. $c_n=\dfrac{1}{n+1}\dbinom{2n}{n}$.

Check $n=2$:

$$c_2=\frac13\binom42=\frac13\cdot6=2,$$

matching the enumeration.

Proof: count the bad paths

All paths from $(0,0)$ to $(2n,0)$ using up/down steps number

$$\binom{2n}{n},$$

since one chooses which $n$ of the $2n$ steps go up. Dyck paths are those that never dip below the axis, so

$$c_n=\binom{2n}{n}-\#\{\text{bad paths}\}.$$

The reflection bijection

A bad path must first reach height $-1$ at some point. Reflect the entire portion of the path after that point across the line $y=-1$. The new path:

• starts at $(0,0)$ and ends at $(2n,-2)$ instead of $(2n,0)$;
• still uses steps $(1,\pm1)$;
• necessarily lies below the axis, hence is not a Dyck path.

Conversely, given any path from $(0,0)$ to $(2n,-2)$, it must first hit $-1$ somewhere; reflecting the part after that point back across $y=-1$ uniquely recovers a bad path.

The two directions are mutually inverse, so this is a bijection. Hence

$$\#\{\text{bad paths}\}=\#\{\text{paths from }(0,0)\text{ to }(2n,-2)\}.$$

The latter has two more down-steps than up-steps. With $u$ up and $d$ down,

$$u+d=2n,\qquad u-d=-2 \;\Longrightarrow\; u=n-1,\quad d=n+1,$$

so

$$\#\{\text{bad paths}\}=\binom{2n}{n-1}.$$

Simplifying

$$\begin{aligned} c_n &=\binom{2n}{n}-\binom{2n}{n-1}\\ &=\frac{(2n)!}{n!\,n!}-\frac{(2n)!}{(n-1)!\,(n+1)!}\\ &=\frac{(2n)!}{n!\,n!}\left(1-\frac{n}{n+1}\right)\\ &=\frac{1}{n+1}\binom{2n}{n}. \end{aligned}$$

The middle step uses $\binom{2n}{n-1}=\binom{2n}{n}\cdot\frac{n}{n+1}$. $\square$

The lecture admits that the reflection idea is hard to invent from nothing. Generating functions, a few weeks later, produce the same formula mechanically — longer, but less mysterious.

Binary trees ↔ Dyck paths

Tree to path

Traverse a full binary tree around its outside (preorder), recording each vertex the first time it is visited. Mark internal nodes as $+1$ and leaves as $-1$, then read the sequence as up/down steps.

• A full binary tree with $n$ internal nodes has $n+1$ leaves, so the traversal has $2n+1$ entries;
• the first and last are leaves ($-1$);
• because leaves outnumber internal nodes by one, the running height never drops below $0$.

Dropping the final step yields a Dyck path of length $2n$.

Path to tree

Conversely, read the path left to right: an up-step creates an internal node with two fresh leaves; a down-step closes the current branch. When the path ends with $n$ internal nodes, a full binary tree has been built.

The operations are mutually inverse, so full binary trees and Dyck paths correspond one-to-one and are both counted by Catalan numbers.

The value of this bijection is not just "another Catalan family": it links a recursive structure (tree) to a linear sequence (path). That link is exactly what turns recursion into algebra when generating functions arrive.

Stirling's formula and asymptotics

Stirling's formula.

$$n!\approx\sqrt{2\pi n}\left(\frac ne\right)^{n}.$$

Apply it to the central binomial coefficient by substituting $2n$ and $n$:

$$\binom{2n}{n}=\frac{(2n)!}{(n!)^2} \approx\frac{\sqrt{4\pi n}\,(2n/e)^{2n}}{2\pi n\,(n/e)^{2n}} =\frac{4^n}{\sqrt{\pi n}} .$$

Therefore

$$c_n=\frac{1}{n+1}\binom{2n}{n} \approx\frac{4^n}{\sqrt{\pi}\,n^{3/2}} .$$

So $c_n$ grows exponentially at rate $4^n$, damped by $n^{3/2}$. The lecture does not prove Stirling's formula, only notes that everything except the constant $\sqrt\pi$ follows from elementary calculus or probability; that constant is the genuinely hard part.

What this lecture establishes

• $\binom nk=\frac{n!}{k!(n-k)!}$: choose in order, then divide by $k!$.
• Pascal's identity $\binom nk=\binom{n-1}{k-1}+\binom{n-1}{k}$ follows by classifying subsets according to a fixed element.
• $\binom nk=\binom n{n-k}$ by symmetry.
• Multinomial coefficients $\binom{n}{a_1,\dots,a_k}=\frac{n!}{a_1!\cdots a_k!}$ come from choosing groups successively.
• A bijection $f:A\to B$ gives $|A|=|B|$; equivalently it has an inverse.
• Stars and bars: colouring $n$ balls with $j$ colours gives $\binom{n+j-1}{j-1}$ schemes.
• Catalan numbers $c_n=1,2,5,14,42,\dots$ count Dyck paths, plane trees and full binary trees.
• Catalan formula $c_n=\frac{1}{n+1}\binom{2n}{n}$, proved by reflecting bad paths to paths ending at $-2$.
• Asymptotics: $\binom{2n}{n}\approx\frac{4^n}{\sqrt{\pi n}}$, $c_n\approx\frac{4^n}{\sqrt\pi\,n^{3/2}}$.

Comprehension check

1. Why divide by $k!$ when choosing $k$ of $n$, and is the correction needed when $k=1$?

Reference answer: The product $n(n-1)\cdots(n-k+1)$ treats the $k!$ orders in which the same set can be picked as different outcomes. For instance, choosing $k=3$ from $\{1,2,3,4,5\}$ counts the set $\{1,2,3\}$ six times, once for each ordering $123,132,213,231,312,321$. Dividing by $k!$ collapses them. When $k=1$, $1!=1$ and there is nothing to correct, since a single element has no ordering.

2. Prove Pascal's identity by double counting, and explain why the two classes are disjoint and exhaustive.

Reference answer: Count the $k$-element subsets of $n$ objects, $\binom nk$. Fix the $n$-th object and split:

• containing it: choose the other $k-1$ from $n-1$, giving $\binom{n-1}{k-1}$;
• not containing it: choose all $k$ from $n-1$, giving $\binom{n-1}{k}$. Every $k$-subset either contains the fixed object or does not; the cases cannot both hold (disjoint) and there is no third option (exhaustive). Hence

$$\binom nk=\binom{n-1}{k-1}+\binom{n-1}{k}.$$

3. Using stars and bars, how many ways are there to colour $5$ balls with $3$ colours, if only the counts per colour matter?

Reference answer: There are $j-1=2$ bars and $n+j-1=5+2=7$ positions in total, so the number is

$$\binom{7}{2}=21 .$$

Equivalently, it counts non-negative integer solutions of $x_1+x_2+x_3=5$, which is $\binom{5+3-1}{3-1}=21$. Enumerating the partitions of $5$ into three non-negative parts confirms $21$.

4. Compute $c_3$ and describe what the reflection bijection maps to what.

Reference answer: $\binom63=20$ total paths and $\binom62=15$ bad paths, so $c_3=20-15=5$. The bijection maps "paths from $(0,0)$ to $(6,0)$ that dip below the axis" to "all paths from $(0,0)$ to $(6,-2)$": find the first point where the path reaches height $-1$ and reflect everything after it across $y=-1$. The inverse takes a path ending at $(6,-2)$, finds its first hit of $-1$, and reflects back. Since the maps are mutually inverse, the number of bad paths equals the number of paths to $(6,-2)$, which require $2$ up-steps and $4$ down-steps, namely $\binom62$.

5. Why does a full binary tree always have one more leaf than internal node, and where is that used in the tree-to-path bijection?

Reference answer: Induct on internal nodes. For $n=1$ the tree is a root with two leaves: $2$ leaves, $1$ internal node, difference $1$. In the induction step, replace any leaf by one internal node with two leaves: internal nodes increase by $1$ and leaves go from $1$ to $2$, also increasing by $1$, so the difference is preserved. Hence "leaves − internal nodes = 1" always. In the bijection this guarantees that the traversal sequence has $2n+1$ entries and that every prefix has at least as many $+1$s as $-1$s (each leaf's $-1$ is backed by an earlier internal node's $+1$), so dropping the final step gives a genuine Dyck path.

6. Use Stirling's formula to estimate $\binom{20}{10}$ and compare with the exact value.

Reference answer: From $\binom{2n}{n}\approx4^n/\sqrt{\pi n}$ with $n=10$,

$$\binom{20}{10}\approx\frac{4^{10}}{\sqrt{10\pi}}=\frac{1\,048\,576}{\sqrt{31.416}}\approx\frac{1\,048\,576}{5.605}\approx187\,100 .$$

The exact value is $184\,756$, a relative error of about $1.3\%$. The approximation is already accurate at moderate $n$ and reveals the exponential base $4$ together with the polynomial factor $n^{-1/2}$.

Relation to neighbouring lectures

This lecture builds two languages of counting: direct algebraic computation and bijective translation of meaning. Binomial and multinomial coefficients recur in probability and coding theory; stars and bars is exactly the count of non-negative integer solutions; Catalan numbers return with generating functions, where $c_n=\frac{1}{n+1}\binom{2n}{n}$ falls out of a quadratic equation for $C(x)$.

One sentence to keep: when the count is out of reach, look for something to correspond it with one-to-one; once found, counting becomes two ways of saying the same thing.