10.4 Catalan 数与 Stirling 数

本节对应原书 PDF 第 258–263 页。定义、定理、公式、例题及其原解答逐字取自原书；解释性文字为 AI 通俗化改写；标有「解读」的引用块为 AI 补充的额外直觉。

有很多种重要的组合计数，如集合的排列数 P(m,n)、集合的组合数 C(m,n)、多重集的全排列数、Fibonacci 数、Catalan 数、Stirling 数等.这些计数广泛应用于各个领域的实际问题.本节主要讨论 Catalan 数与 Stirling 数.

定义 10.8 给定一个凸 n+1 边形，通过在内部不相交的对角线把它划分成三角形，不同的划分方案数称作 Catalan 数，记作 h_n.

例如 h_5=5，说明对一个五边形进行三角划分，共有 5 种不同的方案.图 10.7 列出了这 5 种方案.

解读：注意下标的错位：h_n 对应的是 n+1 边形.这样取下标是为了让递推式 h_n=\sum h_kh_{n-k} 干净，读题时别把 h_5 当成五边形以外的边形.

为确定 h_n，先要建立关于 h_n 的递推方程.考虑 n+1 条边的多边形，端点分别被标记为 A_1,A_2,\cdots,A_{n+1}.将 A_1A_{n+1} 的边记为 a，作为三角形的底边.选择底边以外的顶点 A_{k+1}(k=1,2,\cdots,n-1)，那么底边 a，边 A_{k+1}A_1 和 A_{n+1}A_{k+1} 就构成三角形 T，T 将多边形划分成 R_1 和 R_2 两个部分，分别为 k+1 边形和 n-k+1 边形.划分结果如图 10.8 所示.k+1 边形 R_1 和 n-k+1 边形 R_2 的三角划分方案数分别为 h_k 和 h_{n-k}，根据乘法法则和加法法则，\sum\limits_{k=1}^{n-1}h_kh_{n-k} 就是 n+1 边形的划分方案总数.因此得到下面的递推方程

例 10.20 已经利用生成函数求解了这个递推方程，它的解是 h_n=\frac{1}{n}\binom{2n-2}{n-1}.

解读：这个"钉住一条边、枚举第三个顶点"的分解是 Catalan 数的通用套路：三角形 T 把问题切成左右两块互不干扰的子问题，所以是乘积；k 有 n-1 种取法，所以是求和.两类子问题规模相加恰好为 n，这就是卷积形式递推的来源.

Catalan 数出现在许多组合计数问题中，如前面遇到的从 (0,0) 点到 (n,n) 点除端点外不接触对角线的非降路径计数问题、堆栈输出序列的计数问题等.除此之外，还有 n 个位置固定的数的乘法顺序的计数问题、圆周上 2n 个点用不在内部相交的弦两两配对的方案的计数问题等，有兴趣的读者可以进一步阅读有关的参考书.

下面考虑第一类 Stirling 数.

定义 10.9 考虑多项式 x(x-1)(x-2)\cdots(x-n+1) 的展开式

将上述展开式中 x^r 的系数的绝对值 S_r 记作 \begin{bmatrix}n\\ r\end{bmatrix}，称为第一类 Stirling 数.

不难证明第一类 Stirling 数满足下面的递推方程

证明 将等式

代入下述等式后得到

由于两边的 x^r 的系数应该相等，所以有

下面计算两个初值.根据第一类 Stirling 数的定义，不难得到 \begin{bmatrix}n\\ 0\end{bmatrix}=0.为得到展开式中 x 的系数，除了乘积项中的第一项 x 之外，其他各项只能提供常数，即分别贡献 -1,-2,\cdots,-(n-1).如果不考虑正负号，这些项的乘积是 (n-1)!，因此 \begin{bmatrix}n\\ 1\end{bmatrix}=(n-1)!.

第一类 Stirling 数的递推公式与 Pascal 公式具有类似的形式，可以使用类似于杨辉三角形的图示方法将上述递推公式用图形来表示.

除了上述递推公式外，可以证明第一类 Stirling 数还满足以下恒等式.

（1）\begin{bmatrix}n\\ n\end{bmatrix}=1.

（2）\begin{bmatrix}n\\ n-1\end{bmatrix}=\binom{n}{2}=\frac{n(n-1)}{2}.

（3）\sum\limits_{r=1}^{n}\begin{bmatrix}n\\ r\end{bmatrix}=n!.

其中前两个恒等式的证明比较简单，只需使用第一类 Stirling 数的定义.第三个恒等式可以采用组合分析的方法，具体的组合计数模型将在第 14 章的习题解答中给出.

