专栏文章

Strling数入门指南

ttNuxvs5t
算法·理论参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@mio5ucuw
此快照首次捕获于
2025/12/02 13:51
3 个月前
此快照最后确认于
2025/12/02 13:51
3 个月前
查看原文
由于看不懂你谷和OI Wiki上非常形而上学的知识，这里对Strling数进行主观的串线讲解。
前置知识：离散变换技巧，生成函数基础，指数生成函数
文尾附四个模板题（不包括转多项式）的做法。
定义
第二类斯特林数 {mn}\left\{ {m \atop n} \right\} 表示将m个有序元素分成n个无序非空集合的方案数。
第一类斯特林数 [mn]\left[ {m \atop n} \right] 表示将m个有序元素分为n个无序圆排列的方案数。
什么是圆排列？就是将一个排列围成一圈，我们知道排列的前提是n个本质不同（且有序）的元素组成一列的方案数，一般来说这个值是 n!n!。那么他们能组成多少种圆牌列，考虑取每个圆牌列的最小元素，以顺时针为正方向计数，每个圆牌列贡献n个计数，并且由于所有圆牌列本质不同（关于旋转循环群封闭，不包括立体翻转），所以有 (n−1)!(n-1)! 个圆牌列。
进而有如下组合意义递推式：
{nm}={n−1m−1}+m{n−1m}[nm]=[n−1m−1]+(n−1)[n−1m]\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)=∑n≥0m≥0f(n,m)xnymF(x, y) = \sum_{\substack{n \geq 0 \\ m \geq 0}} f(n, m) x^n y^m.
不妨先从一个简单的情况入手，先来考虑广义二项式系数 (nm)\binom{n}{m} 作系数的情况。
F(x,y)=∑n≥0m≥0(nm)znwm=∑n≥0m≥0(nm)znwm=∑n≥0m≥0(n−1m−1)znwm+∑n≥0m≥0(n−1m)znwm=w∑n≥0m≥0(n−1m)znwm+∑n≥0m≥0(n−1m)znwm=wz∑n,m≥0(nm)znwm+z∑n≥0m≥0(nm)znwm+(w+1)∑m≥0(−1m)wm=(wz+z)F+(w+1)(w+1)−1=z(1+w)F+1∴F=11−z−zw.\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)=∑n≥0m≥0f(n,m)xnym/n!F(x, y) = \sum_{\substack{n \geq 0 \\ m \geq 0}} f(n, m) x^n y^m / n!. 它对二项式系数、斯特林数，甚至是欧拉数(Eulerian number)都有非常好的性质。
这主要要归功于 zn/n!z^n/n! 拥有关于z的导数封闭性，使得一般可以得到关于z的简单偏微分方程，从而使封闭形式变得简单。至于为什么导数封闭性有用，请看下文。
首先尝试
∑n≥0m≥0{nm}xnymn!=∑n≥0m≥0{n−1m−1}xnymn!+∑n≥0m≥0m{n−1m}xnymn!={−1−1}+∑n≥0m≥0{nm}xn+1ym+1(n+1)!+∑n≥0m≥0m{nm}xn+1ym(n+1)!\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）和一个看上去只能用积分来处理的式子，这将大大增加计算的复杂度。这时导数封闭性就派上用场了：我们先对原式求导，也不会改变原式的结构。
∂F∂x=∑n≥0m≥0{nm}xn−1(n−1)!ymable only when n>0=∑n≥0m≥0{n+1m}xnn!ym=∑n≥0m≥0{nm−1}xnn!ym+∑n≥0m≥0{nm}xnn!ym=y∑n≥0m≥0{nm}xnn!ym+y∂F∂y=yF+y∂F∂y∴∂F∂x=y(F+∂F∂y)\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ϕ(yex)F=e^{-y}\phi(ye^x)。取 x=0x=0，得到 ϕ(x)=ex\phi(x)=e^x。于是 F=ey(ex−1)F=e^{y(e^x-1)}。
沿用以上办法，我们得到四个异常重要的式子：
ez+wz=∑m,n≥0(nm)wmznn!ew(ez−1)=∑m,n≥0{nm}wmznn!1(1−z)w=∑m,n≥0[nm]wmznn!1−we(w−1)z−w=∑m,n≥0⟨nm⟩wmznn!\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)(2) (3)(3) 式导出之后的几乎所有内容。
为了引出之后的内容，首先考虑一个组合意义，以第二类斯特林数为例，第二类斯特林数 {mn}\left\{ {m \atop n} \right\} 表示将m个有序元素分成n个无序非空集合的方案数，考虑让 nn 个集合有序，对这个情况算两次处理。
考虑指数生成函数及其卷积的组合意义，构造 (ez−1)n(e^z-1)^n 表示 nn 个盒子，每个盒子可以放任意多个（非空）个元素的EGF，符合将 任意 mm 多个元素放进 nn 个盒子的情境。
同理，根据单个圆排列的方案数生成其指数生成函数再进行卷积，符合第一类斯特林数的对应情境。
于是有：
n!∑m≥0{mn}zmm!=(ez−1)nn!∑m≥0[mn]zmm!=(ln⁡11−z)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)(2) (3)(3) 式。
以 (3)(3) 为例，因为它更困难：
(1−z)−w=∑m,n≥0[nm]wmznn![wm](1−z)−w=∑n≥0[nm]znn!LHS=[wm]ewln⁡(11−z)=[wm]∑i≥0(wln⁡(11−z))ii!=(ln⁡11−z)mm!∴(ln⁡11−z)m=m!∑n≥0[nm]znn!\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*}
易如反掌。
接下来我们考虑那个屡见不鲜的式子：上升/下降幂和普通幂的转化式，用归纳法快速证明的背后，你是否也知晓它的由来，下面让我们接着提取 znz^n ，导出这两个式子。
以第二类斯特林数为例。
ew(ez−1)=∑m≥0n≥0{nm}wmznn![zn]ew(ez−1)=∑m≥0{nm}wmn!LHS=[zn]ewezew=1ew[zn]∑i≥0(wez)ii!=1ew[zn]∑i≥0wieizi!=1ew[zn]∑i≥0wii!∑j≥0(iz)jj!=1ew[zn]∑j≥0zjj!∑i≥0wii!ij=1ew1n!∑i≥0wii!in∴∑m≥0{nm}wmn!=1ew1n!∑i≥0wii!in(ew)(∑m≥0{nm}wm)=∑i≥0wii!in∑m≥0∑k≥0{nk}1(m−k)!wm=∑i≥0wii!in∑k≥0{nk}1(m−k)!=mnm!mn=∑k≥0{nk}mk‾\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! 这样我们就得到了这个经典的式子。
同理，我们也可以得到 mn‾=∑k≥0[nk]mkm^{\overline{n}} = \sum_{k \geq 0} \left[ \begin{matrix} n \\ k \end{matrix} \right] m^k。这样就完成了有关斯特林数的基本恒等式的证明。

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...