wiki - 算法小站

wiki 主题

主题名称

是否为父主题

是否为其添加wiki文章

选择主题

修改主题名称

修改父主题

修改wiki文章

算法基础搜索数据结构字符串数学图论动态规划计算几何杂项

数学

组合计数

二项式定理

生成函数（一）

FFT

多项式与形式幂级数

同余与模

同余与模的应用

同余与模的概念

特殊的数

斯特林数

斯特林数相关的恒等式

斯特林数的综合应用

[[ item.c ]]

斯特林数的综合应用

## 处理技巧：上升幂与下降幂
**下降幂的二项展开**
```math
\displaystyle
(x+m)^{\underline{r}} = \sum_{s} \binom{r}{s} x^{\underline{s}} m^{\underline{r-s}}
```
> 证明
实际上，根据**范德蒙卷积**
```math
\displaystyle
LHS = r! \binom{x+m}{r} =  r! \sum_{s} \binom{x}{s} \binom{m}{r-s} \\
\quad \\
= r! \sum_{s} \left( \frac{x^{\underline{s}}}{s!} \cdot \frac{m^{\underline{r-s}}}{(r-s)!} \right) = \sum_{s} \frac{r!}{s! (r-s)!} x^{\underline{s}} m^{\underline{r-s}}
```
证毕

## 带符号的第一类斯特林数
递推公式如下
```math
\displaystyle
{n \brack m} = {{n-1} \brack {m-1}} - (n-1) {{n-1} \brack m}
```
## 一些结论
### 补充恒等式 1
**恒等式 1，不常用，但可以了解一下**
```math
\displaystyle
{n \brack {n-m}} = \sum_{\lambda=0}^m { {m+\lambda} \brace {\lambda} } \binom{m-n}{m+\lambda} \binom{m+n}{m-\lambda}
```
> 论文由 Ludwig Schläfli 发表

无符号第一类斯特林数$${n \brack k}$$的生成函数，**上升幂**
```math
\displaystyle
x^{\overline{n}} = x(x+1)(x+2)\cdots(x+n-1) = \sum_{k=0}^n  { n \brack k } x^k
```
**Schläfli 的多项式**，给出了另一种生成函数形式
```math
\displaystyle
\prod_{j=0}^{n-1} (1 + j\epsilon) = \sum_{m=0}^{n} { {n} \brack {n-m}  } \epsilon^m
```
> 证明方法，在普通生成函数中，令$$x = \frac{1}{\epsilon}$$
```math
\displaystyle
(\frac{1}{\epsilon} ) (\frac{1}{\epsilon} + 1) (\frac{1}{\epsilon} + 2) \cdots (\frac{1}{\epsilon} + n-1 ) = \sum_{k=0}^n { n \brack k } (\frac{1}{\epsilon} )^k
```
然后将$$\epsilon^n$$拆分成$$n$$个$$\epsilon$$，乘到等式两边
```math
\displaystyle
\prod_{j=0}^{n-1} (1+j\epsilon) = \sum_{k=0}^n { n \brack k } \epsilon^{n-k}
```
换元之后，证毕

**2-关联斯特林数**，记为$$S_2(n, k)$$
考虑生成函数
```math
\displaystyle
\frac{(e^t - 1 - t)^\alpha}{\alpha!}
```
注意，这里多减去了一个$$t$$，而在 Taylor 展开中，$$e^t - 1 = t + \frac{t^2}{2!} + \dots$$
因为减去一个$$t$$之后，剩下的项从 $$\frac{t^2}{2!}$$ 开始，它对应的**组合意义**是
将集合划分成$$\alpha$$个子集，且**每个子集的大小至少是`2`**

构造生成函数
```math
\displaystyle
\frac{(e^t - 1 - t)^\alpha}{\alpha!} = S_2(2\alpha, \alpha)\dfrac{t^{2\alpha}}{(2\alpha)!} + S_2(2\alpha + 1, \alpha)\dfrac{t^{2\alpha + 1}}{(2\alpha + 1)!} \\
\quad \\
+ S_2(2\alpha+2, \alpha)\dfrac{t^{2\alpha + 2}}{(2\alpha + 2)!} + \cdots \\
\quad \\
= \sum_{n = 2\alpha}^{\infty} S_2(n, \alpha)\dfrac{t^n}{n!} 
```
> 考虑将 $$((e^t - 1) - t)^\alpha$$ 展开

