wiki - 算法小站

wiki 主题

主题名称

是否为父主题

是否为其添加wiki文章

选择主题

修改主题名称

修改父主题

修改wiki文章

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

数学

组合计数

二项式定理

生成函数（一）

FFT

多项式与形式幂级数

同余与模

同余与模的应用

同余与模的概念

特殊的数

斯特林数

斯特林数相关的恒等式

斯特林数的综合应用

[[ item.c ]]

斯特林数相关的处理方法

主要介绍了斯特林数的恒等式，生成函数，处理技巧等等
## 斯特林数的恒等式
### 处理技巧：差分
**牛顿级数**是和差分有关
任何多项式$$f(x)$$展开为下降阶乘幂基底时的系数由前向差分$$\Delta$$决定
```math
\displaystyle
f(x) = \sum_m \frac{\Delta^m f(0)}{m!} x^{\underline{m}}
```

### 处理技巧：反演
**处理技巧 1**
记$$a_k, b_n$$，那么$$\times e^{-z}$$对应在**EGF**空间上，对下标做带**交替符号**的二项变换
```math
\displaystyle
A(z) = \sum_{k \geqslant 0} a_k \dfrac{z^k}{k!}, \quad b_n = \sum_{k}\binom{n}{k} (-1)^{n-k}a_k
```
那么有
```math
\displaystyle
B(z) = \sum_{n \geqslant 0}b_n \dfrac{z^n}{n!} = e^{-z}A(z)
```
**恒等式 1**
```math
\displaystyle
{n \brace m} = \sum_{k} \binom{n}{k} {{k+1} \brace {m+1}} (-1)^{n-k}
```
> 代数证明
定义
```math
\displaystyle
A(z) = \sum_{k \geqslant 0} {{k+1} \brace {m+1}} \dfrac{z^k}{k!} = \sum_{n \geqslant 1} {n \brace {m+1}} \dfrac{z^{n-1}}{(n-1)!}
```
构造$$E(z) = \sum\_{n \geqslant 0} {n \brace {m+1}}\dfrac{z^n}{n!} = \dfrac{(e^z - 1)^{m+1}}{(m+1)!}$$

> 那么
```math
\displaystyle
A(z) = E'(z) = \dfrac{e^z (e^z - 1)^m}{m!} \\
\quad \\
B(z) = e^{-z}A(z) = \dfrac{(e^z - 1)^m}{m!} = \sum_{n} {n \brace m} \dfrac{z^n}{n!}
```
根据$$\times e^{-z}$$**EGF**变换，实际上是交替符号的二项变换
```math
\displaystyle
{n \brace m} = \sum_{k} \binom{n}{k} (-1)^{n-k} {{k+1} \brace m+1}
```

**处理技巧 2，二项反演**
```math
\displaystyle
f(n) = \sum_{k = 0}^{n} \binom{n}{k}g(k) \Longleftrightarrow g(n) = \sum_{k = 0}^{n} (-1)^{n-k} \binom{n}{k}f(k)
```
> 证明如下，组合恒等式$$\binom{n}{k}\binom{k}{j} = \binom{n}{j}\binom{n-j}{k-j}$$
上面的式子
```math
\displaystyle
RHS = \sum_{k = 0}^{n} \binom{n}{k} (-1)^{n-k} \left( \sum_{j = 0}^{k} \binom{k}{j}g(j) \right) \\
\quad \\
= \sum_{j = 0}^{n}g(j) \sum_{k = 0}^{n} (-1)^{n-k} \binom{n}{k}\binom{k}{j} =  \sum_{j = 0}^{n}g(j) \binom{n}{j} \sum_{k = j}^{n} (-1)^{n-k} \binom{n-j}{k-j} 
```
令$$i = k - j$$
```math
\displaystyle
RHS = \sum_{j = 0}^{n}g(j) \binom{n}{j} \sum_{i = 0}^{n-j}(-1)^{n-i-j} \binom{n-i}{j}
```
注意到$$\sum\_{i = 0}^{n - j}$$这一项求和，实际上是$$(1-1)^{n - j}$$的二项展开
这一项只有在$$n = j$$时候，值为`1`，其他情况均为$$0$$
```math
RHS = \sum_{j = 0}^{n} g(j) \binom{n}{j} [j = n] = g(n) \binom{n}{n} = g(n)
```

