因为我太菜了不推一遍根本学不会所以就写了这篇笔记来复读学长……

第一类斯特林数

定义

组合意义：把 \(n\) 个不同元素分成 \(m\) 个不考虑顺序的环的方案个数，记作 \(\begin{bmatrix}n\\m\end{bmatrix}\)

递推公式：\(\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\) 个

性质

同一行的第一类斯特林数：\(\sum\limits_{i=0}^n\begin{bmatrix}n\\i\end{bmatrix}=n!\)
证明1：把 \(1\dots n\) 映射到 \(1\dots n\)，那么一定会有一些环产生，而这样的方案与将 \(n\) 个不同元素分成 \(m\) 个不考虑顺序的环方案一一对应，映射的方案为 \(n!\) 种，所以所求即为 \(n!\)
证明2：想不到学长的神仙方法只好硬算，由递推公式代入可得，\(\sum\limits_{i=0}^n\begin{bmatrix}n\\i\end{bmatrix}=n\sum\limits_{i=0}^{n-1}\begin{bmatrix}n-1\\i\end{bmatrix}\)，这样重复的话每次都能提出来一个数，最后就会变成 \(n!\sum\limits_{i=0}^0\begin{bmatrix}0\\i\end{bmatrix}=n!\)

用途

用 \(x^{\overline{k}}\) 来表示 \(\prod\limits_{i=0}^k(x+i-1)\)
用 \(x^{\underline{k}}\) 来表示 \(\prod\limits_{i=0}^k(x-i+1)\)

上升幂转通常幂

\[x^{\overline{n}}=\sum\limits_{i=0}^n\begin{bmatrix}n\\i\end{bmatrix}x^i\tag{1} \]

证明：使用数学归纳法
当 \(n=0\) 时：左右皆为 \(1\)，成立
假设当 \(x^{\overline{n}}\) 时原式成立
那么推一下 \(x^{\overline{n+1}}\)：

\[\begin{aligned} x^{\overline{n+1}} &=(x+n)x^{\overline{n}}\\ &=(x+n)\sum\limits_{i=0}^n\begin{bmatrix}n\\i\end{bmatrix}x^i\\ &=\sum\limits_{i=0}^n\begin{bmatrix}n\\i\end{bmatrix}x^{i+1}+n\sum\limits_{i=0}^n\begin{bmatrix}n\\i\end{bmatrix}x^i\\ &=\sum\limits_{i=1}^{n+1}\begin{bmatrix}n\\i-1\end{bmatrix}x^i+\sum\limits_{i=0}^nn\begin{bmatrix}n\\i\end{bmatrix}x^i\\ &=\sum\limits_{i=0}^{n+1}\begin{bmatrix}n\\i-1\end{bmatrix}x^i+\sum\limits_{i=0}^{n+1}n\begin{bmatrix}n\\i\end{bmatrix}x^i\\ &=\sum\limits_{i=0}^{n+1}\begin{bmatrix}n+1\\i\end{bmatrix}x^i\\ \end{aligned}\]

即此结论对于 \(x^{\overline{n+1}}\) 也成立

下降幂转上升幂

\[x^{\underline{n}}=(-x)^{\overline{n}}\cdot(-1)^n,\ \ \ \ x^{\overline{n}}=(-x)^{\underline{n}}\cdot(-1)^n\tag{2} \]

下降幂转通常幂

把上面的式子代来代去可得：

\[x^{\underline{n}}=\sum\limits_{i=0}^n\begin{bmatrix}n\\i\end{bmatrix}(-1)^{n-i}x^i\tag{3} \]

应用

关于求法：

• 按递推公式暴力求，\(O(n^2)\)
• 多项式做法，待补，\(O(n\log n)\)

[FJOI2016]建筑师

从左看能看到 \(a\) 个，右边能看到 \(b\) 个，那么最高的那个左右肯定都能看到
就会发现所有楼被分成了 \(a+b-1\) 部分，每部分最高的那栋楼组成了最终看到的楼（最高的楼自己占一部分）
发现只要先把最高的楼拿出来，剩下的随便分成 \(a+b-2\) 部分，就一定存在满足条件的方案，这次划分的方案数是 \(\begin{bmatrix}n-1\\a+b-2\end{bmatrix}\) 种
但是斯特林数里是不考虑环之间的顺序的，所以需要考虑多少在左边，多少在右边，这样分完后方案是唯一的，这次划分的方案数是 \(\begin{pmatrix}a+b-2\\a-1\end{pmatrix}\) 种
预处理后直接算就可以了，复杂度是平方的

有一道加强版的这题需要用多项式求，待补

第二类斯特林数

定义

组合意义：把 \(n\) 个不同元素分成不考虑顺序的 \(m\) 堆的方案个数，记作 \(\begin{Bmatrix}n\\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}\)
其中加入一个元素时，前半部分相当于单开出新的一堆，而后半部分相当于找一堆插入进去，可插入的位置有 \(n-1\) 个

用途

似乎跟第一类斯特林数是反着来的……

通常幂转下降幂

\[x^n=\sum\limits_{i=0}^n\begin{Bmatrix}n\\i\end{Bmatrix}x^{\underline{i}}\tag{4} \]

证明：
其实还有一个常见的形式是：

