斯特林数
Meteor_
·
·
个人记录
斯特林数 (Stirling Number)
第二类斯特林数
虽然被称作 「第二类」， 但是第二类斯特林数却在斯特林的相关著作和具体数学中被首先描述，同时也比第一类斯特林数常用得多，所以先介绍第二类斯特林数。
第二类斯特林数，即斯特林子集数，一般记作 \displaystyle {n \brace k}，或记作 S(n, k)。
组合意义：
将 n 个互不相同的元素，划分成 k 个互不区分的非空子集的方案数。
较通俗的来说，就是在两两不同的 n 个数中，选出任意几个数组成非空集合，在这些非空集合中再选出 k 个集合组成新集合 ( 形如\{\{a, b\}, \{c, d\}\})。
递推式：
{n \brace k} &= {n - 1 \brace k - 1} + k {n - 1 \brace k}
\end{aligned}
其边界是\displaystyle {n \brace k} = [n = 0]。
用组合意义来证明：
当我们插入一个新元素时，有两种方式可以选择：
-
将新元素单独放入一个子集;
-
将新元素放入一个现有的非空子集
对于第一种方式，有 \displaystyle {n - 1 \brace k - 1} 种方案（新元素单独放一个集合，对其它集合无影响，方案数不变）
对于第二种方式，有 \displaystyle k {n \brace k - 1} 种方案数（集合数量仍为 k，从 k 个集合中任选一个有 k 种可能，根据乘法原理，用 k 乘上原先方案数即可）
再根据加法原理，讲两式相加即可得到递推式：
{n \brace k} = {n - 1 \brace k - 1} + k {n - 1 \brace k}
\end{aligned}
通项公式及其他方面还待更新 \dots