卡特兰数&斯特林数&贝尔数 学习笔记

卡特兰数

卡特兰数由发现者的名字 Catalan 命名，与植物卡特兰 Cattleya 没有关系。

卡特兰数是组合数学中解决计数问题常用的一个数列，其第 $n$ 项记为 $H_n$：

• 初值 $H_{0}=1$
• 定义 $H_{n}=\sum_{i=0}^{n-1} H_{i}H_{n-1-i}$
• 递推式 $H_{n}=\frac{4n-2}{n+1}H_{n-1}$
• 通项公式 $H_{n}=C_{2n}^{n}-C_{2n}^{n-1}=\frac{1}{n+1}C_{2n}^{n}$
• 生成函数 $H(x)=\frac{1-\sqrt{1-4x}}{2x}$

括号序列计数

问题：长度为 $2n$ 的合法括号序列有多少种？

分析：合法括号序列包含 $n$ 个左括号和 $n$ 个右括号，且每个前缀中右括号的个数不超过左括号。首先，满足第一个条件的序列有 $C_{2n}^{n}$ 种。考虑其中的非法序列，将所有非法序列的第一个非法前缀中所有括号取反，将与包含 $n-1$ 个左括号和 $n+1$ 个右括号的所有括号序列形成一一对应的双射关系。因此非法序列有 $C_{2n}^{n-1}$ 种。答案为 $C_{2n}^{n}-C_{2n}^{n-1}=H_{n}$。

出栈序列计数

问题：$1,2,\cdots,n$ 按顺序进栈，可能的出栈序列有多少种？

分析：将出栈序列扩展成进出栈序列，进栈相当于左括号，出栈相当于右括号，问题与括号序列计数完全相同。

三角路径计数

问题：从 $(0,0)$ 走向 $(n,n)$，每次只能向上或向右走 $1$ 且不能向上穿过直线 $y=x$，这样的路线有多少种？

分析：将向右视为左括号，向上视为右括号，问题与括号序列计数完全相同。

二叉树计数

问题：包含 $n$ 个点的二叉树有多少种形态？

分析：从根开始考虑，枚举左子树的大小 $i$，有右子树大小 $n-1-i$，得到与卡特兰数定义相同的递推关系 $H_{n}=\sum_{i=0}^{n-1} H_{i}H_{n-1-i}$，因此答案为卡特兰数 $H_{n}$。

蛋糕切法计数

问题：圆上有 $2n$ 个无编号的点，将这些点成对连接使得没有线段相交的方案数有多少种？

分析：从第一条线开始连，每一种连法会使得一边还剩 $i$ 对点，另一边还剩 $n-1-i$ 对点，得到与卡特兰数定义相同的递推关系 $H_{n}=\sum_{i=0}^{n-1} H_{i}H_{n-1-i}$，因此答案为卡特兰数 $H_{n}$。

第二类斯特林数

第二类斯特林数在原著中先于第一类斯特林数被介绍，同时也比第一类斯特林数更加常用。

第二类斯特林数是将 $n$ 个有编号的元素划分为 $m$ 个无编号的非空集合的方案数，记为 $S(n,m)$：

• 初值 $S(n,0)=[n=0]$
• 递推式 $S(n,m)=S(n-1,m-1)+mS(n-1,m)$
• 通项公式 $S(n,m)=\frac{1}{m!}\sum_{i=0}^m(-1)^{m-i}C_m^ii^n=\sum_{i=0}^m(-1)^{m-i}\frac{i^n}{i!(m-i)!}$

考虑插入一个新元素，此时可以选择加入现有集合中的任意一个，也可以选择作为一个新的集合，由此可得递推式；而通项公式可以利用容斥原理/二项式反演推导。

第二类斯特林数的计算实现：