> 证明二，**EGF**视角
考虑两个$$G(x), H(x)$$，他们是关于$$g_i, h_i$$的 **EGF**，对他们做卷积，不难发现
```math
\displaystyle
G(x)H(x) = \sum_{n = 0}^{\infty} \left(\sum_{k = 0}^{n} \dfrac{g(k)}{k!} \dfrac{h(n-k)}{(n-k)!}  \right) x^n \\
\quad \\
= \sum_{n=0}^{\infty} \sum_{k = 0}^{n} \binom{n}{k} g(k)h(n-k) \dfrac{x^n}{n!}
```
**二项式卷积定理**
如果$$f(n)$$是$$g, h$$的二项式卷积，那么$$f$$的 **EGF** 就是 $$g, h$$对应的 **EGF**的乘积

> 回到原来的问题，如果我们定义$$i(n) = 1$$的话
```math
\displaystyle
f(n) = \sum_{k = 0}^{n} \binom{n}{k} g(k) 1^{n-k} = \sum_{k = 0}^{n} \binom{n}{k} g(k) i(n-k) 
```
那么$$i(n)$$的 **EGF** 对应是
```math
\displaystyle
I(x) = \sum_{n = 0}^{\infty} 1 \cdot \dfrac{x^n}{n!} = 1 + x + \dfrac{x^2}{2!} + \cdots = e^x
```
从而有，对$$f, i, g$$求 **EGF**
```math
\displaystyle
\displaystyle
F(x) = G(x)I(x) = G(x)\cdot e^x \\
G(x) = e^{-x} \cdot F(x)
```
而$$e^{-x}$$对应的项恰好是$$(-1)^n \dfrac{x^n}{n!}$$，也就是说$$i'(n) = (-1)^{n}$$
从而
```math
\displaystyle
g(n) = \sum_{k = 0}^{n} \binom{n}{k} f(k) (-1)^{n-k}
```

### 二项反演与错排
记$$D_n$$为$$n$$个元素错排的方案数，枚举恰有$$k$$个不动点，剩下的$$n - k$$个全错排
```math
\displaystyle
n! = \sum_{k = 0}^{n} \binom{n}{k} D_{n-k} = \sum_{j = 0}^{n} \binom{n}{j}D_j \\
\quad \\
D(n) = \sum_{k = 0}^{n} (-1)^{n-k} \binom{n}{k} k! \\
\quad \\
D(n) = n!\sum_{i = 0}^{n} \dfrac{(-1)^i}{i!}
```

同样由**二项反演**
之前已经推导的公式
```math
\displaystyle
{{n+1} \brace {m+1}} = \sum_{k} \binom{n}{k} {k \brace m} \\
\quad \\
{{n+1} \brack {m+1}} = \sum_{k} {n \brack k} \binom{k}{m} \\
```
经过二项反演
```math
\displaystyle
{n \brace m} = \sum_{k} \binom{n}{k} {{k+1} \brace {m+1}} (-1)^{n-k} \\
\quad \\
{n \brack m} = \sum_{k} {{n+1} \brack {k+1}} \binom{k}{m}  (-1)^{m-k}
```

## 附加的斯特林数恒等式
**恒等式 1**
```math
\displaystyle
{{n+1} \brace {m+1}} = \sum_{k = 0}^{n} {k \brace m} (m+1)^{n - k}
```
> 组合意义
某种放置方案中，一定存在标号是$$k+1$$的球，它是**最后一个开辟新盒子**的球
前$$k$$个球的状态，对应$$\displaystyle {k \brace m}$$

> 第$$k+1$$个球呢，没得选，只能放到新开辟的盒子中
还剩下$$n - k$$个球，即编号$$[k+2, n+1]$$，每个球对应$$m+1$$种选择，方案数$$(m+1)^{n - k}$$