解读：第一类 Stirling 数 \begin{bmatrix}n\\ r\end{bmatrix} 的绝对值等于"n 个元素排成 r 个轮换"的方案数；恒等式（3）说把所有 r 加起来等于 n!，正是"每个排列唯一分解为若干轮换"的计数翻版.

下面考虑第二类 Stirling 数，它是关于放球问题（组合计数模型 6）的组合计数.

定义 10.10 n 个不同的球恰好放到 r 个相同的盒子里的方法数称作第二类 Stirling 数，记作 \begin{Bmatrix}n\\ r\end{Bmatrix}.

例如，\begin{Bmatrix}4\\ 2\end{Bmatrix}=7，下面给出这 7 种放球方案.

a,b,c|d\quad a,c,d|b\quad a,b,d|c\quad b,c,d|a\quad a,b|c,d\quad a,c|b,d\quad a,d|b,c

可以证明第二类 Stirling 数满足下述递推方程

证明 将 n 个不同的球恰好放到 r 个相同的盒子.取球 a_1，把放球的方法如下进行分类：

若 a_1 单独放在一个盒子里，剩下的是对其他 n-1 个球的放置问题，有 \begin{Bmatrix}n-1\\ r-1\end{Bmatrix} 种方法.

若 a_1 与别的球放在同一盒子里，可以先把 n-1 个球恰好放到 r 个盒子里，有 \begin{Bmatrix}n-1\\ r\end{Bmatrix} 方法，然后把 a_1 插入到 r 个盒子中，有 r 种方法.因此，总共 r\begin{Bmatrix}n-1\\ r\end{Bmatrix} 种方法.根据加法法则得到

根据第二类 Stirling 数的定义，不难得到 \begin{Bmatrix}n\\ 0\end{Bmatrix}=0，\begin{Bmatrix}n\\ 1\end{Bmatrix}=1.

第二类 Stirling 数的递推公式也可以采用图形表示.图 10.9 给出了当 n=5 时所有第二类 Stirling 数的值.

第二类 Stirling 数满足以下恒等式.

（1）\begin{Bmatrix}n\\ 2\end{Bmatrix}=2^{n-1}-1.

（2）\begin{Bmatrix}n\\ n-1\end{Bmatrix}=\binom{n}{2}.

（3）\begin{Bmatrix}n\\ n\end{Bmatrix}=1.

（4）\sum\binom{n}{n_1,n_2,\cdots,n_m}=m!\begin{Bmatrix}n\\ m\end{Bmatrix}，其中 \sum 是对满足 n_1+n_2+\cdots+n_m=n 的正整数解求和.

（5）\sum_{k=1}^{m}\begin{bmatrix}m\\ k\end{bmatrix}\begin{Bmatrix}n\\ k\end{Bmatrix}k!=m^n.

（6）\begin{Bmatrix}n+1\\ r\end{Bmatrix}=\sum_{i=0}^{n}\binom{n}{i}\begin{Bmatrix}i\\ r-1\end{Bmatrix}.

证明 （1）将 n 个不同的球放到 2 个相同的盒子里.先选定一个球，比如是 a_1，把它放在一个盒子里.然后放剩下的 n-1 个球，每个球有 2 种选择，总计 2^{n-1} 种放法.但是，这些球全落入 a_1 所在盒子的选法不符合要求，所以要从中间减去 1 种选法.

（2）将 n 个不同的球恰好放到 n-1 个相同的盒子里，必有一个盒子含有 2 个球，其余每个盒子 1 个球.选择这两个球有 \binom{n}{2} 种方法.

（3）根据第二类 Stirling 数的定义可以直接得到.

（4）使用组合分析的方法证明.首先证明等式左边计数了 n 个不同的球恰好放到 m 个不同的盒子的方法.当所有的 n_i 为正整数，且 n_1+n_2+\cdots+n_m=n 时，\binom{n}{n_1,n_2,\cdots,n_m} 对应了 n 个不同的球恰好放到 m 个不同盒子里，并且使得第一个盒子含有 n_1 个球、第二个盒子含有 n_2 个球、\cdots、第 m 个盒子含有 n_m 个球的方法数.对所有满足上述条件的 n_1,n_2,\cdots,n_m，通过对 \binom{n}{n_1,n_2,\cdots,n_m} 求和就得到 n 个不同的球恰好放到 m 个不同的盒子的方法数.再看等式右边.先把 n 个不同的球恰好放到 m 个相同的盒子，有 \begin{Bmatrix}n\\ m\end{Bmatrix} 种方法；然后对盒子进行编号，编号的方式有 m! 种.因此，m!\begin{Bmatrix}n\\ m\end{Bmatrix} 也计数了 n 个不同的球恰好放到 m 个不同的盒子的方法.

