wiki - 算法小站

wiki 主题

主题名称

是否为父主题

是否为其添加wiki文章

选择主题

修改主题名称

修改父主题

修改wiki文章

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

数学

组合计数

二项式定理

生成函数（一）

FFT

多项式与形式幂级数

同余与模

同余与模的应用

同余与模的概念

特殊的数

斯特林数

斯特林数相关的恒等式

斯特林数的综合应用

[[ item.c ]]

斯特林数

## 第二类斯特林数
**问题**
有`n`个互不相同的球，放到`k`个**互不区分**的盒子里，每个盒子里至少要有一个球，求方案数
实际上，是把$$n$$个元素划分成$$k$$个子集的方案数，记为`n 子集 k`
> 递推求解

用$$f(n, k)$$来表示方案数，假设已经完成了$$n - 1$$个球，考虑第`n`个球的放法，有两种决策
第一种是第`n`个球单独开一个盒子，剩下对应$$n - 1$$个球放入$$k-1$$个盒子的方案数
这种情况的答案是$$f(n-1, k-1)$$
第二种，考虑$$n - 1$$个球用完了$$k$$个盒子，方案数是$$f(n - 1, k)$$，然后第$$n$$个球选其中`1`个盒子放
方案数是$$\displaystyle\binom{k}{1}$$

综上所述，$$f(n, k) = f(n-1, k-1) + k f(n - 1, k)$$

这样的数记为**第二类斯特林数**$$\displaystyle {n \brace m}$$
```math
\displaystyle
{n \brace k} = k {{n-1} \brace k} + {{n-1} \brace {k-1}} \quad n > 0
```

（当然也有第一类斯特林数，记为$$\displaystyle {n \brack m}$$）

### 第二类斯特林数的性质
**容斥**
```math
\displaystyle
{n \brace  k} = \dfrac{1}{k!} \sum_{i = 0}^{k} (-1)^i \binom{k}{i} (k - i)^n
```
虽然有`k`个互不区分的盒子，但可以**编号**成$$1,2, \cdots, k$$
记$$a_i$$表示`第 i 个盒子里没有球`，那么对应的方案数记为
```math
\displaystyle
N(1-a_1, 1-a_2, \cdots, 1-a_k)
```
根据容斥原理
```math
\displaystyle
N(1-a_1, 1-a_2, \cdots, 1-a_k) = \sum_{i = 0}^{k}(-1)^i \binom{k}{i} N(a_1, a_2, \cdots, a_i)
```
其中$$N(a_1, \cdots, a_i)$$表示前$$i$$个盒子里面**一定没有球**
那么`n`个球，都有$$\binom{k - i}{1}$$个盒子可以放，所以$$N(a_1, \cdots, a_i) = (k - i)^n$$
```math
\displaystyle
\sum_{i = 1}^{k} (-1)^i \binom{k}{i} (k - i)^n = {n \brace k} k!
```

**封闭形式**
```math
\displaystyle
n^m = \sum_{k = 0}^{m} {m \brace k} n^{\underline{k}}
```

> 代数证明

注意到$$x^{\underline{k+1}} = x(x-1)\cdots(x-k)$$
而$$x^{\underline{k}} = x(x-1)\cdots(x-k+1)$$
所以有$$x^{\underline{k+1}} = x^{\underline{k}}(x - k)$$，即$$x \cdot x^{\underline{k}} = x^{\underline{k+1}} + kx^{\underline{k}}$$

用数学归纳法，对$$n$$归纳
```math
\displaystyle
x^n = x \cdot x^{n-1} = x \sum_{k} { {n-1} \brace k }x^{\underline{k}} \\
\quad \\
= \sum_{k} { {n-1} \brace k }x^{\underline{k+1}} + \sum_k {{n-1} \brace k} kx^{\underline{k}} \\
\quad \\
= \sum_k { {n-1} \brace {k-1} } x^{\underline{k}} + \sum_k { {n-1} \brace k } kx^{\underline{k}} \\
\quad \\
= \sum_k {n \brace k} x^{\underline{k}}
```

> 组合意义

有$$n$$个盒子，$$m$$个球，球放入盒子的方案数总共是$$n^m$$