> 暴力递推
记忆$$\displaystyle T_t = {{t+1} \brace {m+1}}$$，根据斯特林数的递推
```math
\displaystyle
{{t+1} \brace {m+1}} = (m+1) {t \brace {m+1}} + {t \brace m} \\
\quad \\
T_t = (m+1)T_{t-1} + {t \brace m} \\
\quad \\
= (m+1)^2T_{t-2} + (m+1){{t-1} \brace m} + {t \brace m} = \\
\cdots \quad \\
= (m+1)^kT_{t-k} + \sum_{j = 0}^{t} (m+1)^{t-j} {j \brace m}
```
换元之后
```math
\displaystyle
T_n = (m+1)^{n-k} T_k + \sum_{j = 0}^{n} (m+1)^{n-j} {j \brace m}
```
令$$k = 0$$，那么$$T_0 = {1 \brace {m+1}} = 0$$除非$$m = 0$$（$$m = 0$$情况可以手动验证成立）

> 那么$$T\_n = \displaystyle {{n+1} \brace {m+1}} = \sum\_{j = 0}^{n} (m+1)^{n-j} {j \brace m}$$

**恒等式 2**
```math
\displaystyle
{{n+1} \brack {m+1}} = \sum_{k = 0}^{n} {k \brack m} n^{\underline{n-k}} = n! \sum_{k = 0}^{n}  \dfrac{ {k \brack m} }{k!}
```
> 证明也类似，暴力递推，令
```math
\displaystyle
T_{n+1} = {{n+1} \brack {m+1}} \\
\quad \\
T_{n+1} = nT_n + {n \brack m} = \cdots \\
\quad \\
= n(n-1)(n-2) T_{n-2} + n(n-1) {{n-2} \brack m} + n{{n-1} \brack m} + {n \brack m} \\
\cdots \\
(n^{\underline{k+1}} \cdot T_{n-k}) + \sum_{j = 0}^{k} n^{\underline{j}} {{n-j} \brack m}
```
其中第一项为`0`，然后令$$n - j = k$$即证毕

> 组合意义
从$$n$$个元素，挑出$$k$$个，**不和**最后一个元素`n+1`在同一个圈，方案数$$\displaystyle\binom{n}{k}$$

> 那么，这$$k$$个元素，划分成$$m$$个圆排列的方案数是$$\displaystyle {k \brack m}$$
剩下的$$n - k$$个元素呢？必须和$$n+1$$在同一个圆排列中，一个大小为$$|T|$$的圆排列
方案数是$$(|T|-1)! \quad |T| = n - k+1$$，所以方案数是$$(n - k)!$$
总的方案数是
```math
\displaystyle
\binom{n}{k} {k \brack m} (n - k)!
```

**恒等式 3**
```math
\displaystyle
{{m+n+1} \brace m} = \sum_{k = 0}^{m} k {{n+k} \brace k}
```
> 证明，依然是迭代的
```math
\displaystyle
{{m+n+1} \brace m} = m {{m+n} \brace m} + {{m+n} \brace {m-1}} = \\
\quad \\
\cdots 
= m {{m+n} \brace m} + (m-1){{m+n-1} \brace {m-1}} + (m-2){{m+n-2} \brace {m-2}} + {{m+n-2} \brace {m-3}} \\
\quad \\
= \sum_{j = 0}^{m} (m - j) {{m+n-j} \brace {m-j}}
```
令$$k = m - j$$，即可证毕

**恒等式 4**
```math
\displaystyle
{{m+n+1} \brack m} = \sum_{k = 0}^{m} (n+k) {{n+k} \brack k}
```
> 证明，类似的迭代
```math
\displaystyle
{{m+n+1} \brack m} = (m+n) {{m+n} \brack m} + {{m+n} \brack {m-1}} \\
\quad \\
= \sum_{k = 0}^{m} (n + k) {{n+k} \brack k}
```

## 斯特林反演
### 斯特林反演及其证明
```math
\displaystyle
\begin{aligned}
x^n = \sum_{k} {n \brace k} x^{\underline{k}} &\quad \textbf{(1)} \\
x^{\overline{n}} = \sum_{k} {n \brack k} x^k &\quad \textbf{(2)}  \\
x^n = \sum_{k} {n \brace k} (-1)^{n-k} x^{\overline{k}} &\quad \textbf{(3)} \\
x^{\underline{n}} = \sum_{k} {n \brack k} (-1)^{n-k} x^k &\quad \textbf{(4)}
\end{aligned}
```
将`(2) --> (3)`