• 需要预处理 $n\times m$ 个 $S(i,j)$ 时，可以根据递推式 $O(nm)$ 计算
• 需要预处理 $m$ 个 $S(n,i)$ 时，可以通过计算多项式 $\sum_{i=0}^m \frac{i^n}{i!}x_i$ 和 $\sum_{i=0}^{m} \frac{(-1)^i}{i!}x_i$ 的卷积得到，时间复杂度 $O(m\log m)$
• 需要预处理 $n$ 个 $S(i,m)$ 时，分析问题：将 $i$ 个有编号元素划分为 $1$ 个非空集合的方案数用指数型生成函数表达为 $F(x)=\sum_{i=1}^n\frac{x^i}{i!}=e^x-1$，此时 $F^m(x)$ 即为将 $i$ 个有编号元素划分为 $m$ 个有编号非空集合的方案数，再除以 $m!$ 即转化为集合无编号的情况。因此 $S(i,m)$ 的指数型生成函数为 $\frac{\left[\frac{x^i}{i!}\right]F^m(x)}{m!}$ ，计算多项式的幂即可得到答案，时间复杂度 $O(n\log n)$

元素无编号时的组合问题用普通生成函数卷积，元素有编号时的组合问题用指数型生成函数卷积。

贝尔数

贝尔数是 $n$ 个有编号元素划分为若干无编号非空子集的方案数，记为 $B_i$：

• 初值 $B_0=1$
• 递推式 $B_n=\sum_{i=0}^{n-1}C_{n-1}^{i}B_i$

考虑插入一个新元素，此时可以选择若干个元素和新元素组成一个集合，剩下的元素组成剩下的集合，由此可得递推式。

根据定义容易看出，贝尔数实际上就是第二类斯特林数的前缀和 $B_i=\sum_{i=1}^n S(n,i)$。

贝尔数的计算实现：由前面第二类斯特林数算法的分析，$i$ 个有编号元素划分为任意多个无编号集合的方案为 $\sum_{i\ge 0}\frac{(e^x-1)^i}{i!}=\exp(e^x-1)$，即贝尔数的指数型生成函数为 $\exp(e^x-1)$。因此可以先预处理出多项式 $\sum_{i=1}^n \frac{1}{i!}x^i$，再求多项式 exp 得到贝尔数的前 $n$ 项，时间复杂度 $O(n\log n)$。

第一类斯特林数

第一类斯特林数是由 $n$ 个有编号的元素构成 $m$ 个无编号的圆排列（轮换）的方案数，记为 $s(n,m)$：

• 初值 $s(n,0)=[n=0]$
• 递推式 $s(n,m)=s(n-1,m-1)+(n-1)s(n-1,m)$

考虑插入一个新元素，此时可以将新元素插入任意一个数的后方，也可以作为一个新的圆排列，由此可得递推式。

第一类斯特林数的计算实现：

• 需要预处理 $n\times m$ 个 $s(i,j)$ 时，可以根据递推式 $O(nm)$ 计算
• 需要预处理 $n$ 个 $s(n,i)$ 时，根据递推式有 $s(n,i)$ 的生成函数 $F_n(x)=\frac{(x+n-1)!}{(x-1)!}=x^{\overline{n}}$，其中 $x^{\overline{n}}=x^{\overline{\lfloor\frac{n}{2}}\rfloor}(x+\lfloor\frac{n}{2}\rfloor)^{\overline{\lfloor\frac{n}{2}}\rfloor}(x+2\lfloor\frac{n}{2}\rfloor)^{\overline{n-2\lfloor\frac{n}{2}}\rfloor}$ 可以倍增计算。因为由 $x^{\overline{k}}$ 计算 $f_k(x)=(x+k)^{\overline{k}}$ 时只需要一次长度为 $k$ 的多项式卷积（推导略），总时间复杂度 $O(n\log n)$
• 需要预处理 $n$ 个 $s(i,m)$ 时，与第二类斯特林数同理分析得 $s(i,m)$ 的指数型生成函数为 $\frac{\left[\frac{x^i}{i!}\right]F^m(x)}{m!}$，其中 $F(x)=\sum_{i=1}^n \frac{x^i}{i}$。求多项式的幂 $O(n\log n)$ 即得答案

---