第一类斯特林数
定义
第一类Stirling数\(s(n,m)\)，也可记为\(\begin{bmatrix}n\\m\end{bmatrix}\)。
第一类Stirling分为无符号第一类Stirling数\(s_u(n,m)\)和带符号第一类Stirling数\(s_s(n,m)\)。
他们分别表现为其升阶函数和降阶函数的各项系数，形式如下：
\[ x^{n\downarrow}=x\cdot (x-1)\cdot (x-2)\cdots (x-n+1)=\sum_{k=0}^ns_s(n,k)\cdot x^k\\ x^{n\uparrow}=x\cdot (x+1)\cdot (x+2)\cdots(x+n-1)=\sum_{k=0}^ns_u(n,k)\cdot x^k \]
无符号Stirling数更为常用，表示将\(n\)个不同元素构成\(m\)个圆排列的数目。
有无符号Stirling之间有关系式\(s_s(n,m)=(-1)^{n+m}\cdot s_u(n,m)\)。
递推式
无符号第一类Stirling数
设元素有编号\(1,2,...,n\)，则将\(n\)个元素构成\(m\)个圆有两种情况：
①把第\(n\)个元素单独作为一个圆，用前\(n-1\)个元素构成\(m-1\)个圆，方案数\(\begin{bmatrix}n-1\\m-1\end{bmatrix}\)。
②用前\(n-1\)个元素构成\(m\)个圆，把第\(n\)个元素插在前\((n-1)\)个元素任意一个之前，方案数\((n-1)\cdot \begin{bmatrix}n-1\\m\end{bmatrix}\)。
综上：
\[ \begin{bmatrix}n\\m\end{bmatrix}=\begin{bmatrix}n-1\\m-1\end{bmatrix}+(n-1)\cdot \begin{bmatrix}n-1\\m\end{bmatrix} \]
赋初值\(s(0,0)=1\)。
有符号第一类Stirling数
可以从其表示的降阶函数归纳证明：
\[ \sum_{k=0}^{n}s_s(n,k)\cdot x^k=x^{n\downarrow}=x^{(n-1)\downarrow}\cdot(x-(n-1))=\sum_{k=0}^{n-1}s_s(n-1,k)\cdot x^{k+1}-(n-1)\cdot\sum_{k=0}^{n-1}s_s(n-1,k)\cdot x^k \]
依次把\(x^m\)的左右两边的系数提取出来得：
\[ s_s(n,m)=s_s(n-1,m-1)-n\cdot s_s(n-1,m-1) \]
用分治+NTT求第一类Stirling数
以求无符号第一类Stirling数为例:
因为可以表示为升阶函数的各项系数，即：
\[ x^{n\uparrow}=x\cdot (x+1)\cdot (x+2)\cdots(x+n-1)=\sum_{k=0}^ns_u(n,k)\cdot x^k \]我们可以用分治的思想，每次处理一半的多项式来NTT，时间复杂度\(O(n\log^2n)\)。
代码实现
int rev[N];void NTT(int *a,int x,int K){ int n=(1< >1; int f[N],g[N]; memset(f,0,(r-l+1)<<3),memset(g,0,(r-l+1)<<3); Binary(f,l,mid),Binary(g,mid+1,r); int x=ceil(log2(r-l+2)); for(int i=0;i<(1< >1]>>1)|((i&1)< 例题
第二类斯特林数
定义
第二类Stirling数记为\(S(n,m)\)或者\(\begin{Bmatrix}n\\m\end{Bmatrix}\) 。
第二类Stirling数实际上是集合的一个拆分，表示将n个不同的元素拆分成m个集合的方案数。
常常用于解决组合数学中几类放球模型；
描述为：将n个不同的球放入m个无差别的盒子中，要求盒子非空，有几种方案？
由容斥原理可以得到其通项公式：
\[ \begin{Bmatrix}n\\m\end{Bmatrix}=\frac 1 {m!}\sum_{i=0}^m(-1)^i\binom mi(m-i)^n \]递推式
设元素有编号\(1,2,...,n\)，则将\(n\)个元素构成\(m\)个集合有两种情况：
①把第\(n\)个元素单独作为一个集合，用前\(n-1\)个元素构成\(m-1\)个集合，方案数\(\begin{Bmatrix}n-1\\m-1\end{Bmatrix}\)。
②用前\(n-1\)个元素构成\(m\)个集合，把第\(n\)个元素插入任意一个集合之中，方案数\(m\cdot \begin{Bmatrix}n-1\\m\end{Bmatrix}\)。
综上：
\[ \begin{Bmatrix}n\\m\end{Bmatrix}=\begin{Bmatrix}n-1\\m-1\end{Bmatrix}+m\cdot \begin{Bmatrix}n-1\\m\end{Bmatrix} \]赋初值：\(S(0,0)=1\)。
两类Stirling数之间的关系
\[ \sum_{i=0}^nS(n,i)s(i,m)=\sum_{i=0}^ns(n,i)S(i,m) \]
推论&总结
对原式二项式反演可得
\[ m^n=\sum_{i=0}^m\binom mi\begin{Bmatrix}n\\i\end{Bmatrix}i!=\sum_{i=0}^m\begin{Bmatrix}n\\i\end{Bmatrix}m^{i\downarrow} \]等价于
\[ m^n=\sum_{i=0}^n\binom mi\begin{Bmatrix}n\\i\end{Bmatrix}i!=\sum_{i=0}^n\begin{Bmatrix}n\\i\end{Bmatrix}m^{i\downarrow} \]
可以用于计算其他式子。
比如：
\[ \begin{split} &\sum_{i=0}^ni^k=\sum_{i=0}^k\begin{Bmatrix}k\\i\end{Bmatrix}i!\binom{n+1}{i+1}\\ &\sum_{i=1}^ni^k\binom ni=\sum_{i=0}^k\begin{Bmatrix}k\\i\end{Bmatrix}i!\binom ni2^{n-i} \end{split} \]例题
将通项公式再化一下：
\[ \begin{Bmatrix}n\\m\end{Bmatrix}=\sum_{i=0}^m\frac{(-1)^i}{i!}\cdot\frac{(m-i)^n}{(m-i)!} \]这是一个形如\(\sum_{i=0}^mf(i)*g(m-i)\)的卷积的形式，可以用FFT快速计算。
第一个多项式的第\(i\)项系数为\(\frac {(-1)^i}{i!}\)；第二个多项式的第\(i\)项系数为\(\frac {i^n}{i!}\)。
两式相乘，第\(i\)项的系数即为\(S(n,i)\)。
例题
其他题目
斯特林反演
\[ \displaystyle f(n)=\sum_{k=0}^n \begin{Bmatrix}n\\k \end{Bmatrix}g(k) \iff g(n)=\sum_{k=0}^n(-1)^{n-k}\begin {bmatrix} n\\k \end{bmatrix}f(k) \]
证明斯特林反演
首先，我们需要考虑如何建立上升阶乘幂与下降阶乘幂之间的关系。
结论：
\[ x^{n\downarrow}=(-1)^n(-x)^{n\uparrow}\\ x^{n\uparrow}=(-1)^n(-x)^{n\downarrow} \]证明：
\[ \begin{split} (-1)^n(-x)^{n\uparrow}&=(-1)^n(-x)(-x+1)\cdots(-x+n-1)\\ &=(-1)^n(-x)(-(x-1))\cdots(-(x-n+1))\\ &=x(x-1)\cdots(x-n+1)\\ &=x^{n\downarrow} \end{split} \]同理可证\(x^{n\uparrow}=(-1)^n(-x)^{n\downarrow}\)。
接下来，我们需要证一个叫反转公式的东西：
还是先给出结论：
\[ \sum_{i=m}^n(-1)^{n-i}\begin{bmatrix}n\\i\end{bmatrix}\begin{Bmatrix}i\\m\end{Bmatrix}=[m=n]\\ \sum_{i=m}^n(-1)^{n-i}\begin{Bmatrix}n\\i\end{Bmatrix}\begin{bmatrix}i\\m\end{bmatrix}=[m=n] \]
证明：
\[ \begin{split} n^m&=\sum_{i=0}^m\begin{Bmatrix}m\\i\end{Bmatrix}n^{i\downarrow}\\ &=\sum_{i=0}^m\begin{Bmatrix}m\\i\end{Bmatrix}(-1)^i(-n)^{i\uparrow} \end{split} \]
将\(x^{n\uparrow}=\sum\limits_{k=0}^ns_u(n,k)\cdot x^k\)带入：
\[ \begin{split} n^m&=\sum_{i=0}^m\begin{Bmatrix}m\\i\end{Bmatrix}(-1)^i\sum_{j=0}^i\begin{bmatrix}i\\j\end{bmatrix}(-n)^j\\ &=\sum_{j=0}^mn^j\sum_{i=j}^m\begin{Bmatrix}m\\i\end{Bmatrix}\begin{bmatrix}i\\j\end{bmatrix}(-1)^{i-j} \end{split} \]
即：
\[ \sum_{i=j}^m\begin{Bmatrix}m\\i\end{Bmatrix}\begin{bmatrix}i\\j\end{bmatrix}(-1)^{i-j}=[j=m] \]这个与上面的式2等价，于是我们就证出了其中一个反转公式。
\[ \begin{split} m^{n\downarrow}&=\sum_{i=0}^n(-1)^{n-i}\begin{bmatrix}n\\i\end{bmatrix}m^i\\ &=\sum_{i=0}^n(-1)^{n-i}\begin{bmatrix}n\\i\end{bmatrix}\sum_{j=0}^i\begin{Bmatrix}i\\j\end{Bmatrix}m^{j\downarrow}\\ &=\sum_{j=0}^nm^{j\downarrow}\sum_{i=j}^n(-1)^{n-i}\begin{bmatrix}n\\i\end{bmatrix}\begin{Bmatrix}i\\j\end{Bmatrix} \end{split} \]即：
\[ \sum_{i=j}^n(-1)^{n-i}\begin{bmatrix}n\\i\end{bmatrix}\begin{Bmatrix}i\\j\end{Bmatrix}=[j=n] \]由此证出了式1。
然后，我们就可以证明斯特林反演了：
若满足\(g(n)=\sum\limits_{j=0}^n(-1)^{n-j}\begin{bmatrix}n\\j\end{bmatrix}f(j)\)，则
\[ \begin{split} f(n)&=\sum_{j=0}^n[j=n]f(j)\\ &=\sum_{j=0}^n\sum_{k=j}^n\begin{Bmatrix}n\\k\end{Bmatrix}\begin{bmatrix}k\\j\end{bmatrix}(-1)^{k-j}f(j)\\ &=\sum_{k=0}^n\begin{Bmatrix}n\\k\end{Bmatrix}\sum_{j=0}^k(-1)^{k-j}\begin{bmatrix}k\\j\end{bmatrix}f(j)\\ &=\sum_{k=0}^n\begin{Bmatrix}n\\k\end{Bmatrix}g(k) \end{split} \]