```math
\displaystyle
x^n = \sum_{k} {n \brace k} (-1)^{n-k} \sum_m {k \brack m} x^m = \sum_k \sum_m {n \brace k}{k \brack m} (-1)^{n-k}x^m
```
两边系数相等，所以只有
```math
\displaystyle
\sum_k {n \brace k} {k \brack m} (-1)^{n - k} = [m = n], \quad m, n \geqslant 0
```
**斯特林反演定理**
```math
\displaystyle
f(n) = \sum_{k = 0}^{n} {n \brace k} g(k) \Longleftrightarrow \\
\quad \\
g(n) = \sum_{k = 0}^{n} (-1)^{n-k} {n \brack k} f(k)
```
> 证明，假设已知
```math
\displaystyle
f(n) = \sum_{k = 0}^{n} {n \brace k} g(k)
```
那么我们有
```math
\displaystyle
RHS = \sum_{k=0}^{n} (-1)^{n-k} {n \brack k} f(k)
```
将$$f(k) =  \sum\_{j = 0}^{k} {k \brace j} g(j)$$代入
```math
\displaystyle
RHS = \sum_{k = 0}^{n} (-1)^{n-k} {n \brack k} \left( \sum_{j = 0}^{k} {k \brace j} g(j) \right) \\
\quad \\
= \sum_{j = 0}^{n} g(j) \sum_{k = j}^{n} (-1)^{n-k} {n \brack k}{k \brace j}
```
注意到$$ \sum\_{k = j}^{n} (-1)^{n-k} {n \brack k}{k \brace j} = \bm{i}$$是**对角阵**

> 从而有$$RHS = \sum\_{j = 0}^{n}g(j) \bm{i} = g(n)$$

### 相关的恒等式
**恒等式 3**
```math
\displaystyle
\binom{n}{m} = \sum_k {{n+1} \brace {k+1}} {k \brack m} (-1)^{m-k}
```

> **处理技巧，斯特林数基底**
```math
\displaystyle
x^{n+1} = \sum_j {{n+1} \brace j} x^{\underline{j}} \Rightarrow \\
```
两边同时$$/x$$，可以得到
```math
\displaystyle
x^n = \sum_{j = 0}^{n+1} {{n+1} \brace j} (x-1)^{\underline{j-1}} \\
\quad \\
x^n = \sum_{k = 0}^{n} {{n+1} \brace {k+1}} (x-1)^{\underline{k}}
```
将下降阶乘幂展开为普通幂
```math
\displaystyle
(x-1)^{\underline{k}} = \sum_m {k \brack m} (-1)^{k-m} (x - 1)^m \\
\quad \\
x^n = \sum_{k = 0}^{n} {{n+1} \brace {k+1}} \left( \sum_m {k \brack m} (-1)^{k-m} (x - 1)^m \right) \\
\quad \\
((x-1) + 1)^n = \sum_m \left(  \sum_{k = 0}^{n} {{n+1} \brace {k+1}} {k \brack m} (-1)^{k-m}  \right) (x - 1)^m 
```
比较系数可以知道
```math
\displaystyle
\binom{n}{m} = \sum_{k = 0}^{n} {{n+1} \brace {k+1}} {k \brack m} (-1)^{k-m} 
```

**恒等式 4**
```math
\displaystyle
n^{\underline{n-m}} [n \geqslant m] = \sum_k {{n+1} \brack {k+1}} {k \brace m} (-1)^{m-k}
```
> 证明要用到以下重要的关系
1）记$$s(n, k)$$是有符号的第一类斯特林数，那么$$s(n, k) = (-1)^{n-k} {n \brace k}$$
2）有符号的第一类斯特林数，满足递推$$s(n+1, j) = s(n, j-1) - ns(n, j)$$

> 3）$$\sum\_i s(n, i) {i \brace m} = \delta\_{n, m}$$，其中$$\delta\_{n, m} = [n = m]$$