同时，考虑哪些盒子是一定要放球的，枚举有$$k$$个盒子是一定要放球的
从$$n$$个盒子中选$$k$$个，方案数是$$\displaystyle \binom{n}{k}$$

然后将$$m$$个球，放入$$k$$个互不区分的盒子，方案数是$$\displaystyle {m \brace k}$$
另外，总的方案数对相同的盒子是要区分的，还需要$$\times k!$$

所以有$$\displaystyle n^m = \sum_k \binom{n}{k} {m \brace k} k!$$

## 第一类斯特林数
**轮换**
环形序列，比如说`[A, B, C, D] = [B, C, D, A] = [C, D, A, B] = [D, A, B, C]`是同一种轮换
但是`[A, B, C]`和`[A, C, B]`却构成了不同的轮换

如果两个序列能够通过循环移位来变成一样的，那么它们就属于同一个轮换

**第一类斯特林数**
```math
\displaystyle
{n \brack k}
```
定义为将$$n$$个元素拆分成$$k$$个轮换的方案数

### 一些性质
**和排列的关系**
任何一个大小为$$n$$的轮换，都可以映射到一个排列上
但还不够，可以把轮换中`n`个元素中的任意一个作为第一个元素。即$$\displaystyle\binom{n}{1} {n \brack 1} = n!$$
这样才和排列一一对应，所以$$\displaystyle {n \brack 1} = (n - 1)! \quad n > 0$$

**任何一个排列可以进行轮换分解**
```bash
1 2 3 4 5 6 7 8 9
3 8 4 7 2 9 1 5 6

[1, 3, 4, 7][2, 8, 5][6, 9]
```
从而一定有
```math
\displaystyle
\sum_{k = 0}^{n} {n \brack k} = n! \quad (n \geqslant 0)
```

**和第二类斯特林数初步的关系**
轮换数至少应该和子集数一样大
```math
\displaystyle
{n \brack k} \geqslant {n \brace k} \quad n, k \geqslant 0
```
当所有的轮换都一定是单元素或者是双元素的时候，等号成立，在这种情形中，轮换和子集等价
（即使是`2`个元素的轮换，也只有`1`种方案，`[A, B] = [B, A]`）
```math
\displaystyle
{n \brack n} = {n \brace n} = 1, \quad {n \brack {n-1}} = {n \brace {n-1}} = \binom{n}{2}
```
第二个式子是因为，将$$n$$个元素放进$$n - 1$$个轮换，第一步先考虑一个元素对应一个轮换
然后考虑任意选`2`个元素合并，方案数是$$\displaystyle \binom{n}{2}$$

**递推**
**引理**，恰有$$j$$种方式，把一个新元素放入**大小**为$$j$$的轮换
可以用插板法来证明，本来有`j+1`个空位可以插，但是插到最后一个位置，和插入第一个位置
得到的轮换是一样的，所以插空方式恰好有$$j$$种

对$$\sum_j$$求和，`插空方式 = sum(已经划分的轮换大小之和) = n - 1`
```math
\displaystyle
{n \brack k} = (n - 1) {{n-1} \brack k} + {{n-1} \brack {k-1}} \quad n > 0
```
第一个式子，恰好对应了“把最后一个元素放进前$$n - 1$$个元素划分成的$${{n-1} \brack k}$$个轮换”的方案数

**封闭形式**
```math
\displaystyle
x^{\overline{n}} = x(x+1)\cdots (x+n-1) \\
\quad \\
x^{\overline{n-1}} = x(x+1)\cdots (x+n) \\
\quad \\
x^{\overline{n}} = (x+n - 1)x^{\overline{n-1}} = (x+n-1)\sum_k {{n-1} \brack k}x^k = \sum_k {n \brack k} x^k
```
最后一步是对$$n$$归纳

**一些冷门的递推**
```math
\displaystyle
x^{\underline{n}} = (-1)^n(-x)^{\overline{n}}
```
> 注意到
```math
\displaystyle
x^{\overline{n}} = \sum_k {n \brack k}x^k , \text{ let } x \leftarrow (-x) \\
\quad \\
(-x)^{\overline{n}} = \sum_k {n \brack k}(-1)^k x^k \Rightarrow (-1)^nx^{\underline{n}} = \sum_k {n \brack k}(-1)^k x^k 
```

