斯特林数

第一类斯特林数

第一类斯特林数为有$k$个轮换的$n$元置换的方案数，表示为$\begin{bmatrix}n\\m\end{bmatrix}$或$c(n,m)$。
递推公式

$$\begin{bmatrix}n\\k\end{bmatrix}=(n-1)\times\begin{bmatrix}n-1\\k\end{bmatrix}+\begin{bmatrix}n-1\\k-1\end{bmatrix}$$

重要公式

$$x^{\overline{n}}=\sum\limits_{k=0}^n\begin{bmatrix}n\\k\end{bmatrix}x^k$$

有符号第一类斯特林数：$S_1(n,k)=(-1)^{n+k}\begin{bmatrix}n\\k\end{bmatrix}$
满足

$$x^{\underline{n}}=\sum\limits_{k=0}^nS_1(n,k)x^k$$

关于$n$的指数生成函数

$$\sum_{n\ge0}S_1(n,k)\dfrac{x^n}{n!}=\dfrac{1}{k!}(\ln(1+x))^k\\ \sum_{n\ge0}\begin{bmatrix}n\\k\end{bmatrix}\dfrac{x^n}{n!}=\dfrac{1}{k!}(-\ln(1-x))^k$$

快速计算一行可以利用重要公式进行计算，显然我们只需要求$x^{\overline{n}}$，观察$\prod\limits_{i=L}^{R}(x+i)$，其中$R-L+1$为偶数，显然可以将其分成两个长度相同的部分，设左半部分为$f(x)=\sum_{n\ge0}a_nx^n$则右半部分为$f(x+d),d=\dfrac{R-L+1}{2}$，则有

$$f(x+d)=\sum_{n\ge0}a_n(x+d)^n=\sum_{i\ge0}\sum_{n\ge i}a_n\begin{pmatrix}n\\i\end{pmatrix}d^{n-i}x^i=\sum_{i\ge0}\dfrac{1}{i!}\sum_{n\ge i}n!a_n\dfrac{d^{n-i}}{(n-i)!}x^i$$

设$A_n=n!a_nx^n,B_n=\dfrac{d^{n}}{n!}x^{-n}$，则有

$$\sum_{n\ge i}a_n\begin{pmatrix}n\\i\end{pmatrix}d^{n-i}x^i=\sum_{n\ge i}A_n\times B_{n-i}$$

很明显的卷积形式，直接FFT/NTT/MTT求解即可。

快速计算一列直接用指数生成函数解决。

第二类斯特林数

第二类斯特林数为将$n$个有标号的球分配到$k$个无标号的盒子的方案数，记为$S_2(n,k)$或$\begin{Bmatrix}n\\m\end{Bmatrix}$。
递推公式

$$\begin{Bmatrix}n\\k\end{Bmatrix}=\begin{Bmatrix}n-1\\k-1\end{Bmatrix}+k\times\begin{Bmatrix}n-1\\k\end{Bmatrix}$$

通项公式（容斥）

$$\begin{Bmatrix}n\\k\end{Bmatrix}=\dfrac{1}{k!}\sum\limits_{i=0}^k(-1)^i\begin{pmatrix}k\\i\end{pmatrix}(k-i)^n$$

重要公式

$$x^n=\sum\limits_{k=0}^n\begin{Bmatrix}n\\k\end{Bmatrix}x^{\underline{k}}$$

关于$n$的指数生成函数

$$\sum_{n\ge0}\begin{Bmatrix}n\\k\end{Bmatrix}\dfrac{x^n}{n!}=\dfrac{1}{k!}(\exp(x)-1)^k$$

快速计算一行可以利用通项公式计算，式子化为

$$\begin{Bmatrix}n\\k\end{Bmatrix}=\sum\limits_{i=0}^k\dfrac{(-1)^i}{i!}\dfrac{(k-i)^n }{(k-i)!}=\sum\limits_{i=0}^kA_iB_{k-i}$$

明显的卷积形式，用FFT/NTT/MTT求解。

快速计算一列可以利用生成函数计算，直接求多项式快速幂即可。

斯特林反演

两类斯特林数之间的联系：

$$x^n=\sum\limits_{k=0}^nS_2(n,k)x^{\underline{k}}即\begin{pmatrix}x^0\\x^1\\x^2\\...\end{pmatrix}=\begin{pmatrix}S_2(0,0)\\S_2(1,0)&S_2(1,1)\\S_2(2,0)&S_2(2,1)&S_2(2,2)\\...&...&...&...\end{pmatrix}\begin{pmatrix}x^{\underline 0}\\x^{\underline 1}\\x^{\underline 2}\\...\end{pmatrix}\\ x^{\underline{n}}=\sum\limits_{k=0}^nS_1(n,k)x^k即\begin{pmatrix}x^{\underline 0}\\x^{\underline 1}\\x^{\underline 2}\\...\end{pmatrix}=\begin{pmatrix}S_1(0,0)\\S_1(1,0)&S_1(1,1)\\S_1(2,0)&S_1(2,1)&S_1(2,2)\\...&...&...&...\end{pmatrix}\begin{pmatrix}x^0\\x^1\\x^2\\...\end{pmatrix}\\ \sum_{k\ge0}S_2(n,k)S_1(k,m)=[n=m]即S_1\times S_2=S_2\times S_1=I$$

斯特林反演：
如果数列$f,g$满足$f_n=\sum\limits_{i=0}^nS_2(n,i)g_i$，则$g_n=\sum\limits_{i=0}^nS_1(n,i)f_i$，反之也成立。

整数分拆

将$n$个无标号的球分配到$k$个无标号的盒子中的方案数，记为$p(n,k)$。
递推公式

$$p(n,k)=p(n-1,k-1)+p(n-k,k)$$

关于$n$的常生成函数

$$\sum_{n\ge 0}p(n,k)x^n=\prod\limits_{i=1}^k\dfrac{1}{1-x^i}-\prod\limits_{i=1}^{k-1}\dfrac{1}{1-x^i}=x^k\prod\limits_{i=1}^k\dfrac{1}{1-x^i}$$

根据常生成函数，可以快速计算$k$相同的$p(n,k)$，对上面的式子取$\ln$，得到

$$\ln\prod\limits_{i=1}^k\dfrac{1}{1-x^i}=\sum\limits_{i=1}^k-\ln(1-x^i)=\sum\limits_{i=1}^k\sum\limits_{j\ge0}\dfrac{x^{i\cdot j}}{j}$$

将上式取$\exp$再乘上$x^k$就得到了他的形式幂级数。

将$n$个无标号的球分配到一些无标号盒子的方案数记为$p(n)$。
显然有

$$p(n)=\sum\limits_{k=1}^{n}p(n,k)$$

递推公式

$$p(n)=\sum_{k\ge1}(-1)^{k-1}(p(n-\dfrac{3k^2-k}{2})+p(n-\dfrac{3k^2+k}{2}))$$

常生成函数

$$\sum_{n\ge0}p(n)x^n=\prod_{i\ge1}\dfrac{1}{1-x^i}$$

同样可以通过先取$\ln$再用$\exp$还原的方法$O(n\log n)$计算，利用递推式直接计算是$O(n\sqrt{n})$的。