```math
\displaystyle
= \sum_{\lambda=0}^\alpha \frac{(e^t - 1)^\lambda}{\lambda!} \cdot \frac{(-1)^{\alpha-\lambda} t^{\alpha-\lambda}}{(\alpha-\lambda)!}
```

> 引入第二类斯特林数

```math
\displaystyle
\frac{(e^t - 1)^\lambda}{\lambda!} = \sum_{k=\lambda}^\infty { k \brace \lambda } \frac{t^k}{k!} \Rightarrow
\quad \\
\quad \\
RHS = \sum_{\lambda=0}^\alpha \left( \sum_{k=\lambda}^\infty { k \brace \lambda } \frac{t^k}{k!} \right) \cdot \frac{(-1)^{\alpha-\lambda} t^{\alpha-\lambda}}{(\alpha-\lambda)!}
```

> 考虑提取$$t^{m+\alpha}$$的系数

现在只考虑项$$[t^{m+ \alpha}]$$，右边的总的指数$$t^{k + \alpha - \lambda}$$
令$$k + \alpha - \lambda = m + \alpha$$，即$$k = m + \lambda$$

```math
\displaystyle
[t^{m+\alpha}] = \sum_{\lambda = 0}^{\alpha} \dfrac{(-1)^{\alpha - \lambda}}{(m+\lambda)! (\alpha - \lambda)!} {{m+\lambda} \brace \lambda}
```

左边呢？左边也考虑$$\dfrac{S_2(m+\alpha, \alpha)}{(m+\alpha)!}t^{m+\alpha}$$

两边同时$$\times (m+\alpha)!$$，那么

```math
\displaystyle
\sum_{\lambda = 0}^{\alpha} (-1)^{\alpha - \lambda} \dfrac{(m+\alpha)!}{(m+\lambda)! (\alpha - \lambda)!} {{m+\lambda} \brace \lambda}
```
从而有关系
```math
\displaystyle
S_2(m+\alpha, \alpha) = \sum_{\lambda=0}^\alpha (-1)^{\alpha-\lambda} \binom{m+\alpha}{\alpha-\lambda} {  {m+\lambda} \brace {\lambda}  }
```

**关于2-关联斯特林数的递推**，求$$S_2(j, \alpha)$$的递推
```math
\displaystyle
G(\alpha) = \sum_{j} S_2(j, \alpha) \dfrac{t^j}{j!}
```
我们要证明
```math
\displaystyle
\dfrac{d}{dt} G(\alpha) = \alpha \cdot G(\alpha) + t \cdot G(\alpha-1)
```

> 证明如下
```math
\displaystyle
\dfrac{d}{dt}(G(\alpha)) = \dfrac{\alpha (e^t - 1 - t)^{\alpha - 1}}{\alpha !} \cdot (e^t - 1) \xrightarrow{e^t - 1 = e^t - 1 - t + t} \\
\quad \\
= \alpha \dfrac{ (e^t - 1 - t)^{\alpha}}{\alpha !} + t \dfrac{(e^t - 1 - t)^{\alpha - 1}}{(\alpha-1) !} = \alpha G(\alpha) + t G(\alpha - 1)
```

有递推关系
```math
\displaystyle
S_2(n, \alpha) = \alpha \cdot S_2(n-1, \alpha) + (n-1) S_2(n-2, \alpha-1)
```
> 证明
左边，因为$$\frac{d}{dt}$$，所以只考虑$$t^{n-1}$$这一项
```math
\displaystyle
[t^{n-1}] = s_2(n, a) \dfrac{t^{n-1}}{(n-1)!}
```
右边呢？右边同样考虑找$$[t^{n-1}]$$的项
先考虑第二项$$tG(\alpha - 1)$$，写成幂级数展开
```math
\displaystyle
t\sum_k S_2(k, \alpha - 1) = S_2(k, \alpha - 1) \dfrac{t^{k+1}}{k!}
```
令$$k+1 = n - 1$$，即$$k = n - 2$$，幂级数为$$s_2(n-2, \alpha-1)\dfrac{t^{n-1}}{(n-2)!}$$

