Preface
下文简单介绍了两类斯特林数，也总结了它们的一些性质
由于第二类较第一类容易理解，更简单，因此先介绍第二类
第二类斯特林数
给你N个元素（有差别），M个集合（无差别），要你将这N个元素放入M个集合，要求没有空集。求方案数。
Text
符号表示为$或
考虑递推式
前个元素，若放入了
个集合，那么这个元素肯定是新开一个集合，所以等于
若已经放入了个集合，那么这个元素在前面所有元素中选一个放入，就是
总的说来，就是
其实上下两部分就是个二项式反演
根据上面第二类斯特林数的展开式，如果我们想快速求n相同的所有第二类斯特林数，发现上面的式子是将阶乘提出来是一个卷积的形式，NTT优化可以做到。
主要应用在组合数之类的问题中。
几个经典例子。
- N本书，M个抽屉（无差别），每个抽屉不能为空，求方案数。
易得 - N本书，M个抽屉（有差别），每个抽屉不能为空，求方案数。
易得 - N本书，M个抽屉（无差别），每个抽屉可以空，求方案数。
枚举多少个抽屉非空，易得
这也就是贝尔数 - N本书，M个抽屉（有差别），每个抽屉可以空，求方案数。
枚举非空抽屉数，乘上一个排列。
例题
给你M行N列的棋盘，让你放棋子，每行每列至少有1枚棋子，棋子有c种颜色，要求每种颜色至少1枚，求方案数（旋转，翻转算不同方案）。
题解见http://blog.csdn.net/hzj1054689699/article/details/54645826
第一类斯特林数
给你N个元素（有差别），M个圆环（无差别），要你将N个元素放入M个圆环中，求方案数
圆环有排列，但是不能循环同构
Text
第一类斯特林数有两种，带符号与无符号，分别用表示，后者也可记作
同样的我们考虑递推
容易有
即考虑新的这个元素是成一个圆环还是插在前面某一个元素的左边。
第一类斯特林数还有另一种定义方式
无符号第一类斯特林数是上升幂展开式的系数，带符号第一类斯特林数是下降幂展开式的系数
容易发现
联系这两个形式可以通过归纳得到，此处不再赘述。
根据上面两个式子，第一类斯特林数可以用分治FFT在n log^2时间求出，也可以采用倍增的方式n log 时间求出。
斯特林反演
等价于
如何推导呢？
考虑我们之前关于两类斯特林数的公式，它们连接了下降幂和乘方幂
(2)式代入(1)式
因为上式对所有的x均满足，因此有后面的求和有唯一解
类似的可以推出
有了这两个公式，考虑推斯特林反演的公式
若有
显然
交换主体
反过来同理
这样斯特林反演就得证了。