补充数学 - 斯特林数

斯特林数感觉已经偏向于动态规划求解了，是一个很漂亮的组合数学，本来这一部分应该关于生成函数的介绍，但是因为没时间了，所以就鸽了。

在这个博文里，不仅介绍斯特林数，还介绍了对组合数学的一种普遍处理。所以还是有很好的参考意义的。

一、第二类斯特林数

第二类斯特林数记作 $S(n, m)$​，意思是把含有 n 个元素的集合秩为 m 的划分的个数，如果更加形象一点，就是把 n 个球丢入 m 个不加区分的盒子里，并且每个盒子不能为空的方法数。

这个是可以用容斥原理求出通项的，容斥原理是为了计算一个并集中元素的多少，每个组成并集的集合有一条性质来描述，不同的性质之间可能会重合（也就是集合的交不为空集），但是容斥原理可以在重合的条件下很好的计算出元素的个数（也就是这些元素可以满足其中的至少一条性质）。当我们应用容斥原理的时候，有两种用法：一种是求并集性质，也就是所有性质都要满足，这个其实比较反人类，因为一般性质越复杂，计数越简单，所以通常不予考虑（但是这是公式的描述）。另一种是求交集的性质，那么就是在等式两端移项了。

对于这道题来说，我们用的是广义容斥原理（我其实也不知道是不是），我们写个公式

也就是说，我们思考的问题由 0 个盒子没有被放满，转换为求解至少一个盒子没被放满，至少两个盒子没被放满，至少三个盒子没被放满……

我们可以这样思考，这个数，就是 n 个球，扔进 m 个有区分的盒子里的数量（全集数量），减去 “n 个球，扔进 m-1 个有区分的盒子里（至少 1 个盒子中没有球）” 的数量，加上 “n 个球，扔进 m-2 个有区分的盒子里（至少 2 个盒子没有球）” 的数量，写成通项，就是

$$(-1)^kC^k_m(m-k)^n$$

然后对他们进行累加，得到

$$\sum^{m}_{k = 0}(-1)^kC^k_m(m-k)^n$$

但是因为这样是有标志的盒子，所以要除以组合数，最后得到通项

$$S(n,m) = \frac{1}{m!}\sum^{m}_{k = 0}(-1)^kC^k_m(m-k)^n$$

---

二、递推与 Pascal 三角形

除了通项，我们还可以求递推式，这个很好思考，对于 $S(n+1,m)$ 而言，新加入的球，要么放进原来没有球的盒子（就是新开一个盒子），那么有 $S(n,m-1)$ 种方法，要么就是放到原来已经有球的盒子中，那么共有 m 个盒子供其挑选，就是 $m*S(n,m)$ 种方法，所以有状态转移方程

$$S(n+1,m)=S(n,m-1)+m\times S(n,m)$$

有了状态转移方程，还需要确定一下边界条件，有 $S(n,0) = n^0,S(n,n) = 1$（我不知道当 n 是 0 的时候为啥这样），然后就可以递推了。

对于 Pascal 三角形，也就是杨辉三角，我们熟悉组合数的三角形，这是因为组合数有递推性质

$$C^{m}_{n+1} = C_n^{m-1} + C_n^{m}$$

其实 Pascal 三角形就是适用于所有在 (n + 1, m)（底）,(n, m - 1)（左肩）, (n, m)（右肩）间建立关系的递推式。

故其三角形为

---

三、贝尔数

贝尔数是元素为 n 的集合的能形成划分的总数目，不难想，贝尔数就是对第二类斯特林数的求和，有

$$B(n) = \sum^n_{k = 0}S(n, k)$$

贝尔数也是有自己的递推公式的，考虑 $B(n+1)$ 第 n + 1 个元素如果自己单独形成一个划分，那么就有 $B(n)$ 种，如果第 n + 1 个元素去加入之前含有 1 个元素的类，那么就有 $C_n^{1}B(n-1)$ 种分法，那么如果加入之前含有 2 个元素的类，那么就有 $C_n^2B(n-2)$ 种方法，故有递推式

$$B(n+1) = \sum^n_{k = 0}B(k)$$