> 为了统一起来，分子分母同时$$\times (n - 1)$$，$$(n-1)s_2(n-2, \alpha-1)\dfrac{t^{n-1}}{(n-1)!}$$
右边的第一项呢？第一项就简单了，$$\sum s_2(k, \alpha - 1) = \frac{t^k}{k!}$$，取$$k = n - 1$$

> 这样就可以导出递推关系式

**从差分的角度来看**，观察第一类斯特林数的递推，和$$S_2$$的递推
```math
\displaystyle
{ {n+1} \brack {n+1-m} } = n { {n+1} \brack {n-(m-1)} } + { {n} \brack {n-m} }
```
考虑差分 $$\Delta_n f(n) = f(n+1) - f(n)$$
```math
\displaystyle
\Delta_n {n \brack {n-m}} = n {n \brack {n - m + 1}}
```
观察**多项式的次数**
每增加一个$$n$$，会产生一个$$n \times$$`(更低阶的斯特林数)`
而关于$$S_2$$，每增加一个$$n$$，就会产生一个$$(n - 1) \times$$`(更低阶的 S2)`
二者在**差分意义**下，应该有相似的代数结构，类似
```math
\displaystyle
f_m(n) = C(m, n) \cdot S_2(m, n) \xRightarrow{\Delta} \\
f_m(n+1) - f_m(n) = nf(?) 
```
要有$$nf(?)$$的恒等形式，怎么办呢？

> 考虑二项恒等式$$n \binom{m-n}{m+a}$$
```math
\displaystyle
n\binom{m-n}{m+a} = -(m+a+1)\binom{m-n}{m+a+1} - a\binom{m-n}{m+a}
```
证明如下
```math
\displaystyle
= -(m+a+1) \dfrac{(m-n)^{\underline{m+a+1}}}{(m+a+1)!} - a \dfrac{(m-n)^{\underline{m+a}}}{(m+a)!} \\
\quad \\
= -\dfrac{(m-n)^{\underline{m+a+1}}}{(m+a)!} - a \dfrac{(m-n)^{\underline{m+a}}}{(m+a)!} \\
\quad \\
= -\dfrac{(m-n)^{\underline{m+a}}}{(m+a)!} (m-n-m-a + a) = n \binom{m-n}{m+a}
```

**一个技巧性比较强的构造**
构造
```math
\displaystyle
f_m(n) = \sum_{a = 0}^{m} \binom{m-n}{m+a} S_2(m+a, a)
```
根据$$\binom{m+1-n}{m+1+a} - \binom{m-n}{m+a+1} = \binom{m-n}{m+a}$$
计算差分
```math
\displaystyle
\Delta f = f_{m+1}(n) - f_{m+1}(n+1) = \sum_{\alpha=0}^{m+1} \binom{m-n}{m+\alpha} S_2(m+\alpha+1, \alpha) 
```

接下来**处理处理权重项**$$nf_m(n)$$，应用上面讨论的关于$$n \binom{m-n}{m+a}$$恒等式
并且对右边第一项作平移，令$$\alpha \leftarrow \alpha - 1$$
```math
\displaystyle
nf_m(n) =  \sum_{\alpha=1}^{m+1} (m+\alpha) \binom{m-n}{m+\alpha} S_2(m+\alpha-1, \alpha-1) \\
- \sum_{\alpha=0}^{m} \alpha \binom{m-n}{m+\alpha} S_2(m+\alpha, \alpha)
```

考虑
```math
\displaystyle
f_{m+1}(n) - f_{m+1}(n+1) + nf_m(n) \\
\quad \\
= \sum_a \binom{m-n}{m+a} ( S_2(m+a+1, a) - (m+a)S_2(m+a-1, a-1) - aS_2(m+a, a) )
```
注意到之前分析的
```math
\displaystyle
S_2(m+a+1, a) - aS_2(m+a, a) = (m+a)S_2(m+a-1, a-1)
```
从而有
```math
\displaystyle
f_{m+1}(n+1) = nf_m(n) + f_{m+1}(n)
```
**这很像第一类斯特林数的递推公式**，那看一下到底是不是呢

