这里不讨论狭义计数和过于高深的多项式。
斯特林数
两类斯特林数在组合计数中具有重要意义。
第一类斯特林数
定义：
表示将个不同的数划分到个圆排列的方案数。
递推式：
就是枚举最后一个数是单独一组还是填进其他组。
性质：
证明：就是然后除以就是圆排列。
证明：一个排列对应唯一一个圆排列的划分，具体来说，对于一个排列向连边，必定会形成几个环。
证明：数学归纳，当的时候显然成立。
这里解释下上面，时的左边和时的右边都是，只是为了配上一项好看一点。
这样当的时候也是成立的。
于是一个的下降幂就被我们表示成了多项式形式了，系数就是一行斯特林数。
求第一类斯特林数
倍增法。先咕着。
第二类斯特林数
定义：
个数分成个集合的方案数，集合内于集合间无序。
递推式：
同样是考虑每个新加的数是单独占一个还是加进其它的。
应用：
第二类斯特林数主要应用于不同的球扔进各种桶里的问题，这里桶中的元素无序。
桶相同，不为空:
此时就是的定义：
桶相同，可为空：
枚举扔进几个桶里:
桶不同，不为空:
我们把每个桶编号，相当于就是要乘上一个的排列。
桶不同，可为空:
就是枚举扔几个桶加上排列数。
这里换一种方式考虑，相当于每个球可以随意扔进任何一个桶，只要某一步不一样就是不同的方案，那么就有:
求第二类斯特林数
证明的话就是数学归纳，把拆成求解。
可以发现它可以拆成两个多项式的卷积：
于是可以运用在时间内求解一行斯特林数。