\[x^n=\sum\limits_{i=0}^n\begin{Bmatrix}n\\i\end{Bmatrix}\begin{pmatrix}x\\i\end{pmatrix}i!\tag{5} \]

这个式子可以理解为：把 \(n\) 个元素放入 \(x\) 堆（可以有空堆），可以先确定有 \(i\) 堆最后有球，然后把球分成 \(i\) 堆，然后从 \(x\) 堆里选 \(i\) 堆放球，因为要考虑顺序所以乘上 \(i!\)

通常幂转上升幂

和之前一样代入互相转化的式子可得：

\[x^n=\sum\limits_{i=0}^n\begin{Bmatrix}n\\i\end{Bmatrix}(-1)^{n-i}x^{\overline{i}}\tag{6} \]

应用

Crash 的文明世界

有一棵树，求对于每个点 \(i\)：

\[\sum\limits_{j=1}^n\text{dis}(i,j)^k \]

如果没有这个 \(k\) 次方，就是直接换根 \(dp\)，但是这个式子中，当我们换根时，\(\text{dis}\) 的变化加上 \(k\) 次幂不好维护，这个时候每个点的价值都随着决策点的变动而变动
所以应当考虑怎么把 \(k\) 的影响固定下来
发现用刚刚的式子，可以推出：

\[\text{dis}(i,j)^k=\sum\limits_{i=0}^k\begin{Bmatrix}k\\i\end{Bmatrix}\begin{pmatrix}\text{dis}(i,j)\\i\end{pmatrix}i! \]

这里面 \(k\) 只对前半部分造成一个不变的影响，而且和 \(x\) 分开了，现在其实需要求得就是中间的部分了，就可以换根 \(dp\) 解决了
那么合并子树的过程：

\[\begin{pmatrix}x\\i\end{pmatrix}+\begin{pmatrix}x\\i-1\end{pmatrix}=\begin{pmatrix}x+1\\i\end{pmatrix} \]

换根的过程也类似
可以分别在每个点存下每一个 \(i\) 的贡献，最后再把斯特林数和阶乘算进去即可

斯特林反演

反转公式

通过之前的推导可以发现两类斯特林数都能使上升/下降幂和通常幂建立联系
也就是说通过代入其实可以使两类斯特林数建立联系
处理 \((1)(2)(4)\) 式得：

\[\begin{aligned} x^n &=\sum\limits_{i=0}^n\begin{Bmatrix}n\\i\end{Bmatrix}x^{\underline{i}}\\ &=\sum\limits_{i=0}^n\begin{Bmatrix}n\\i\end{Bmatrix}(-1)^i(-x)^{\overline{i}}\\ &=\sum\limits_{i=0}^n\begin{Bmatrix}n\\i\end{Bmatrix}(-1)^i\sum\limits_{j=0}^i\begin{bmatrix}i\\j\end{bmatrix}(-x)^j\\ &=\sum\limits_{j=0}^nx^j\sum\limits_{i=j}^n\begin{bmatrix}i\\j\end{bmatrix}\begin{Bmatrix}n\\i\end{Bmatrix}(-1)^{i-j}\\ \end{aligned}\]

发现当且仅当 \(j=n\) 时，右边为 \(x^n\)
因此此时若 \(j=0\dots n-1\)，右边的后半部分都为 \(0\)
即

\[\sum\limits_{i=j}^n\begin{bmatrix}i\\j\end{bmatrix}\begin{Bmatrix}n\\i\end{Bmatrix}(-1)^{i-j}=[j=n]\tag{7} \]

同理可得

\[\sum\limits_{i=j}^n\begin{Bmatrix}i\\j\end{Bmatrix}\begin{bmatrix}n\\i\end{bmatrix}(-1)^{i-j}=[j=n]\tag{8} \]

斯特林反演

结论：

\[f(n)=\sum\limits_{i=1}^n\begin{Bmatrix}n\\i\end{Bmatrix}g(i)\Leftrightarrow g(n)=\sum\limits_{i=1}^n(-1)^{n-i}\begin{bmatrix}n\\i\end{bmatrix}f(i)\tag{9} \]

证明：
用莫比乌斯反演的相似证法来逆推

\[\begin{aligned} \sum\limits_{i=1}^n(-1)^{n-i}\begin{bmatrix}n\\i\end{bmatrix}f(i) &=\sum\limits_{i=1}^n(-1)^{n-i}\begin{bmatrix}n\\i\end{bmatrix}\sum\limits_{j=1}^i\begin{Bmatrix}i\\j\end{Bmatrix}g(j)\\ &=\sum\limits_{j=1}^ng(j)\sum\limits_{i=j}^n\begin{bmatrix}n\\i\end{bmatrix}\begin{Bmatrix}i\\j\end{Bmatrix}(-1)^{n-i}\\ &=\sum\limits_{j=1}^ng(j)[j=n]\\ &=g(n) \end{aligned}\]

到这里可以发现其实反演就是两个函数互相转换的途径，在做题时需要做的是设出恰当的函数并找出适合反演的函数推导关系
之前学长讲过反演的本质是容斥，其实反演就是一个看上去挺复杂，但有一些妙妙的关系使式子内部互相消去，最后得到所求单个值的过程