令$$f\_m(n) = {n \brack m}, f\_{m+1}(n+1) = {{n+1} \brack {n-m}}, nf\_{m}(n) = n{{n} \brack {n-m}}, f\_{m+1}(n) = {n \brack {n-m-1}}$$

很显然是符合$${{n+1} \brack {n-m}} = n{n \brack {n-m}} + {n \brack {n-m-1}}$$，符合第一类斯特林数的定义

> 这样的话，我们有两个重要的公式

```math
\displaystyle

S_2(m+\alpha, \alpha) = \sum_{\lambda=0}^\alpha (-1)^{\alpha-\lambda} \binom{m+\alpha}{\alpha-\lambda} {  {m+\lambda} \brace {\lambda}  } \\
\quad \\
{n \brack {n-m}} = \sum_{\alpha=0}^m \binom{m-n}{m+\alpha} S_2(m+\alpha, \alpha)
```

> 将公式 (1) 代入公式 (2)，我们有

```math
\displaystyle
{n \brack {n-m}} = \sum_{a = 0}^{m} \binom{m-n}{m+a} \left( \sum_{\lambda = 0}^{a} (-1)^{a - \lambda} \binom{m+a}{a - \lambda} {{m+\lambda} \brace \lambda}\right)
```
交换求和顺序
```math
\displaystyle
\sum_{\lambda = 0}^{m} {{m+\lambda} \brace \lambda} \left( \sum_{a = 0}^m (-1)^{a - \lambda} \binom{m-n}{m+a}\binom{m+a}{a - \lambda}   \right)
```
其中$$\binom{m+a}{a - \lambda} = \binom{m+a}{m + \lambda}$$

令$$S = \sum\_{a = 0}^m (-1)^{a - \lambda} \binom{m-n}{m+a}\binom{m+a}{m + \lambda} $$

利用组合数恒等式$$\binom{r}{m}\binom{m}{k} = \binom{r}{k}\binom{r-k}{m-k}$$

```math
\displaystyle
\binom{m-n}{m+a} \binom{m+a}{m+\lambda} = \binom{m-n}{m+\lambda} \binom{m-n-m-\lambda}{m+a -m-\lambda} \\
= \binom{m-n}{m+\lambda} \binom{-n-\lambda}{a - \lambda}
```
从而
```math
\displaystyle
S = \binom{m-n}{m+ \lambda} \sum_{a = \lambda}^m (-1)^{a - \lambda} \binom{-n-\lambda}{a - \lambda}
```
根据$$\sum_k (-1)^k \binom{-r}{k} = \binom{r+n}{n}$$，其中$$n$$是$$k$$的上界

在这个问题中，$$k = a- \lambda \in [0, m - \lambda]$$，而$$r = n+\lambda$$

最后的结果应该是$$\displaystyle S = \binom{m+n}{m -\lambda} \binom{m-n}{m +\lambda}$$

> 这也就证明了一开始的恒等式
```math
\displaystyle
{n \brack {n-m}} = \sum_{\lambda=0}^m { {m+\lambda} \brace {\lambda} } \binom{m-n}{m+\lambda} \binom{m+n}{m-\lambda}
```

### 补充恒等式 2
**比较有用，最好掌握**
```math
\displaystyle
{n \brace {l+m}} \binom{l+m}{l} = \sum_k \binom{n}{k} {k \brace l} {{n-k} \brace m}
```

> 代数证明，**指数生成函数**
```math
\displaystyle
\sum_{n \geqslant 0} {n \brace {l+m}} \dfrac{x^n}{n!} = \dfrac{(e^x - 1)^{l+m}}{(l+m)!}
```
将方程两边同时$$\times \frac{(l+m)!}{l!m!}$$
```math
\displaystyle
\sum_{n \geqslant 0} {n \brace {l+m}} \binom{l+m}{m} \dfrac{x^n}{n!} = \dfrac{(e^x - 1)^{l+m}}{l!m!} = \dfrac{(e^x - 1)^l}{l!} \dfrac{(e^x - 1)^m}{m!}
```
比较系数，右边也是两个斯特林多项式相乘，写成卷积的形式，第一个多项式取$$k$$为幂，第二个取$$n - k$$为幂
这样考虑方程两边取$$[x^n]$$
```math
\displaystyle
[x^n] = \sum_{k = 0}^{n} \binom{n}{k} {k \brace l} {{n-k} \brace m}
```
实际上，右边等于$$\sum_k {{n-k} \brace m}\frac{x^{n-k}}{(n-k)!} \cdot {k \brace l} \frac{x^k}{k!}$$，而两边要得到$$[x^n]$$怎么办？
方程两边同时$$\times n!$$
左边$$[x^n] = {n \brace {l+m}} \binom{l+m}{m}$$，右边多出来的系数恰好是$$\frac{n!}{k! (n-k)!} = \binom{n}{k}$$

