斯特林数学习笔记
正文开始前，感谢以下几篇博客：
https://www.cnblogs.com/y2823774827y/p/10700231.html（不认识的）
https://www.cnblogs.com/p-b-p-b/p/10943453.html（PB的）
https://www.cnblogs.com/AThousandMoons/p/10949178.html（CDW的）
第一类斯特林数的定义：$egin{bmatrix}n\mend{bmatrix}$ 表示把 $n$ 个不同的物品组成恰好 $m$ 个没有区别的圆排列的方案数。
那么有递推公式 $egin{bmatrix}n\mend{bmatrix}=(n-1)egin{bmatrix}n-1\mend{bmatrix}+egin{bmatrix}n-1\m-1end{bmatrix}$。前面是把新的物品塞在一个原来的物品后边，后面是新开一个圆排列。
初始 $egin{bmatrix}1\1end{bmatrix}=1,egin{bmatrix}n\mend{bmatrix}=0(n<m)$。
这毒瘤玩意居然没有单个的通项公式
有个式子：$n^{overline{m}}=sumlimits^{m}_{i=0}egin{bmatrix}m\iend{bmatrix}n^i$。
组合意义？不会
理性证明？看PB的去（算了还是搬过来吧）
$$n^{overline{m+1}}$$
$$(n+m)n^{overline{m}}$$
$$(n+m)sumlimits^{m}_{i=0}egin{bmatrix}m\iend{bmatrix}n^i$$
$$sumlimits^{m+1}_{i=0}(megin{bmatrix}m\iend{bmatrix}+egin{bmatrix}m\i-1end{bmatrix})n^i$$
$$sumlimits^{m+1}_{i=0}egin{bmatrix}m+1\iend{bmatrix}n^i$$
求一行的：$x^{overline{n}}=sumlimits^{n}_{i=0}egin{bmatrix}n\iend{bmatrix}x^i$。
所以只要求出 $x^{overline{n}}$ 这个多项式即可。
设 $F_n(x)=x^{overline{n}}$。
当 $n$ 是奇数时 $F_n(x)=(x+n-1)F_{n-1}(x)$，不管。
当 $n$ 是偶数时 $F_n(x)=F_{frac{n}{2}}(x)F_{frac{n}{2}}(x+frac{n}{2})$。
（为方便将式子变为 $F_{2n}(x)=F_n(x)F_n(x+n)$）
假设已经求出 $F_n(x)=sumlimits_{i=0}^na_ix^i$。
$$F_n(x+n)$$
$$sumlimits_{i=0}^na_i(x+n)^i$$
$$sumlimits_{i=0}^na_isumlimits_{j=0}^idbinom{i}{j}x^jn^{i-j}$$
$$sumlimits_{i=0}^na_ii!sumlimits_{j=0}^idfrac{x^j}{j!}dfrac{n^{i-j}}{(i-j)!}$$
$$sumlimits_{j=0}^ndfrac{x^j}{j!}sumlimits_{i=j}^n(a_ii!)dfrac{n^{i-j}}{(i-j)!}$$
令 $A_i=a_ii!,B_i=dfrac{n^{n-i}}{(n-i)!}$，那么 $x^j$ 的系数是 $dfrac{A imes B}{j!}[x^{j+n}]$。
时间复杂度 $O(nlog n)$。
求一列的：
考虑生成函数 $F(x)=sumlimits_{i=1}^{+infty}(i-1)!dfrac{x^i}{i!}=sumlimits_{i=1}^{+infty}dfrac{x^i}{i}$（注意下界是 $1$）。表示把 $n$ 个球形成圆排列（非空）的指数型生成函数（斯特林数中集合没有区别，所以要指数型）。那么 $dfrac{F^m(x)}{m!}$ 就是把 $n$ 个球形成 $m$ 个圆排列且每个圆排列非空的方案数的指数型生成函数。那么 $dfrac{egin{bmatrix}i\mend{bmatrix}}{i!}=dfrac{F^m(x)}{m!}[x^i]$。$O(nlog n)$。
第二类斯特林数的定义：$egin{Bmatrix}n\mend{Bmatrix}$ 表示把 $n$ 个不同的物品放进 $m$ 个没有区别的集合，且每个集合都非空的方案数。
那么有递推公式 $egin{Bmatrix}n\mend{Bmatrix}=megin{Bmatrix}n-1\mend{Bmatrix}+egin{Bmatrix}n-1\m-1end{Bmatrix}$。前面是把新的物品随便找个集合塞下，后面是新开一个集合。
初始 $egin{Bmatrix}1\1end{Bmatrix}=1,egin{Bmatrix}n\mend{Bmatrix}=0(n<m)$。
有个式子：$n^m=sumlimits^{m}_{i=0}egin{Bmatrix}m\iend{Bmatrix}dbinom{n}{i}i!=sumlimits^m_{i=0}egin{Bmatrix}m\iend{Bmatrix}n^{underline{i}}$。
组合意义理解一下，左边是 $m$ 个不同物品扔进 $n$ 个不同集合，且可以有空集合的方案数。右边枚举有多少个非空集合，然后把 $m$ 个物品放进这些集合里。注意第二类斯特林数中集合没有区别，所以要乘回一个 $i!$ 使他们有区别。
二项式反演后可得通项公式 $egin{Bmatrix}n\mend{Bmatrix}=dfrac{1}{m!}sumlimits^m_{k=0}(-1)^kdbinom{m}{k}(m-k)^n$。
求一行的：
发现 $egin{Bmatrix}n\iend{Bmatrix}=sumlimits^i_{k=0}dfrac{(-1)^k}{k!}dfrac{(i-k)^n}{(i-k)!}$，是个卷积的形式，$O(nlog n)$ 求解。
求一列的：
考虑生成函数 $F(x)=sumlimits_{i=1}^{+infty}dfrac{x^i}{i!}=e^x-1$（注意下界是 $1$）。表示把 $n$ 个球丢入一个集合（非空）的指数型生成函数（斯特林数中集合没有区别，所以要指数型）。类似上面的做法即可。$O(nlog n)$。
还有一种方法。考虑 $F_m(x)=sumlimits_{i=0}^{+infty}egin{Bmatrix}i\mend{Bmatrix}x^i$。那么显然有 $F_0(x)=1$。
$$F_m(x)=sumlimits_{i=0}^{+infty}egin{Bmatrix}i\mend{Bmatrix}x^i$$
$$F_m(x)=sumlimits_{i=0}^{+infty}(megin{Bmatrix}i-1\mend{Bmatrix}+egin{Bmatrix}i-1\m-1end{Bmatrix})x^i$$
$$F_m(x)=msumlimits_{i=0}^{+infty}egin{Bmatrix}i-1\mend{Bmatrix}x^i+sumlimits_{i=0}^{+infty}egin{Bmatrix}i-1\m-1end{Bmatrix}x^i$$
$$F_m(x)=msumlimits_{i=0}^{+infty}egin{Bmatrix}i\mend{Bmatrix}x^{i+1}+sumlimits_{i=0}^{+infty}egin{Bmatrix}i\m-1end{Bmatrix}x^{i+1}$$
$$F_m(x)=mxF_m(x)+xF_{m-1}(x)$$
$$F_m(x)=dfrac{xF_{m-1}(x)}{1-mx}$$
$$F_m(x)=dfrac{x^m}{prodlimits_{i=1}^m(1-ix)}$$
分母实际上是 $prodlimits_{i=1}^m(x-i)$ 的系数倒置。可以用上面的方法。也可以 $O(nlog n)$，常数更小。
首先由两个很显然的式子：
$n^{overline{m}}=(-1)^{n+1}(-n)^{underline{m}}$
$n^{underline{m}}=(-1)^{n+1}(-n)^{overline{m}}$
总结一下上面提到的性质：（顺便引入一些新的）
$n!=sumlimits^n_{i=0}egin{bmatrix}n\iend{bmatrix}$（其实就是下面的式子令 $n=1$，$m=n$，也可以用抽象代数的意义证）
$n^{overline{m}}=sumlimits^m_{i=0}egin{bmatrix}m\iend{bmatrix}n^i$
$n^{underline{m}}=sumlimits^m_{i=0}(-1)^{m-i}egin{bmatrix}m\iend{bmatrix}n^i$（也可以用数学归纳法证）
$n^m=sumlimits^m_{i=0}egin{Bmatrix}m\iend{Bmatrix}n^{underline{i}}=sumlimits^m_{i=0}egin{Bmatrix}m\iend{Bmatrix}dbinom{n}{i}i!$
$n^m=sumlimits^m_{i=0}(-1)^{m-i}egin{Bmatrix}m\iend{Bmatrix}n^{overline{i}}$（下面会讲到怎么证）
$sumlimits^n_{i=0}i^k=frac{(n+1)^{underline{k+1}}}{k+1}-sumlimits_{i=0}^{k-1}(-1)^{k-i}egin{bmatrix}k\iend{bmatrix}sumlimits_{j=0}^nj^i$
$sumlimits^n_{i=0}i^k=sumlimits^k_{i=0}egin{Bmatrix}k\iend{Bmatrix}dfrac{(n+1)^{underline{i+1}}}{i+1}$
关于最后一个式子的证明：（倒数第二个自己来咕了）
$$sumlimits^n_{i=0}sumlimits^k_{j=0}egin{Bmatrix}k\jend{Bmatrix}dbinom{i}{j}j!$$
$$sumlimits^k_{j=0}j!egin{Bmatrix}k\jend{Bmatrix}sumlimits^n_{i=0}dbinom{i}{j}$$
$$sumlimits^k_{j=0}j!egin{Bmatrix}k\jend{Bmatrix}dbinom{n+1}{j+1}$$
$$sumlimits^k_{j=0}j!egin{Bmatrix}k\jend{Bmatrix}dfrac{(n+1)^{underline{j+1}}}{j+1}$$
中间 $sumlimits^n_{i=0}dbinom{i}{j}=dbinom{n+1}{j+1}$ 就是传说中的杨辉恒等式。右边是从 $n+1$ 个位置中选 $j+1$ 个位置，左边是枚举最右边的位置（$i+1$），然后从前 $i$ 个位置中选剩下的 $j$ 个。
有些题目中会用到普通幂和上升/下降幂转换的方法来做。根据PB的总结，当普通幂转上升/下降幂时用第二类，当上升/下降幂转普通幂时用第一类。
斯特林反演：
长得和二项式反演很像。
$$f_n=sumlimits^n_{k=0}(-1)^kegin{bmatrix}n\kend{bmatrix}g_kiff g_n=sumlimits^n_{k=0}(-1)^kegin{Bmatrix}n\kend{Bmatrix}f_k$$
$$f_n=sumlimits^n_{k=0}egin{bmatrix}n\kend{bmatrix}g_kiff g_n=sumlimits^n_{k=0}(-1)^{n-k}egin{Bmatrix}n\kend{Bmatrix}f_k$$
用这个式子也可以证明上面的一些式子。
证明的话需要两个反转公式：
$$sum_{i=m}^n(-1)^{n-i}egin{bmatrix}n\iend{bmatrix}egin{Bmatrix}i\mend{Bmatrix}=[n=m]$$
$$sum_{i=m}^n(-1)^{n-i}egin{Bmatrix}n\iend{Bmatrix}egin{bmatrix}i\mend{bmatrix}=[n=m]$$
两个奇怪的柿子：
$$egin{Bmatrix}n+1\m+1end{Bmatrix}=sum_{k}inom{n}{k}egin{Bmatrix}k\mend{Bmatrix}$$
证明：后面那个相当于从 $n$ 个物品中选出一些，并分成 $m$ 个无序非空集合。
前面那个是把 $n+1$ 个物品分成 $m+1$ 个无序非空集合。
钦定这 $n+1$ 个物品中有一个关键物品，分成的 $m+1$ 个集合中恰好一个含有关键物品，删掉这个集合，显然和后半部分等价。
$$egin{bmatrix}n+1\m+1end{bmatrix}=sum_{k}egin{bmatrix}n\kend{bmatrix}inom{k}{m}$$
证明：后面那个相当于把 $n$ 个物品分成若干个圆排列，再选出 $m$ 个圆排列。
前面那个是把 $n+1$ 个物品分成 $m+1$ 个圆排列。
钦定这 $n+1$ 个物品中有一个关键物品，分成的 $m+1$ 个圆排列中恰好一个含有关键物品，将包含关键物品的那个环从关键物品那里断开。
断开之后会变成一个排列，注意到排列是可以和大小之和一定的圆排列集合一一对应的。
将这些圆排列和原来没被断掉的 $m$ 个圆排列合在一起看，显然和后半部分等价。
暂时先咕到这里。