第一类第二类斯特林数学习笔记

本文主要是介绍第一类第二类斯特林数学习笔记，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

第一类斯特林数

$p$个不同人围着$k$个不同圆桌坐，要求每桌非空，方案数即为$S(p,k)$

递推

边界
$$S(p,p)=1(p>=0),S(p,0)=0(p>=1)$$
分类讨论一下…
新加入的人可以新开一张桌子，前面的方案即为$S(p-1,k-1)$
也可以和之前的人坐，先把前面的人安排好了的方案数是$S(p-1,k)$，我们让这个人任选一个人，坐在他的左边，方案数即为$(p-1)\ast S(p-1,k)$
综上，转移即为
$$S(p,k)=S(p-1,k-1)+(p-1)\ast S(p-1,k)$$
复杂度$O(n^2)$

性质

第一类斯特林数$S(n,m)$其实可以表示为$x$的$n$次上升幂的第$m$项系数，即有
$$x^{n\uparrow }=x(x+1)(x+2)\cdots (x+n-1)=\sum _{i=0}^{n}s(n,i)x^i$$
可以分治NTT或FFT求出，复杂度$O(nlo{g}^{2}n)$

某个式子

$$n!=\sum _{i=0}^{n}s(n,i)$$

证明考虑任意一个排列对应了唯一一个置换，一个置换可以看作一个轮换，于是轮换与置换，排列一一对应，右边相当于枚举所有轮换，由此得证

另一个重要式子

$$x^{\underline{n}}=\sum _{i=0}^{n}s(n,i)(-1{)}^{n-i}{x}^i$$

证明考虑归纳
$$\begin{gathered} x^{\underline{n+1}}=x^{\underline{n}}(x-n) \\ =x\ast x^{\underline{n}}-n\ast x^{\underline{n}} \\ =\sum _{i=0}^{n}s(n,i)(-1{)}^{n-i}{x}^{i+1}-n\sum _{i=0}^{n}s(n,i)(-1{)}^{n-i}{x}^i \\ =\sum _{i=1}^{n+1}s(n,i-1)(-1{)}^{n-i+1}{x}^i+n\sum _{i=1}^{n+1}s(n,i)(-1{)}^{n-i+1}{x}^i \\ =\sum _{i=1}^{n+1}(s(n,i-1)+n\ast s(n,i))(-1{)}^{n-i+1}{x}^i \\ =\sum _{i=1}^{n+1}s(n+1,i)(-1{)}^{n-i+1}{x}^i \end{gathered}$$
注意这个多项式的常数项一定为$0$所以可以不予考虑，得证

$n\log n$推出第一类斯特林数

由上可知第一类斯特林数可以用下降幂来搞，但是存在正负性不好考虑，所以用上升幂

设$f(x)=x^{\underline{n}},g(x)=(x+n{)}^{\underline{n}}$，显然$f(x)g(x)=x^{\underline{2n}}$，这个其实是我们上面分治$NTT$的过程，现在我们不考虑递归两侧，直接递归一侧来算出另一侧，于是
$$\begin{gathered} f(x)=\sum _{i=0}^n{a}_i{x}^i \\ 则g(x)=\sum _{i=0}^n{a}_i(x+n{)}^i \\ =\sum _{i=0}^n{a}_i\sum _{j=0}^i(\genfrac{}{}{0ex}{}{i}{j})x^j{n}^{i-j} \\ =\sum _{j=0}^n(\sum _{i=j}^n{a}_i\left(\genfrac{}{}{0ex}{}{i}{j}\right)n^{i-j})x^j \end{gathered}$$
中间是个卷积，直接卷就行了，然后再当前层再卷一次

注意我们强行把当前层看作了偶数，如果是奇数再把最后一项暴力乘上去就行了

复杂度就变为$n\log n$了

第二类斯特林数

$n$个不同球放入$m$个相同盒子的方案数即为$S(n,m)$

递推

仍然分类讨论
新加入的球可以新开一个盒子，即为$S(n-1,m-1)$
或者在之前任选一个盒子放入，即为$m\ast S(n-1,m)$
综上所述，有
$$S(n,m)=S(n-1,m-1)+m\ast S(n-1,m)$$
复杂度$O(n^2)$

容斥原理

我们可以枚举至少有多少个盒子是空的，剩下的盒子随便放
那么有
$$S(n,m)=\frac{1}{m!}\sum _{k=0}^m(-1{)}^k{C}_m^k(m-k{)}^n$$
再推一下会有
$$=\frac{1}{m!}\sum _{k=0}^m(-1{)}^k\frac{m!}{k!(m-k)!}(m-k{)}^n$$
$$=\sum _{k=0}^m\frac{(-1{)}^k}{k!}\ast \frac{(m-k{)}^n}{(m-k)!}$$
容易发现，这是一个卷积形式，组合数和次幂都可以预处理
于是可以通过FFT或者NTT求出$S(n,0),S(n,1)...$
复杂度 $O(nlogn)$

性质

$$n^k=\sum _{i=0}^{min(n,k)}S(k,i)\ast i!\ast C_n^i$$
等式左边即为$k$个不同小球放入$n$个不同盒子的方案数
我们可以通过枚举放入了多少个盒子，即为$S(k,i)\ast i!$，由于第二类斯特林数中盒子是相同的所以我们需要乘一个$i!$
再在$n$个盒子中选出$i$个可知等式合法

这篇关于第一类第二类斯特林数学习笔记的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---