> 利用第一类斯特林数的**基底关系**
```math
\displaystyle
x^{\overline{n+1}} = \sum_k {{n+1} \brack k} x^k
```
两边都$$/x$$，可以得到
```math
\displaystyle
(x+1)^{\overline{n}} = \sum_k {{n+1} \brack {k+1}} x^k
```
利用第二类斯特林数，将$$x^k$$展开成下降幂
```math
\displaystyle
(x+1)^{\overline{n}} = \sum_k {{n+1} \brack {k+1}} \left( \sum_m {k \brace m}x^{\underline{m}} \right)
```
交换求和顺序，不难发现
```math
\displaystyle
(x+1)^{\overline{n}} = \sum_m x^{\underline{m}} \left( \sum_k {{n+1} \brack {k+1}} {k \brace m} \right)
```
而我们已知$$\sum_k {n \brace k}{k \brack m} (-1)^{n-k} = [n = m]$$，想办法对`RHS`做**符号反转**
实际上，原问题很难求的时候，往往可以考虑作符号反转
```math
\displaystyle
\text{RHS} = \sum_k {{n+1} \brack {k+1}} {k \brace m} (-1)^{m-k} = \sum_k (-1)^{n-k} s(n+1, k+1) {k \brace m} (-1)^{m-k} \\
\quad \\
= (-1)^{n+m} \sum_k s(n+1, k+1) {k \brace m}
```
接下来，令 $$j = k+1$$
```math
\displaystyle
A(n) = \sum_{j \geqslant 1} s(n+1, j) {{j-1} \brace m} \\
RHS = (-1)^{n+m} A(n)
```
下面考虑怎么求$$A(n)$$，根据**有符号第一类斯特林数的递推式**
```math
\displaystyle
A(n) = \sum_j s(n, j-1) {{j-1} \brace m} - n\sum_j s(n, j) {{j-1} \brace m} \\
\quad \\
= \sum_i s(n, i) {i \brace m} - n\sum_j s(n, j) {{j-1} \brace m} = \delta_{n, m} - nA(n-1)
```
考虑$$A(m)$$，即$$n = m$$时，根据$$s(m+1, j)$$，可知$$1 \leqslant j \leqslant m+1$$
同时$${{j-1} \brace m}$$蕴含$$j - 1\geqslant m$$，所以$$j = m+1$$
所以$$A(m)$$只有一项$$j = m+1$$，即$$A(m) = 1$$

> 对于$$n > m$$，那么$$\delta\_{n, m} = 0, \quad A(n) = -nA(n-1)$$
```math
\displaystyle
A_n = -nA_{n-1} = \cdots \\
= (-1)^3 n(n-1)(n-2) A_{n-3} \\
\cdots \\
= (-1)^m n(n-1)\cdots (n-m+1)A_{n-m} \xrightarrow {n - m = m'} \\
= (-1)^{n-m'} n(n-1)\cdots (m'+1) A_{m'} \xrightarrow{m = m'} \\
\quad \\
= (-1)^{n-m} n^{\underline{n-m}}
```
这恰好等于左边，这样就完成了证明

## 工具：留数定理和Cauchy积分
若解析函数$$f(z)$$在$$a$$点有$$m$$阶极点，即$$\lim\_{x \to a} f(z) = \infty$$，则在此极点附近$$f(z)$$
具有以下形式的洛朗级数
```math
\displaystyle
f(z) = \dfrac{c_0}{(z-a)^{m}} + \dfrac{c_1}{(z-a)^{m-1}} + \cdots + \dfrac{c_{m-1}}{(z-a)} + c_m + c_{m+1}(z - a) + \cdots
```
那么$$\dfrac{1}{(z-a)}$$的系数$$c\_{m-1}$$称为$$f(z)$$在$$a$$点的留数
算法竞赛中，$$a$$一般取`0`，通常需要考虑$$1/z$$项的系数

**Cauchy 积分公式**
```math
\displaystyle
a_n = [z^n]A(z) = \dfrac{1}{2\pi i} \oint \dfrac{A(z)}{z^{n+1}}dz
```
在组合数学中，常常用$$\text{Res}\_{z = 0} \left[ \dfrac{A(z)}{z^{n+1}} \right]$$来表示$$A(z)$$中$$[z^n]$$的系数