> 组合证明，**组合意义也很典型**
相当于将$$n$$个元素放入$$l+m$$个无区别的盒子中，但是$$l+m$$个盒子预先被染成了`2`种颜色
其中$$l$$个盒子是红色，$$m$$个是蓝色

> 左边式子，**先分组再染色**
第一步，先分组，方案数是$${{n} \brace {l+m}}$$

> 第二步，染色，方案数是$$\binom{l+m}{m}$$

> 右边的式子呢？**先确定元素，再分组**
第一步，选出元素，选$$k$$个放入红色盒子，$$\binom{n}{k}$$

> 第二步，将$$k$$个元素正式放入$$l$$个红色盒子中，方案数$${k \brace l}$$

> 第三步，将剩下的$$n-k$$个元素，正式放入$$m$$个蓝色盒子中，方案数$${{n-k} \brace m}$$

### 补充恒等式 3
对于第一类斯特林数，同样也有类似
```math
\displaystyle
{n \brack {l+m}} \binom{l+m}{l} = \sum_{k} {k \brack l} {{n-k} \brack m} \binom{n}{k}
```

> 代数证明，完全类似
```math
\displaystyle
\sum_{n \geqslant 0} {n \brack r} \dfrac{x^n}{n!} = \dfrac{(-\ln(1-x))^r}{r!}
```
从而有
```math
\displaystyle
\sum_{n \geqslant 0} {n \brack {l+m}} \binom{l+m}{l} \dfrac{x^n}{n!} = \binom{l+m}{l} \dfrac{(-\ln(1-x))^{l+m}}{(l+m)!} = \binom{l+m}{l} \dfrac{(-\ln(1-x))^l}{l!} \dfrac{(-\ln(1-x))^m}{m!}
```
按照 EGF 的卷积法则，按$$\frac{x^n}{n!}$$系数比较
```math
\displaystyle
{n \brack {l+m}} \binom{l+m}{l} = \sum_{k} \binom{n}{k} {k \brack l} {{n-k} \brack m}
```

> 组合证明，异曲同工
将$$n$$个有区别的元素，划分成$$l+m$$个圆排列，并且将轮换染色成两种颜色，$$l$$个红色轮换，$$m$$个蓝色轮换
求方案数

## 斯特林数与自然数幂和
**自然数幂和**的通项公式如下
```math
\displaystyle
\sum_{k = 0}^{n} k^p = \sum_{j = 0}^{p} j! {p \brace j} \binom{n+1}{j+1}
```
> 证明过程并不难
```math
\displaystyle
k^p = \sum_{j=0}^{p} {p \brace j} k^{\underline{j}} = \sum_{j = 0}^{p} j! {p \brace j} \binom{k}{j}
```
代入求和公式，并且交换求和符号
```math
\displaystyle
\sum_{k=0}^{n} k^p = \sum_{k=0}^{n} \sum_{j=0}^{p} j! {p \brace j} \binom{k}{j} \\
\quad \\
\sum_{j = 0}^p j! {p \brace j} \sum_{k = 0}^{n} \binom{k}{j}
```

> 根据上指标求和，$$\sum\_{k = 0}^{n} \binom{k}{j} = \binom{n+1}{j+1}$$
从而有
```math
\sum_{k = 0}^{n} k^p = \sum_{j = 0}^{p} j! {p \brace j} \binom{n+1}{j+1}
```

这样，对于$$n$$很大，但是$$p$$很小的情况，就可以$$O(p)$$的时间复杂度求解了

看完文章有啥想法

算法小站

wiki 主题

数学

斯特林数的综合应用

目录