关于第二类斯特林数通项公式的生成函数推导以及一些拓展应用
spire001
·
·
算法·理论
关于第二类斯特林数通项公式的生成函数推导以及一些拓展应用
引入
第二类斯特林数 S_{n,k} 表示 n 元集合的 k 划分数。
其递推式为：
S_{n,k}=S_{n - 1, k - 1} + kS_{n - 1, k}
其通项公式为：
S_{n, k} = \sum_{i=0}^{k}\frac{(-1)^i(k-i)^n}{i!(k-i)!}
边界为 S_{0, 0} = 1,S_{0,i}=0,i\in \mathbb N^*。
但貌似没有封闭形式。
容斥原理的推导较为难以理解，下以生成函数的方法推导之。
有两种推导方向，第一种是记
f_n(x)=\sum_{i=0}^\infty S_{n,i}x^i
第二种是记
f_k(x)=\sum_{i=0}^\infty S_{i,k}x^i
我们分别给出推导。
最后我们给出一些与推导过程无关的拓展，其耐人寻味且难度不高易于理解。
约定
-
-
推导方向 1
记
f_n(x)=\sum_{i=0}^\infty S_{n,i}x^i
则有：
f_n(x) = xf_{n- 1}(x) + xf_{n - 1}'(x)
这个如果看不明白可以去看看生成函数的教学。
令 e^xf_n(x) = g_n(x)\Leftrightarrow f_n(x)=e^{-x}g(x)，则有：
e^xf_n(x) = e^xxf_{n- 1}(x) + e^xxf_{n - 1}'(x)=x(e^xf_{n - 1}(x)+e^xf_{n - 1}'(x))=x(e^xf_{n - 1}(x))'
即：
g_n(x)=xg_{n - 1}'(x)
设 g_n(x)=\sum\limits_{i = 0}^\infty g_{n,i}x^i。那么 g_0(x)=e^x,g_{0,i}=\frac{1}{i!}。
则有：
g_{n,i}=ig_{n-1,i}\Rightarrow g_{n,i}=\frac{i^n}{i!}
所以：
g_n(x)=\sum_{i = 0}^\infty \frac{i^n}{i!}x^i
那么：
S_{n,k}=[x^k]f_n(x)=[x^k](e^{-x}g(x))=[x^k]\sum_{i=0}^\infty\frac{(-1)^i}{i!}\sum_{i=0}^\infty\frac{i^n}{i!}x^i=\sum_{i=0}^{k}\frac{(-1)^i(k-i)^n}{i!(k-i)!}
证毕。
推导方向 2
记
f_k(x)=\sum_{i=0}^\infty S_{i,k}x^i
由：
S_{k,n}=kS_{k, n - 1}+S_{k-1,n-1}
则有：
f_k(x)=xf_{k - 1}(x)+kxf_{k}(x)\Rightarrow f_k(x)=\frac{xf_{k-1}(x)}{1-kx}
容易得到：
$$
f_k(x)=\frac{x^k}{\prod\limits_{i=1}^k(1-ix)}
$$
我们令：
$$
\frac{x^k}{\prod\limits_{i=1}^k(1-ix)}=\sum_{i=1}^k \frac{A_i x^k}{1-ix}
$$
对于 $i\in[1,k]\cap \mathbb Z$，左右两式子同乘 $1-ix$，然后令 $x = \frac{1}{i}$。
则有：
$$
A_i=\frac{1}{(1-\frac{1}{i})(1-\frac{2}{i})\cdots(1-\frac{i-1}{i})\times(1-\frac{i+1}{i})(1-\frac{i+2}{i})\cdots(1-\frac{k}{i})}=\frac{1}{\frac{(i-1)!(k-i)!(-1)^{k-i}}{i^{k-1}}}=\frac{i^k(-1)^{k-i}}{i!(k-i)!}
$$
则：
$$
S_{k,n}=[x^n]f_k(x)=[x^n]\sum_{i=1}^k \frac{A_i x^k}{1-ix}=\sum_{i=1}^k [x^{n-k}]\frac{A_i}{1-ix}=\sum_{i=1}^k i^{n-k}\frac{i^k(-1)^{k-i}}{i!(k-i)!}=\sum_{i=1}^k\frac{i^n(-1)^{k-i}}{i!(k-i)!}
$$
小心 $k=n=0$ 的特殊情况。
证毕。
### 拓展 1
证明：
$$
x^n=\sum_{k=1}^nS_{n,k}x^{\underline{k}}
$$
其中：
$$
x^{\underline k}=x(x-1)(x-2)\cdots(x-k+1)
$$
考虑组合意义：
先考虑 $x\in\mathbb Z$ 。
有 $x$ 个箱子，$n$ 个球，考虑将所有球放入箱子的方案数。
一方面，就是 $x^n$。
另一方面，第一步枚举要将 $n$ 个球放入 $k$ 个箱子，即右式 $\sum_{i=1}^k$，第二步将 $n$ 个球分成 $k$ 部分，即右式 $S_{n,k}$，第三步在 $x$ 个箱子中选择 $k$ 个箱子放入，即 $A_x^k=x^{\underline k}$。
故左右相等，我们证明了在 $x\in\mathbb Z$ 时，左右式相等。
而有一个定理：
$$
\text{对于两个 k}\text{ 次函数 f(x) 与 g(x), 若存在 k + 1 个 不同的 u 使得 f(u) = g(u), 那么 f(x) = g(x)}
$$
这个定理可以用 拉格朗日插值 的唯一性说明。
对于左右两式，取 $u=1,2,3,\dots,n+1$，显然成立，于是我们证明了在 $x\in \mathbb R$ 时命题成立。
### 拓展 2
以后再写。。。