**斯特林数常用的代换**
单值解析代换，令$$z = 1 - e^{-t}$$，那么有$$t = -\ln (1-z)$$
这样两种生成函数的形式可以统一起来

## 拉格朗日反演
**已知函数$$f(w)$$的幂级数，如何求其反函数$$w = f^{-1}(z)$$的幂级数的系数，不妨设$$g = f^{-1}$$**

设$$f(w)$$是一个形式幂级数，满足$$f(0) = 0, f'(0) \neq 0$$（需要原点附近可逆）
如果我们定义反函数$$g(z) = f^{-1}(z)$$，使得$$f(g(z)) = z$$，换言之，$$f(w) = g^{-1}(w) = z$$
那么对于任何解析函数$$H$$
```math
\displaystyle
[z^n] H(g(z)) = \frac{1}{n} [w^{n-1}] \left( H'(w) \left( \frac{w}{f(w)} \right)^n \right)
```
**最常用**的特例是$$H(w) = w$$时，直接求反函数$$w = g(z)$$的系数
```math
\displaystyle
[z^n] g(z) = \frac{1}{n} [w^{n-1}] \left( \frac{w}{f(w)} \right)^n
```

> 证明如下，根据柯西积分公式
>
```math
\displaystyle
[z^n] H(g(z)) = \frac{1}{2\pi i} \oint_{\gamma} \frac{H(g(z))}{z^{n+1}} dz
```
令$$z = f(w), g(z) = f^{-1}(z) = w$$
```math
\displaystyle
[z^n] H(g(z)) = \frac{1}{2\pi i} \oint_{\Gamma} \frac{H(w)}{f(w)^{n+1}} f'(w) dw
```
其中考虑到$$\frac{f'(w)}{f(w)^{n+1}} = -\frac{1}{n} \frac{d}{dw} \left( f(w)^{-n} \right)$$，代回去

> 
```math
\displaystyle
[z^n] H(g(z)) = \frac{1}{2\pi i} \oint_{\Gamma} H(w) \cdot \left[ -\frac{1}{n} \frac{d}{dw} (f(w)^{-n}) \right] dw \\
\quad \\
= -\dfrac{1}{2 \pi i} \oint_{\Gamma} H(w) \cdot d(f(w)^{-n})
```
利用分部积分公式$$-\int udv = \int vdu - uv$$，因为是闭合曲线，所以$$uv$$这一项是`0`
```math
\displaystyle
[z^n] H(g(z)) = \frac{1}{n} \cdot \frac{1}{2\pi i} \oint_{\Gamma} \frac{H'(w)}{f(w)^n} dw
```

> 下面考虑**提取系数**，分子分母同时$$\times w^n$$
```math
\displaystyle
[z^n] H(g(z)) = \frac{1}{n} \cdot \frac{1}{2\pi i} \oint_{\Gamma} \frac{H'(w) \left( \frac{w}{f(w)} \right)^n}{w^n} dw
```
从而有，积分的结果实际上对应在$$w^{n-1}$$的系数
```math
\displaystyle
[z^n] H(g(z)) = \frac{1}{n} [w^{n-1}] \left( H'(w) \left( \frac{w}{f(w)} \right)^n \right)
```

## 留数的计算
不妨设
```math
\displaystyle
g(z) = \dfrac{\phi (z)}{(z-a)^m}
```
将$$\phi(z)$$展开成以$$a$$为中心的 Taylor 级数
```math
\displaystyle
\phi(z) = \sum_{n = 0}^{\infty} c_n (z-a)^n, \quad c_n = \dfrac{\phi^{(n)} (a)}{n!}
```
那么我们有，在$$m$$阶极点的留数
```math
\displaystyle
Res_{z = a} = c_{m-1} = \dfrac{\phi^{(m-1)} (a)}{(m-1)!} \\
\quad \\
= \dfrac{1}{(m-1)!} \lim_{z \to a} \frac{d^{m-1}}{dz^{m-1}} ((z-a)^m g(z))
```

看完文章有啥想法

算法小站

wiki 主题

数学

斯特林数相关的处理方法

目录