从而有
```math
\displaystyle
x^{\underline{n}} = \sum_k {n \brack k} (-1)^{n-k}x^k
```

> 另一方面
```math
\displaystyle
x^n = \sum_k {n \brace k} x^{\underline{k}}, \text{ let } x = (-x) \\
x^n (-1)^n = \sum_k {n \brace k} (-x)^{\underline{k}} = \sum_k {n \brace k} (-1)^k x^{\overline{k}}
```

从而有
```math
\displaystyle
x^n = \sum_k {n \brace k} (-1)^{n-k}x^{\overline{k}}
```

## 一些冷门的性质
### 第二类斯特林数的指数生成函数
> 根据**容斥推导**
```math
\displaystyle
m!{n \brace m} = \sum_{j = 0}^{m} (-1)^{m-j} \binom{m}{j} j^n
```
因为$$\displaystyle \sum\_{n \geqslant 0} j^n \dfrac{x^n}{n!} = e^{jx}$$，两边同时$$\times \dfrac{x^n}{n!}$$
```math
\displaystyle
m! {n \brace m} \dfrac{x^n}{n!} = \sum_{j = 0}^{m} (-1)^{m-j} \binom{m}{j} j^n \dfrac{x^n}{n!}
```
两边同时关于$$n$$求和，$$\sum\_{n \geqslant 0}$$
```math
\displaystyle
\sum_{n \geqslant 0} m! {n \brace m} \dfrac{x^n}{n!} = \sum_{j = 0}^{m} (-1)^{m-j} \binom{m}{j} e^{jx}
```
不难发现，右边实际上就是关于$$(e^x - 1)^m$$的二项展开
```math
\displaystyle
\sum_{n \geqslant 0} m! {n \brace m} \dfrac{x^n}{n!} = (e^x - 1)^m
```

指数生成函数
```math
\displaystyle
\sum_{n \geqslant 0} {n \brace m} \dfrac{x^n}{n!} = \dfrac{(e^x - 1)^m}{m!}
```

### 第一类斯特林数的指数生成函数
> 长度为$$j$$的圆排列的方案数是$$(j - 1)!$$，前面讨论过了
方案数记为$$C(z)$$，对应的 EGF 表示为
```math
\displaystyle
C(z) = \sum_{j = 1}^{\infty} (j-1)! \dfrac{z^j}{j!} = \sum_{j = 1}^{\infty} \dfrac{z^j}{j} \\
= -\ln(1-z)
```
考虑有$$k$$个圆排列，并且每个组件之间不做区分，那么恰好对应第一类斯特林数，即`n 轮换 k`
```math
\displaystyle
\sum_{n = k}^{\infty} {n \brack k} \dfrac{z^n}{n!} = \dfrac{C^k(z)}{k!} = \dfrac{ (-\ln(1-z))^k }{k!}
```

```math
\displaystyle
\sum_{n = k}^{\infty} {n \brack k} \dfrac{z^n}{n!} = \dfrac{ (-\ln(1-z))^k }{k!}
```

> 代数推导，因为
```math
\displaystyle
x^{\overline{n}} = \sum_k {n \brack k} x^k, \text{  let } G(z, x) = \sum_{n = 0}^{\infty} \dfrac{z^n}{n!}\sum_{k = 0}^{n} {n \brack k}x^k = \sum_{n = 0}^{\infty}x^{\overline{n}} \dfrac{z^n}{n!}
```
根据
```math
\displaystyle
\binom{-x}{n} = \dfrac{(-x)(-x-1)\cdots (-x-n+1)}{n!} = \dfrac{(-1)^n x^{\overline{n}}}{n!} \\
\quad \\
(1-z)^{-x} = \sum_{n = 0}^{\infty} \dfrac{(-1)^n x^{\overline{n}}}{n!} (-z)^n = \sum_{n = 0}^{\infty} \dfrac{x^{\overline{n}}}{n!} z^n
```
对比发现
```math
\displaystyle
G(z, x) = (1 - z)^{-x} \\
G(z, x) = e^{-x \ln (1-z)} = \sum_{k = 0}^{\infty} x^k \dfrac{(-\ln (1-z))^k}{k!}
```
另一方面，回到最原本的定义
```math
\displaystyle
G(z, x) = \sum_{k = 0}^{\infty}x^k \left( \sum_{n = k}^{\infty} {n \brack k} \dfrac{z^n}{n!} \right)
```
比较$$[x^k]$$可以得到结论