（5）由于每个球有 m 种可能的选择，根据乘法法则，m^n 计数了 n 个不同的球放到 m 个不同的盒子并允许空盒的方法.将这些方法按照含有球的盒子的个数 k 进行分类，其中 k=1,2,\cdots,m.对于给定的 k，可以分步处理：先从 m 个不同的盒子选出 k 个盒子，选法有 \binom{m}{k} 种.然后将 n 个不同的球恰好放入这 k 个不同的盒子有 \begin{Bmatrix}n\\ k\end{Bmatrix}k! 种方法.因此根据乘法法则与加法法则，\sum\limits_{k=1}^{m}\binom{m}{k}\begin{Bmatrix}n\\ k\end{Bmatrix}k! 恰好计数了 n 个不同的球放到 m 个不同的盒子并允许空盒的方法.

（6）等式左边计数了 n+1 个不同的球恰好放入 r 个相同的盒子的方法.先选定一个球，比如是 a_1，把它放在一个盒子里.将其余 n 个球的放法根据剩下 r-1 个盒子含有的球数 i 进行分类，i=0,1,\cdots,r-1,r,\cdots,n.对于给定的 i，先从 n 个不同的球中选出 i 个球，有 \binom{n}{i} 种选法.然后将这 i 个球恰好放入 r-1 个相同的盒子，有 \begin{Bmatrix}i\\ r-1\end{Bmatrix} 种放法.这里要注意到，当 i<r-1 时，\begin{Bmatrix}i\\ r-1\end{Bmatrix} 的值等于 0.对 i 求和就得到 n+1 个不同的球恰好放入 r 个相同的盒子的方法数.

解读：\begin{Bmatrix}n\\ r\end{Bmatrix} 与 \begin{bmatrix}n\\ r\end{bmatrix} 的递推形状完全一样，只差系数：第二类的 r 来自"a_1 插进已有的 r 个盒子"，第一类的 n-1 来自"乘上因式 (x-n+1)".两者的方括号/花括号千万别写反.

第二类 Stirling 数来源于一个重要的组合计数问题——放球问题，这个问题可以按照球是否有区别、盒子是否有区别、是否允许空盒等约束条件划分成 8 种类型，通过一一对应的技巧，可以使用放球问题的计数结果来求解其他组合计数问题.设有 n 个球，m 个盒子，下面将与放球问题相关的计数结果列在表 10.3.

表 10.3

解读：这张表是"放球问题"的查询表，判断方法只有三个问题：球是否可区分、盒子是否可区分、是否允许空盒.前四行靠第二类 Stirling 数，中两行化为不定方程解的个数，后两行是整数拆分.

下面考虑一个关系与函数的计数问题.

例 10.31 设 A,B 为集合，其中 |A|=n，|B|=m，问：

（1）从 A 到 B 的关系有多少个？

（2）A 上关系有多少个？其中等价关系有多少个？

（3）从 A 到 B 的函数有多少个？其中单射函数有多少个？满射函数有多少个？双射函数有多少个？

解 （1）|A|=n，|B|=m，从 A 到 B 的关系是 A\times B 的子集，|A\times B|=mn.因此从 A 到 B 有 2^{mn} 个不同的二元关系.

（2）A 上的关系有 2^{n^2} 个.任何 A 上的等价关系都对应了 A 的划分.根据划分块的个数 k 将划分进行分类，其中 k=1,2,\cdots,n，具有 k 个划分块的划分相当于将 n 个不同的球恰好放入 k 个相同盒子的放球方案数，因此是第二类 Stirling 数 \begin{Bmatrix}n\\ k\end{Bmatrix}，对 k 求和就得到所有的划分个数，也就是等价关系的个数.因此 \sum\limits_{k=1}^{n}\begin{Bmatrix}n\\ k\end{Bmatrix} 是 A 上的等价关系个数.

（3）从 A 到 B 的函数有 m^n 个，而一个单射函数对应于从 m 个元素中选 n 个元素的一种排列，因此单射函数有 P(m,n)=m(m-1)\cdots(m-n+1) 个.下面考虑满射函数，将 m 个函数值考虑成 m 个不同的盒子，将 n 个自变量看作 n 个不同的球，将它们恰好放入 m 个不同的盒子，放球的方法数就是满射函数的个数，即 m!\begin{Bmatrix}n\\ m\end{Bmatrix}.双射函数仅当 m=n 的情况下成立，这时 P(n,n)=n!\begin{Bmatrix}n\\ n\end{Bmatrix}=n!，因此恰好有 n! 个双射函数.

解读：第（2）问的关键一步是"A 上的等价关系 ↔ A 的划分"这个双射：划分块是无标号的，所以用第二类 Stirling 数而不是排列数.第（3）问则相反，函数值是有标号的，所以要乘 m!.