斯特林数

生成函数

同一列第二类斯特林数：一个盒子的 egf 是 \(e^x-1\)，有 \(k\) 个盒子但是盒子之间无区分，所以同一列斯特林数的 egf 是 \((e^x-1)^k/k!\)．还有一个东西是根据它的递推式解出来 ogf 是 \({\frac{x^k}{\prod(1-ix)}}\)．

如果不限定盒子个数，那么 egf 是 \(\exp(e^x-1)\)，这就是贝尔数的 egf。

同一行第二类斯特林数：利用 egf 列通项：\(\begin{Bmatrix}n\\k\end{Bmatrix}=\frac{n!}{k!}[x^n]\sum\limits_{i=0}^k\binom{k}{i}e^i(-1)^{k-i}=\sum\limits_{i=0}^k\frac{i^n(-1)^{k-i}}{i!(k-i)!}\)，对所有 \(k\) 求这个式子的值于是卷积计算。

同一列第一类斯特林数：单个轮换 egf 是置换 egf 取 ln，而置换 egf 是 \(\frac{1}{1-x}\) 那么轮换的 egf 是 \(\ln(\frac{1}{1-x})=-\ln(1-x)\)，和上面同理计算其 \(k\) 次方除掉 \(k!\) 就行。

同一行第一类斯特林数：利用递推式解出来 ogf 是 \(x^{\overline{n}}\)，直接分治 ntt 是 2log。

套路是给定 \(F(x)\) 的系数，可以通过一次卷积求出 \(F(x+c)\) 的系数，列出式子之后交换求和号，发现是个差卷积的形式。利用这个将所有 \(x^{\overline{2^i}}\) 算出之后选取一些乘起来，复杂度是 \(T(n)=T(n/2)+\mathcal{O}(n\log n)=\mathcal{O}(n\log n)\)．

幂之间的转换

\[\begin{aligned} x^n&=\sum_k\begin{Bmatrix}n\\k\end{Bmatrix}x^{\underline{k}}\ \\ x^{\overline{n}}&=\sum_k\begin{bmatrix}n\\k\end{bmatrix}x^k \end{aligned} \]

这个应该怎么记忆，\(x^{\overline n}\geq x^n\geq x^{\underline n}\)，所以应该是若干个下降幂乘上一个什么系数得到普通幂，普通幂得到上升幂。利用 \(x^{\underline n}=(-1)^n(-x)^{\overline n}\) 再还元就能得到：

\[\begin{aligned} x^n&=\sum_k\begin{Bmatrix}n\\k\end{Bmatrix}(-1)^{n-k}x^{\overline{k}} \\ x^{\underline{n}}&=\sum_k\begin{bmatrix}n\\k\end{bmatrix}(-1)^{n-k}x^k \end{aligned} \]

反转公式

上一节中把其中一个往另一个式子的右侧代入，能够得到四个比较对称的式子，两边提取 \([x^n]\) 就得到了 \([n=m]\) 的展开，为了更好记忆这里记作 \([l=r]\)，那么就有：

\[\begin{aligned} \sum_{k=l}^r\begin{Bmatrix}r\\k\end{Bmatrix}\begin{bmatrix}k\\l\end{bmatrix}(-1)^{k-l}=[l=r]\\ \sum_{k=l}^r\begin{Bmatrix}r\\k\end{Bmatrix}\begin{bmatrix}k\\l\end{bmatrix}(-1)^{r-k}=[l=r]\\ \sum_{k=l}^r\begin{bmatrix}r\\k\end{bmatrix}\begin{Bmatrix}k\\l\end{Bmatrix}(-1)^{k-l}=[l=r]\\ \sum_{k=l}^r\begin{bmatrix}r\\k\end{bmatrix}\begin{Bmatrix}k\\l\end{Bmatrix}(-1)^{r-k}=[l=r]\\ \end{aligned} \]

这四个式子非常对称，仅需要记忆 \(\begin{Bmatrix}r\\k\end{Bmatrix}\begin{bmatrix}k\\l\end{bmatrix}\) 和 \(\begin{bmatrix}r\\k\end{bmatrix}\begin{Bmatrix}k\\l\end{Bmatrix}\) 可以互换；\((-1)^{k-l}\) 和 \((-1)^{r-k}\) 可以互换就能把这些记住。

斯特林反演

\[f(n)=\sum_{i=0}^n\begin{Bmatrix}n\\i\end{Bmatrix}g(i)\Longleftrightarrow g(n)=\sum_{i=0}^n(-1)^{n-i}\begin{bmatrix}n\\i\end{bmatrix}f(i) \]

证明（来自 cjl）