## 差分序列和斯特林数
### 算子方法
定义移位算子$$(Ef)(x) = f(x+1)$$，恒等算子$$(If)(x) = f(x)$$，前向差分算子就是$$\Delta = E-I$$
很显然$$E, I$$均是线性变换，并且可交换，那么
```math
\displaystyle
\Delta^m = (E - I)^m = \sum_{j = 0}^{m} \binom{m}{j} E^j (-1)^{m-j}
```
将其作用到$$f$$上并且在点$$x = 0$$取值，那么有
```math
\displaystyle
\Delta^m f(0) = \sum_{j = 0}^{m} \binom{m}{j} (-1)^{m-j} (E^jf)(0)
```
注意到$$(E^jf)(0)$$相当于平移$$j$$个单位，$$(E^jf)(0) = f(j)$$
```math
\displaystyle
\Delta^mf(0) = \sum_{j = 0}^{m} (-1)^{m - j} \binom{m}{j} f(j)
```
### 二项生成函数
```math
\displaystyle
(1+u)^{x+1} = (1+u)\sum_{k \geqslant 0} \binom{x}{k}u^k = \sum_{k \geqslant 0} \binom{x}{k}u^k + \sum_{k \geqslant 0} \binom{x}{k} u^{k+1}
```
两边关于$$u$$的幂指相同，那么有$$\displaystyle \binom{x+1}{k} = \binom{x}{k} + \binom{x}{k-1}$$
从而有**恒等式**
```math
\displaystyle
(x+1)^{\underline{k}} - x^{\underline{k}} = k x^{\underline{k-1}} \\
\quad \\
\Delta ( x^{\underline{k}} ) = kx^{\underline{k-1}}
```
### 差分序列和斯特林数
对二项生成函数递归
```math
\displaystyle
\Delta^r( x^{\underline{k}} ) = 
\begin{cases}
0 & r > k \\
\dfrac{k!}{(k - r)!}x^{\underline{k-r}} & r \leqslant k
\end{cases}
```
特别地，取$$r = k$$，并且在$$x = 0$$处取值
```math
\displaystyle
\Delta^r( x^{\underline{r}} ) \mid_{x = 0} = k!
```
对左边进行差分展开
```math
\displaystyle
\Delta^mf(0) = \sum_{j = 0}^{m} (-1)^{m-j} \binom{m}{j} f(j) = \sum_{j = 0}^{m} (-1)^{m-j} \binom{m}{j} j^{\underline{k}} \\
\quad \\
= \begin{cases}
0, & k < m \\
m! & k = m
\end{cases}
```

考虑朴素的恒等式$$\displaystyle j^n = \sum\_{k = 0}^{n} {n \brace k} j^{\underline{k}}$$
> 这可以有组合意义的证明，$$n$$个球放入$$j$$个桶的方案，需要在$$j$$个桶中选$$k$$个必须放球
然后对应$$k ! \displaystyle {n \brace k}$$，所以方案数是$$\displaystyle \sum\_{k} \binom{j}{k} k! {n \brace k}$$

在等式两边对$$j = 0, 1, \cdots, m$$作二项求和，$$\times (-1)^{m-j} \binom{m}{j}$$
```math
\displaystyle
\sum_{j = 0}^{m} (-1)^{m-j} \binom{m}{j}j^n = \sum_{k = 0}^{n} {n \brace k} \left( \sum_{j=0}^{m} (-1)^{m-j} \binom{m}{j} j^{\underline{k}} \right)
```
不难发现，右边只有$$k = m$$这一项，这一项的值恰好是$$m!$$，所以有
```math
\displaystyle
\sum_{j = 0}^{m} (-1)^{m - j} \binom{m}{j} j^n = {n \brace m} m!
```
这就是斯特林数的一种封闭形式
```math
\displaystyle
m!{n \brace m} = \sum_{j = 0}^{m} (-1)^{m - j} \binom{m}{j} j^n
```

