Strling数入门指南
tNuxvs5t
·
·
算法·理论
由于看不懂你谷和OI Wiki上非常形而上学的知识，这里对Strling数进行主观的串线讲解。
前置知识：离散变换技巧，生成函数基础，指数生成函数
文尾附四个模板题（不包括转多项式）的做法。
定义
第二类斯特林数 \left\{ {m \atop n} \right\} 表示将m个有序元素分成n个无序非空集合的方案数。
第一类斯特林数 \left[ {m \atop n} \right] 表示将m个有序元素分为n个无序圆排列的方案数。
什么是圆排列？就是将一个排列围成一圈，我们知道排列的前提是n个本质不同（且有序）的元素组成一列的方案数，一般来说这个值是 n!。那么他们能组成多少种圆牌列，考虑取每个圆牌列的最小元素，以顺时针为正方向计数，每个圆牌列贡献n个计数，并且由于所有圆牌列本质不同（关于旋转循环群封闭，不包括立体翻转），所以有 (n-1)! 个圆牌列。
进而有如下组合意义递推式：
\begin{align*}
\left\{ \begin{matrix} n \\ m \end{matrix} \right\} &= \left\{ \begin{matrix} n-1 \\ m-1 \end{matrix} \right\} + m \left\{ \begin{matrix} n-1 \\ m \end{matrix} \right\} \\
\left[ \begin{matrix} n \\ m \end{matrix} \right] &= \left[ \begin{matrix} n-1 \\ m-1 \end{matrix} \right] + (n-1) \left[ \begin{matrix} n-1 \\ m \end{matrix} \right]
\end{align*}
这里重点强调一下着为什么体现了集合的无序性，考虑有序的元素，每个元素新开集合直接确定了这个集合的特征（最大元素），并且所有集合特征不同，满足无序性。（如果有序，那么第一项需要乘系数m）
接下来我们考虑求出这东西的二重生成函数，形如 F(x, y) = \sum_{\substack{n \geq 0 \\ m \geq 0}} f(n, m) x^n y^m.
不妨先从一个简单的情况入手，先来考虑广义二项式系数 \binom{n}{m} 作系数的情况。
\begin{align*}
F(x, y) &= \sum_{\substack{n \geq 0 \\ m \geq 0}} \binom{n}{m} z^n w^m \\
&= \sum_{\substack{n \geq 0 \\ m \geq 0}} \binom{n}{m} z^n w^m \\
&= \sum_{\substack{n \geq 0 \\ m \geq 0}} \binom{n-1}{m-1} z^n w^m + \sum_{\substack{n \geq 0 \\ m \geq 0}} \binom{n-1}{m} z^n w^m \\
&= w \sum_{\substack{n \geq 0 \\ m \geq 0}} \binom{n-1}{m} z^n w^m + \sum_{\substack{n \geq 0 \\ m \geq 0}} \binom{n-1}{m} z^n w^m \\
&= wz \sum_{n, m \geq 0} \binom{n}{m} z^n w^m + z \sum_{\substack{n \geq 0 \\ m \geq 0}} \binom{n}{m} z^n w^m \\
&\quad + (w+1) \sum_{m \geq 0} \binom{-1}{m} w^m \\
&= (wz + z) F + (w+1) (w+1)^{-1} \\
&= z(1+w) F + 1 \\
\therefore \quad F &= \frac{1}{1 - z - zw}.
\end{align*}
我们很顺利地求出了这个二重生成函数，注意我们仅仅使用了递推式。在本行后的内容将会充分发挥二重生成函数的威力。
但如果我们直接把这个方法平移到第二类斯特林数，会得到一个难解的方程，并得到一个非常复杂的解，为了避免这种情况，转而考虑另一种生成函数：F(x, y) = \sum_{\substack{n \geq 0 \\ m \geq 0}} f(n, m) x^n y^m / n!. 它对二项式系数、斯特林数，甚至是欧拉数(Eulerian number)都有非常好的性质。
这主要要归功于 z^n/n! 拥有关于z的导数封闭性，使得一般可以得到关于z的简单偏微分方程，从而使封闭形式变得简单。至于为什么导数封闭性有用，请看下文。
首先尝试
\begin{align*}
\sum_{\substack{n \geq 0 \\ m \geq 0}} \left\{ \begin{matrix} n \\ m \end{matrix} \right\} \frac{x^n y^m}{n!}
&= \sum_{\substack{n \geq 0 \\ m \geq 0}} \left\{ \begin{matrix} n-1 \\ m-1 \end{matrix} \right\} \frac{x^n y^m}{n!} + \sum_{\substack{n \geq 0 \\ m \geq 0}} m \left\{ \begin{matrix} n-1 \\ m \end{matrix} \right\} \frac{x^n y^m}{n!} \\
&= \left\{ \begin{matrix} -1 \\ -1 \end{matrix} \right\} + \sum_{\substack{n \geq 0 \\ m \geq 0}} \left\{ \begin{matrix} n \\ m \end{matrix} \right\} \frac{x^{n+1} y^{m+1}}{(n+1)!} + \sum_{\substack{n \geq 0 \\ m \geq 0}} m \left\{ \begin{matrix} n \\ m \end{matrix} \right\} \frac{x^{n+1} y^m}{(n+1)!}
\end{align*}
等等，出现了向前移位的现象，这很不妙，这意味着我们需要考虑一个意义不明的项（实际为1）和一个看上去只能用积分来处理的式子，这将大大增加计算的复杂度。这时导数封闭性就派上用场了：我们先对原式求导，也不会改变原式的结构。
\begin{align*}
\frac{\partial F}{\partial x} &= \sum_{\substack{n \geq 0 \\ m \geq 0}} \left\{ \begin{matrix} n \\ m \end{matrix} \right\} \frac{x^{n-1}}{(n-1)!} y^m \quad \textcolor{red}{\text{able only when } n > 0} \\
&= \sum_{\substack{n \geq 0 \\ m \geq 0}} \left\{ \begin{matrix} n+1 \\ m \end{matrix} \right\} \frac{x^n}{n!} y^m \\
&= \sum_{\substack{n \geq 0 \\ m \geq 0}} \left\{ \begin{matrix} n \\ m-1 \end{matrix} \right\} \frac{x^n}{n!} y^m + \sum_{\substack{n \geq 0 \\ m \geq 0}} \left\{ \begin{matrix} n \\ m \end{matrix} \right\} \frac{x^n}{n!} y^m \\
&= y \sum_{\substack{n \geq 0 \\ m \geq 0}} \left\{ \begin{matrix} n \\ m \end{matrix} \right\} \frac{x^n}{n!} y^m + y \frac{\partial F}{\partial y} \\
&= y F + y \frac{\partial F}{\partial y} \\
\therefore \frac{\partial F}{\partial x} &= y \left( F + \frac{\partial F}{\partial y} \right)
\end{align*}
解方程， F=e^{-y}\phi(ye^x)。取 x=0，得到 \phi(x)=e^x。于是 F=e^{y(e^x-1)}。
沿用以上办法，我们得到四个异常重要的式子：
\begin{align*}
e^{z + wz} &= \sum_{m,n \geq 0} \binom{n}{m} w^m \frac{z^n}{n!} \\
e^{w(e^z - 1)} &= \sum_{m,n \geq 0} \left\{ \begin{matrix} n \\ m \end{matrix} \right\} w^m \frac{z^n}{n!} \\
\frac{1}{(1 - z)^w} &= \sum_{m,n \geq 0} \left[ \begin{matrix} n \\ m \end{matrix} \right] w^m \frac{z^n}{n!} \\
\frac{1 - w}{e^{(w - 1)z} - w} &= \sum_{m,n \geq 0} \left\langle \begin{matrix} n \\ m \end{matrix} \right\rangle w^m \frac{z^n}{n!}
\end{align*}
在本节，将使用 (2) (3) 式导出之后的几乎所有内容。
为了引出之后的内容，首先考虑一个组合意义，以第二类斯特林数为例，第二类斯特林数 \left\{ {m \atop n} \right\} 表示将m个有序元素分成n个无序非空集合的方案数，考虑让 n 个集合有序，对这个情况算两次处理。
考虑指数生成函数及其卷积的组合意义，构造 (e^z-1)^n 表示 n 个盒子，每个盒子可以放任意多个（非空）个元素的EGF，符合将 任意 m 多个元素放进 n 个盒子的情境。
同理，根据单个圆排列的方案数生成其指数生成函数再进行卷积，符合第一类斯特林数的对应情境。
于是有：
\begin{align*}
n! \sum_{m \geq 0} \left\{ \begin{matrix} m \\ n \end{matrix} \right\} \frac{z^m}{m!} &= (e^z - 1)^n \\
n! \sum_{m \geq 0} \left[ \begin{matrix} m \\ n \end{matrix} \right] \frac{z^m}{m!} &= \left( \ln \frac{1}{1-z} \right)^n
\end{align*}
我们尝试不用组合意义，只从代数角度来考虑导出这两个式子。你已经猜到了要用什么，没错就是 (2) (3) 式。
以 (3) 为例，因为它更困难：
\begin{align*}
(1 - z)^{-w} &= \sum_{m,n \geq 0} \left[ n \atop m \right] w^m \frac{z^n}{n!} \\
[w^m] (1 - z)^{-w} &= \sum_{n \geq 0} \left[ n \atop m \right] \frac{z^n}{n!} \\
\text{LHS} &= [w^m] e^{w \ln \left( \frac{1}{1 - z} \right)} \\
&= [w^m] \sum_{i \geq 0} \frac{\left( w \ln \left( \frac{1}{1 - z} \right) \right)^i}{i!} \\
&= \frac{\left( \ln \frac{1}{1 - z} \right)^m}{m!} \\
\therefore \left( \ln \frac{1}{1 - z} \right)^m &= m! \sum_{n \geq 0} \left[ n \atop m \right] \frac{z^n}{n!}
\end{align*}
易如反掌。
接下来我们考虑那个屡见不鲜的式子：上升/下降幂和普通幂的转化式，用归纳法快速证明的背后，你是否也知晓它的由来，下面让我们接着提取 z^n ，导出这两个式子。
以第二类斯特林数为例。
\begin{align*}
e^{w(e^z-1)} &= \sum_{\substack{m\geq0 \\ n\geq0}} \left\{ \begin{matrix} n \\ m \end{matrix} \right\} w^m \frac{z^n}{n!} \\
[z^n]e^{w(e^z-1)} &= \sum_{m\geq0} \left\{ \begin{matrix} n \\ m \end{matrix} \right\} \frac{w^m}{n!} \\
\text{LHS} &= [z^n] \frac{e^{we^z}}{e^w} \\
&= \frac{1}{e^w} [z^n] \sum_{i\geq0} \frac{(we^z)^i}{i!} \\
&= \frac{1}{e^w} [z^n] \sum_{i\geq0} \frac{w^i e^{iz}}{i!} \\
&= \frac{1}{e^w} [z^n] \sum_{i\geq0} \frac{w^i}{i!} \sum_{j\geq0} \frac{(iz)^j}{j!} \\
&= \frac{1}{e^w} [z^n] \sum_{j\geq0} \frac{z^j}{j!} \sum_{i\geq0} \frac{w^i}{i!} i^j \\
&= \frac{1}{e^w} \frac{1}{n!} \sum_{i\geq0} \frac{w^i}{i!} i^n \\
\therefore \sum_{m\geq0} \left\{ \begin{matrix} n \\ m \end{matrix} \right\} \frac{w^m}{n!} &= \frac{1}{e^w} \frac{1}{n!} \sum_{i\geq0} \frac{w^i}{i!} i^n \\
(e^w) \left( \sum_{m\geq0} \left\{ \begin{matrix} n \\ m \end{matrix} \right\} w^m \right) &= \sum_{i\geq0} \frac{w^i}{i!} i^n \\
\sum_{m\geq0} \sum_{k\geq0} \left\{ \begin{matrix} n \\ k \end{matrix} \right\} \frac{1}{(m-k)!} w^m &= \sum_{i\geq0} \frac{w^i}{i!} i^n \\
\sum_{k\geq0} \left\{ \begin{matrix} n \\ k \end{matrix} \right\} \frac{1}{(m-k)!} &= \frac{m^n}{m!} \\
m^n &= \sum_{k\geq0} \left\{ \begin{matrix} n \\ k \end{matrix} \right\} m^{\underline{k}}
\end{align*}
incredible result! 这样我们就得到了这个经典的式子。
同理，我们也可以得到 m^{\overline{n}} = \sum_{k \geq 0} \left[ \begin{matrix} n \\ k \end{matrix} \right] m^k。这样就完成了有关斯特林数的基本恒等式的证明。