尝试利用 egf 解决问题，令 \(F,G\) 为 \(f,g\) 的 egf：

\[\begin{aligned} F(x)&=\sum_k \frac{f_kx^k}{k!}=\sum_{k=0}\frac{x^k}{k!}\begin{Bmatrix}k\\i\end{Bmatrix}g_i \\ &=\sum_i g_i\sum_{k=i}\begin{Bmatrix}k\\i\end{Bmatrix}\frac{x^k}{k!}=\sum_{i=0}g_i\frac{(e^x-1)^i}{i!} \\ &=G(e^x-1) \end{aligned} \]

\(e^x-1\) 的复合逆是 \(\ln(1+x)\)，于是有 \(F(\ln(1+x))=G(x)\)，那么对于另一方向：

\[\begin{aligned} G(x)&=\sum_k f_k\frac{\ln(1+x)^k}{k!}=\sum_k f_k\frac{(-1)^k(-\ln(1-(-x)))^k}{k!}\\ &=\sum_k f_k(-1)^k\sum_{i=k}\begin{bmatrix}i\\k\end{bmatrix} \frac{(-x)^i}{i!}\\ &=\sum_i \frac{x^i}{i!}\sum_{k=i}\begin{bmatrix}i\\k\end{bmatrix}(-1)^{i-k}f_k \end{aligned} \]

类比二项式反演，尝试证另一个方向的斯特林反演：

\[f(m)=\sum_{k\geq m}\begin{Bmatrix}k\\m\end{Bmatrix}g(k)\Longleftrightarrow g(m)=\sum_{k\geq m}(-1)^{k-m}\begin{bmatrix}k\\m\end{bmatrix}f(k) \]

证明（感谢 qwaszx 指点）

来类比这里的证明，普通幂和斯特林数不是很搭，用下降幂来解决。

\[\begin{aligned} \sum_{m\geq 0} f(m)z^{\underline m}&=\sum_{m\geq 0}\sum_{k\geq m}\begin{Bmatrix}k\\m\end{Bmatrix}g(k)z^{\underline m}\\ &=\sum_{k\geq 0}g(k)\sum_{m\leq k}\begin{Bmatrix}k\\m\end{Bmatrix}z^{\underline m}\\ &=\sum_{k\geq 0}g(k)z^k \end{aligned} \]

直接两边提取 \([z^k]\)，那么左侧要计算 \(f(m)\) 的贡献系数是 \([z^k]z^{\underline m}=\begin{bmatrix}m\\k\end{bmatrix}(-1)^{m-k}\)（下降幂转普通幂），于是就完成了证明。每一步都是当且仅当所以逆命题也成立。

恒等式

具体数学 P221

(6.15) 组合意义 \(\binom{n}{k}\) 是把 \(n+1\) 所在的集合给选出来；(6.16) 归纳不是很难（这个怎么组合意义啊？）；(6.17) 和 (6.18) 是 (6.15) 和 (6.16) 二项式反演得到的。

(6.19) 就是同一行第二类斯特林数那个式子，另一个推法是对 \(m^n=\sum_k\binom{m}{k}{n\brace k}k!\) 二项式反演，这个式子是 \(n\) 个不同球放进 \(m\) 个可空盒子方案数，右侧是枚举非空盒子个数。

(6.20) 组合意义，考虑哪个盒子中最小编号球最大，枚举这个球是哪个，对于前面的直接 \(k\brace m\) 分出来 \(m\) 个盒子，对于后面 \(n-k\) 个球每个球都有 \(m+1\) 个盒子可以选择放进去。(6.21) 也一样，后面 \(n-k\) 个球放入的方案数从左到右分别是 \(k+1,k+2\cdots n\)，乘起来就是 \(n^{\underline{n-k}}\)．

(6.22) (6.23)：回想对二项式系数斜线求和是怎么处理的，那么这里也一样，将 \(n+0\brace 0\) 看成 \(n+1\brace 0\) 然后一层层合并，(6.23) 也一样。

/fn 后面的不想看了开摆

互不相等容斥

老题新做一下 TopCoder 13444 CountTables。广为人知的做法是 \(f_i\) 表示 \(n\times i\) 矩阵每行互不相同的个数，\(g_i\) 是每行每列互不相同的个数。将每一列看成一个元素，那么将 \(f_i\) 中的相等元素合并起来就得到了一个 \(g_j\)，所以 \(f_i=\sum_{j\leq i}\begin{Bmatrix}i\\j\end{Bmatrix}g_j\)，而 \(f_i=(c^i)^{\underline n}\) 从而可以利用斯特林反演计算出 \(g_m\) 的值。