## 一些恒等式
**恒等式（1）**
```math
\displaystyle
{{n+1} \brace {m+1}} = \sum_{k = 0}^{n} \binom{n}{k} {k \brace m}
```
> 组合证明
将$$n+1$$个元素划分成$$m+1$$个子集，考虑最后一个元素$$n+1$$，它在哪一个子集（块）中
枚举恰有$$k$$个元素**不和**最后一个元素`n+1`在同一个块中，枚举的方案是$$\binom{n}{k}$$
那么这$$k$$个元素只有$$m$$个块可供选择
方案数对应将$$k$$个元素划分成$$m$$个子集的方案，即$${k \brace m}$$

> 代数证明，构造 EGF
```math
\displaystyle
\sum_{n \geqslant 0} {{n+1} \brace {m+1}} \dfrac{x^n}{n!} = \dfrac{d}{dx} \sum_{n} {n \brace {m+1}}\dfrac{x^n}{n!} \\
\quad \\
\sum_{n \geqslant m+1} {n \brace {m+1}} \dfrac{x^n}{n!} = \dfrac{(e^x - 1)^{m+1}}{(m+1)!} \\
\quad \\
\sum_{n \geqslant 0} {{n+1} \brace {m+1}} \dfrac{x^n}{n!} = \dfrac{d}{dx} \left( \dfrac{(e^x - 1)^{m+1}}{(m+1)!} \right)
```
微分后可以发现
```math
\displaystyle
\sum_{n \geqslant 0} {{n+1} \brace {m+1}} \dfrac{x^n}{n!} = \dfrac{(e^x - 1)^m e^x}{m!} \\
\quad \\
\Longrightarrow\dfrac{(e^x - 1)^m}{m!} = \sum_{k \geqslant m} {k \brace m} \dfrac{x^k}{k!}, \quad e^x = \sum_{r}\dfrac{x^r}{r!} \\
\quad \\
\sum_k \sum_r {k \brace m} \dfrac{x^{k+r}}{k!r!} \xLeftrightarrow{n = k+r} \sum_{n \geqslant 0} \left( \sum_{k = 0}^{n} {k \brace m} \dfrac{x^n}{k!(n-k)!} \right) \\
\quad \\
=\sum_{n \geqslant 0} \left( \sum_{k = 0}^{n} \binom{n}{k} {k \brace m} \right) \dfrac{x^n}{n!}
```

**恒等式（2）**
```math
\displaystyle
{{n+1} \brack {m+1}} = \sum_{k} {n \brack k} \binom{k}{m}
```

> **组合视角**
每个圆排列以其最大元素开头，并且圆排列之间，按照开头元素的大小升序排列
对于第`n+1`开头的排列，它必然是最后一个圆排列的开头
那么我们要构造$$m+1$$个圆排列，前面的$$m$$个呢？可以从$$n$$个元素形成的任意$$k$$个圆排列中挑选
挑完之后，还剩下$$k-m$$个多出来的圆排列，按顺序拼接在`n+1`后面，合并
这样就形成了唯一的包含$$n+1$$的大圆排列

> **代数视角**，利用$$\sum\_{k=0}^{n} {n \brack k}u^k = u^{\overline{n}}$$

> ```math
\displaystyle
P_n(u) = \sum_{k = 0}^{n} {n \brack k} u^k = u^{\overline{n}} \\
\quad \\
P_n(1+x) = \sum_{k=0}^{n} {n \brack k} (1 + x)^k = \sum_{k = 0}^{n} {n \brack k} \sum_{m \geqslant 0} \binom{k}{m}x^m = \sum_{m \geqslant 0} \left( \sum_{k \geqslant 0}^{n} {n \brack k} \binom{k}{m} \right)x^m
```
另一方面
```math
\displaystyle
(1+x)^{\overline{n}} = (1+x)(2+x)\cdots (n+x) = \dfrac{x^{\overline{n+1}}}{x} = \dfrac{1}{x} \sum_{k = 0}^{n+1} {{n+1} \brack k}x^k \\
\quad \\
= \sum_{k = 0}^{n+1} {{n+1} \brack k}x^{k-1} = \sum_k {{n+1} \brack {k+1}}x^{k}
```
比较系数即证

看完文章有啥想法

算法小站

wiki 主题

数学

斯特林数

目录