Stirling数小记
Stirling数小记
定义/组合意义
第一类斯特林数：\(\begin{bmatrix}n\\ m\end{bmatrix}\) 表示 \(n\) 个不同元素分为 \(m\) 个圆排列的方案数。
有标号的第一类斯特林数 \(s(n,m)=(-1)^{n-m}\begin{bmatrix}n\\ m\end{bmatrix}\)。
第二类斯特林数：\(\begin{Bmatrix}n\\ m\end{Bmatrix}\) 表示 \(n\) 个不同元素分为 \(m\) 个集合的方案数。
注意圆排列和集合都是相互之间无序的。
递推方法
第一类斯特林数
\(\begin{bmatrix}n\\ m\end{bmatrix}=\begin{bmatrix}n-1\\ m-1\end{bmatrix}+(n-1)\begin{bmatrix}n-1\\ m\end{bmatrix}\)
即新建一个圆排列，或者插入前面 \(n-1\) 个元素中任意一个的后面。
显然的，有标号的第一类斯特林数递推式就是：
\(\begin{bmatrix}n\\ m\end{bmatrix}=\begin{bmatrix}n-1\\ m-1\end{bmatrix}-(n-1)\begin{bmatrix}n-1\\ m\end{bmatrix}\)
第二类斯特林数：
\(\begin{Bmatrix}n\\ m\end{Bmatrix}=\begin{Bmatrix}n-1\\ m-1\end{Bmatrix}+m\begin{Bmatrix}n-1\\ m\end{Bmatrix}\)
即新建一个集合，或者加入前面的 \(m\) 个集合。
第二类斯特林数的通项公式
\(\begin{aligned} \begin{Bmatrix} n \\ m \end{Bmatrix}=\frac{1}{m!}\sum_{i=0}^{\infty} (-1)^{m-i}\binom{m}{i} i^n \end{aligned}\)
其组合意义是枚举生成了多少个有序的集合，然后容斥，最后除去集合的顺序。
生成函数表示与行/列求解
固定 \(n\)，以 \(m\) 为形式幂指数，则第一类斯特林数的普通生成函数：
\(\displaystyle\text{OGF}=\prod_{i=0}^{n-1}(x+i)=x^{\overline{n}}\)
（其意义就是上面的递推公式）
倍增 + 卷积二项展开求出 \(F(x+i)\) 即可做到 \(O(n\log n)\) 求出一行。
固定 \(m\)，以 \(n\) 为形式幂指数，则第一类斯特林数的指数型生成函数。
\(\begin{aligned}\text{EGF}= & \frac{1}{m!}\cdot (\sum_{i=1}^{\infty}\frac{(i-1)!}{i!}x^i)^m\\= & \frac{1}{m!}\cdot (\sum_{i=1}^{\infty}\frac{x^i}{i})^m\end{aligned}\)
设 \(F(x)=\sum_{i=1}^{\infty}\frac{x^i}{i}\)。
\(\begin{aligned} \because F'(x)=&\sum_{i=1}^{\infty}x^{i-1}=\frac{1}{1-x}\end{aligned}\)
\(\begin{aligned} \therefore F(x)=\int \frac{1}{1-x}=-\ln(1-x)\end{aligned}\)
\(\begin{aligned}\therefore \text{EGF} = & \frac{1}{m!}\cdot (-\ln(1-x))^m\\= & \frac{1}{m!}\cdot (-1)^m\cdot \ln^m(1-x)\end{aligned}\)
（就是百度百科上的那个，它什么都没讲清楚）
多项式快速幂即可做到 \(O(n\log n-n\log ^2n)\) 求一列。
而在上式的推导过程中额外加入 \((-1)^m\) 的常数，并且把 \(x^i\) 换成 \((-x)^i\) 可以得到有标号第一类斯特林数的指数型生成函数：
\(\begin{aligned} \text{EGF} = & \frac{1}{m!}\cdot (\sum_{i=1}^{\infty}\frac{(-x)^i}{i})^m\\=& \frac{1}{m!}\cdot \ln^m(1+x)\end{aligned}\)
第二类斯特林数的一行可以直接由通项公式做卷积得到。
固定 \(m\)，以 \(n\) 为形式幂指数，则第二类斯特林数的指数型生成函数表示为：
\(\begin{aligned} \text{EGF} &=\frac{1}{m!}({\sum_{i=1}^{\infty} \frac{x^i}{i!}})^m\\ &=\frac{1}{m!}(e^x-1)^m \\ &=\frac{1}{m!}\sum_{i=0}^m (-1)^{m-1} \binom{m}{i}e^{ix}\end{aligned}\)
实际上由这个二项展开的形式也可以发现，它就是上面通项公式的生成函数推导。
可以求一列，复杂度为 \(O(n\log n-n\log ^2n)\) 常数很大。
\[ \ \]
虽然没什么意义，但是还是写一下二元形式：
第一类斯特林数：
\(\begin{aligned} \text{EGF}=e^{-\ln (1-x)y}\end{aligned}\)
第二类斯特林数：
\(\begin{aligned}\text{EGF}=e^{\begin{aligned}(e^x-1)y\end{aligned}}\end{aligned}\)
注意元 \(x\) 为指数型，\(y\) 是普通型。
\[ \ \]
斯特林数与幂指数/上升幂/下降幂
第一类斯特林数：
上面已经说过 \(\begin{aligned}x^{\overline{n}}=\sum_{i=0}^{n}\begin{bmatrix}n\\i\end{bmatrix}x^i\end{aligned}\)。
同理，用有标号的第一类斯特林数将 \(x^{\underline{n}}\) 展开的式子是：
\(\begin{aligned}x^{\underline{n}}=\sum_{i=0}^{n}(-1)^{n- i}\begin{bmatrix}n\\i\end{bmatrix}x^i\end{aligned}\)
第二类斯特林数：
类似通项公式的求解，组合意义将幂指数展开，视 \(x^n\) 为将 \(n\) 个元素随意放在 \(x\) 个位置，则枚举 \(x\) 个位置中哪些被选择。
\(\displaystyle x^n=\sum_{i=0}^n \binom{x}{i}i!\begin{Bmatrix}n\\i\end{Bmatrix}\)
把 \(\binom{x}{i}i!\) 写成下降幂的形式，得到优美的式子
\(\displaystyle x^n=\sum_{i=0}^n \begin{Bmatrix}n\\i\end{Bmatrix}x^{\underline{i}}\)
而实际上由上式二项反演也可以得到通项公式
\(\displaystyle \begin{Bmatrix} n \\ m \end{Bmatrix}=\frac{1}{m!}\sum_{i=0}^{\infty} (-1)^{m-i}\binom{m}{i} i^n\)
关于下降幂多项式的快速转化，可以再借鉴这个
斯特林变换/斯特林反演
对于斯特林变换 \(\displaystyle a_n=\sum_{i=0}^n\begin{Bmatrix}n\\i\end{Bmatrix}b_i\)
设 \(A(x),B(x)\) 为数列 \(a,b\) 的指数型生成函数，带入前文推导的式子，则得到上式的生成函数表达就是
\(A(x)=B(e^x-1)\)。
显然得到 \(B(x)=A(\ln(x+1))\)，而 \(\ln(x+1)\) 显然转化为有标号的第一类斯特林数。
因此得到斯特林反演的表达形式是：
\(\begin{aligned}b_n=\sum_{i=0}^{n}(-1)^{n-i}\begin{bmatrix}n\\i\end{bmatrix}a_i\end{aligned}\)
(不大可能搞类似多项式复合的方法处理这个反演吧，最多可能也就是求一个位置)