还是想用常规的容斥思路来算。现在问题是有 \(n\) 个元素 \(a_1,a_2,\cdots a_n\)，每个元素都有若干取值可以取，计算满足 \(a\) 两两不同的方案数。那么限制就是 \(\prod_{i<j}[a_i\neq a_j]\)，写成 \(\prod_{i<j}(1-[a_i=a_j])\) 后将其展开，每个括号取 \(1\) 或者 \(-[a_i=a_j]\)，那么相等关系就会连成若干个连通块，一条边连起来表示这个括号取了 \(-[a_i=a_j]\)，没连表示取 \(1\)．

把每个连通块看成一个点的集合，现在对于 \(1\sim n\) 的一个集合划分计算容斥系数和，其等于各个连通块容斥系数和的乘积。那么现在要计算的就是对于这个连通块内部的边，有多少边集 \(E\) 能够将所有点连通，并且带来 \((-1)^{|E|}\) 容斥系数的贡献。

用总的贡献减去不合法的贡献。假设现在有 \(k\) 个点，取边 \((1,2)\)，对于任意一个方案而言将其存在状态取反即得到另一个边个数奇偶性不同的方案，这是一个双射，两个方案权值相反可以抵消。仅有 \(k=1\) 的时候选不出一条边，所以总的贡献和是 \([k=1]\)．

假设 \(f_i\) 表示 \(i\) 个点的答案，计算不合法贡献就枚举 \(i\) 所在连通块是哪些点，那么就有 \(f_i=[i=1]-\sum_{1\leq j\leq i-1}\binom{i-1}{j-1}f_j[i-j=1]\)，所以 \(i>1\) 时就有 \(f_i=(-1)(i-1)f_{i-1}\)，那么 \(f_k=(-1)^{k-1}(k-1)!\)．

假如枚举了一个集合划分 \(\{S_1,S_2,\cdots ,S_k\}\)，那么所有能得到这个集合划分的钦定方案的容斥系数的和就是 \(\prod (-1)^{|S_i|-1}(|S_i|-1)!\)．

注意到 \((|S_i|-1)!\) 就是环排列方案数，而 \((-1)^{|S|-1}\) 看成初始有 \((-1)^n\) 每多一个 \(S\) 就乘一个 \((-1)\)，所以它其实和斯特林反演是等价的。

欧拉数

欧拉数：恰好满足有 \(k\) 个升高的排列 \(\pi_1\pi_2\cdots \pi_n\) 的个数。其中升高定义为 \(\pi_i<\pi_{i+1}\) 的 \(i\) 的个数，记做 \(\left\langle\begin{matrix}n\\k\end{matrix}\right\rangle\)，考虑将 \(n\) 往 \((n-1)\) 的排列中插入可得递推式：\(\left\langle\begin{matrix}n\\k\end{matrix}\right\rangle=(k+1)\left\langle\begin{matrix}n-1\\k\end{matrix}\right\rangle+(n-k)\left\langle\begin{matrix}n-1\\k-1\end{matrix}\right\rangle\)．

回想起不等关系，尝试用容斥去算欧拉数 \(\left\langle\begin{matrix}n\\m\end{matrix}\right\rangle\)。假定钦定了若干个间隔是 <，它们一共形成了 \(k\) 个极长连续上升段，那么一共钦定了 \(n-k\) 个升高，根据二项式反演其容斥系数为 \((-1)^{n-k-m}\binom{n-k}{m}\)，而考虑每个极长连续段看成一个盒子，那么方案数就是将 \(n\) 个球放进 \(k\) 个盒子中，并且盒子之间有顺序（由于每个段必须要求上升所以不需要考虑球之间的顺序），那么方案数是 \(\begin{Bmatrix}n\\k\end{Bmatrix}k!\)，至此得到了具体数学 P225 (6.40)：

\[\left\langle\begin{matrix}n\\m\end{matrix}\right\rangle=\sum_k{{n}\brace{k}}\binom{n-k}{m}(-1)^{n-k-m}k!\tag{6.40} \]

而 (6.39) 即为 (6.40) 逆用二项式反演得到的结果，在 (6.40) 中令 \(k\gets n-k\) 换元即可看出 \(f(i)=\left\langle\begin{matrix}n\\i\end{matrix}\right\rangle,g(i)=\begin{Bmatrix}n\\n-i\end{Bmatrix}(n-i)!\)，\(f(m)=\sum_{k\geq m}\binom{k}{m}(-1)^{k-m}g(k)\) 从而导出 \(g(m)=\sum_{k\geq m}\binom{k}{m}f(k)\)，再换元 \(m\leq n-m\) 就得到了 (6.39)．