组合数学的一些知识小结（未完）
Fading
2019-01-14 16:59:33
## 二项式反演
$$f(n) = \sum_{i = 0}^{n} (-1)^{i}C_{n}^{i}g(i) \Leftrightarrow g(n) = \sum_{i = 0}^{n} (-1)^{i} C_{n}^{i}f(i)$$
以及
$$f(n) = \sum_{i = 0}^{n} C_{n}^{i}g(i) \Leftrightarrow g(n) = \sum_{i = 0}^{n} (-1)^{n-i} C_{n}^{i}f(i)$$
还有一条经常用的
$$f(n) = \sum_{i = n}^{\infty} C_{i}^{n}g(i) \Leftrightarrow g(n) = \sum_{i = n}^{\infty} (-1)^{i-n} C_{i}^{n}f(i)$$
证明就算了吧~~这掩盖不了我不会的事实~~
## 第二类斯特林数
第二类斯特林数$S_n^m$表示的是把$n$个不同的小球放在$m$个相同的盒子里方案数。**盒子不能为空**
比如$n=4,m=2$
```
123 4
124 3
134 2
234 1
12 34
13 24
14 23
```
所以 $S_4^2=7$
也可以这么表示：$\begin {Bmatrix} n \\ m\end {Bmatrix}$
### 递推式：
$$S_n^m=S_{n-1}^{m-1}+mS_{n-1}^m$$
就不讲了，比较蠢。
还有一个性质就是说：
$$n^m=\sum_ { i=0}^m S_m^i×i!×C_n^i$$
怎么理解呢？
左边是$m$个球可以任意放在$n$个盒子里的答案
右边就是枚举有多少个盒子空着，然后组合数枚举一下。最后因为盒子不同所以要乘一个$i!$
然后我们考虑**通项公式**
$$n^m=\sum_ { i=0}^m S_m^i×i!×C_n^i$$
当然因为$m\geq n$
$$∴n^m=\sum_ { i=0}^n S_m^i×i!×C_n^i$$
设$f(n)=n^m,g(i)=S_m^i×i!$
二项式反演一下就有
$$S_m^n×n!=\sum_ { i=0}^n i^m\times(-1)^{n-i}×C_n^i$$
$$S_m^n=\frac 1{n!}\sum_ { i=0}^n i^m\times(-1)^{n-i}×C_n^i$$
这就是通项公式了
再拆一下$C_n^i=\frac {n!}{i!\times(n-i)!}$
$$∴\ =\sum_ {i=0}^n \frac {(-1)^{n-i}\times i^m}{i!\times (n-i)!}$$
如果你要追求**对称美**的话，可以利用$C_n^i=C_n^{n-i}$
换枚举方式就有
$$S_m^n=\sum_ {i=0}^n \frac {(-1)^{i}\times (n-i)^m}{i!\times (n-i)!}$$
### 求法
发现是一个卷积的形式，直接$NTT$就可以了。
## 第一类斯特林数
第一类斯特林数$s_n^m$(方便区分)表示的是把$n$个不同的小球串成$m$个项链的方案数。([圆排列](https://baike.baidu.com/item/%E5%9C%86%E6%8E%92%E5%88%97/6775234?fr=aladdin)个数)
比如$n=4,m=2$
```
123 4
132 4
124 3
142 3
134 2
143 2
234 1
243 1
12 34
13 24
14 23
```
所以 $s_4^2=11$
也可以这么表示：$s_i^j=\begin{bmatrix} i\\ j \end{bmatrix}$
### 递推式：$s_n^m=s_{n-1}^{m-1}+(n-1)s_{n-1}^m$
可以单独成一个圆排列，也可以加入任意一个数的后面。
有一个有趣的东西：
$$\sum_{i=0}^n s_n^i=n!$$
为什么是对的呢？考虑置换的定义。
比如一个排列
```
123456
```
和
```
145263
```
可以看成三个置换
```
[1][24][356]
```
意义就是$1->1,2->4->2,3->5->6->3$
可以发现一组圆排列对应一组置换，一组置换对应一组排列，所以这个式子是对的。
### 求法
后面讲。
## 习题$1$
[$(\text{P5395 第二类斯特林数}·\text{行})$](https://www.luogu.org/problemnew/show/P5395)[$\text{(题解)}$](https://www.luogu.org/blog/wohaocaia/solution-p5395)
模板。
[$(\text{CF932E Team Work})$](https://www.luogu.org/problemnew/show/CF932E)[$\text{(题解)}$](https://www.luogu.org/blog/wohaocaia/solution-p3175)
$n^m=\sum_{i=0}^mC_n^iS_m^ii!$
暴力代入就好了。
[$(\text{P4091 [HEOI2016/TJOI2016]求和)}$](https://www.luogu.org/problemnew/show/P4091)[$\text{(题解)}$](https://www.luogu.org/blog/wohaocaia/solution-p3175)
暴力代入第二类斯特林数通项公式，卷积就好了。
[$(\text{P4827 [国家集训队]Crash的文明世界})$](https://www.luogu.org/problemnew/show/P4827)
神仙题，利用$n^m=\sum_{i=0}^mC_n^iS_m^ii!$
然后利用$dp$记录组合数和，换根+预处理第二类斯特林数。
[$(\text{[FJOI2016]建筑师})$](https://www.luogu.org/problemnew/show/P4609)[$\text{(题解)}$](https://www.luogu.org/blog/wohaocaia/solution-p4609)
简单的第一类斯特林数，推推式子。
## 斯特林反演
就是一个公式啦...
$$f(i)=\sum_{i=0}^nS_n^ig(i)\Leftrightarrow g(i)=\sum_{i=0}^n(-1)^{n-i}s_n^if(i)$$
暂时没用过，咕咕咕
## 斯特林数与下降幂
### 下降幂:定义
$${x}^{\underline{i}}=\prod_{j=0}^{i-1}(x-j)$$
### 上升幂:定义
$$x^{\overline{i}}=\prod_{j=0}^{i-1}(x+j)$$
### 有趣的性质
$$x^n=\sum_{i=1}^nS_{n}^{i}{x}^{\underline{i}}$$
好神仙啊，为什么是对的呢？？？
考虑数学归纳法：
假设之前都是对的（懒）
$$x^n=x^{n-1}x=x\sum_{i=1}^{n-1}S_{n-1}^{i}{x}^{\underline{i}}$$
由于${x}^{\underline{i+1}}={x}^{\underline{i}}(x-i)$
$$\therefore\ =\sum_{i=1}^{n-1}S_{n-1}^{i}{x}^{\underline{i+1}}+\sum_{i=1}^{n-1}iS_{n-1}^{i}{x}^{\underline{i}}$$
由于$S_n^0=0,S_n^{n+1}=0$
$$\therefore\ =\sum_{i=1}^{n}S_{n-1}^{i-1}{x}^{\underline{i}}+\sum_{i=1}^{n}iS_{n-1}^{i}{x}^{\underline{i}}$$
$$=\sum_{i=1}^nS_{n}^{i}{x}^{\underline{i}}$$
还有一些有趣的式子（$4$个，证明方法类似，也可以套用斯特林反演）
$$x^n=\sum_{i=1}^nS_{n}^{i}{x}^{\underline{i}}$$
$$x^{\overline{n}}=\sum_{i=1}^ns_{n}^{i}{x}^i$$
$$x^n=\sum_{i=1}^nS_{n}^{i}(-1)^{n-i}{x}^{\overline{i}}$$
$$x^{\underline{n}}=\sum_{i=1}^ns_{n}^{i}(-1)^{n-i}{x}^i$$
后面两个非常有趣，为什么乘上$-1$的幂次就对了呢？
比如
$$x^{\underline{4}}=x^4-6x^3+11x^2-6x$$
$$x^{\overline{4}}=x^4+6x^3+11x^2+6x$$
懂了吗 qwq
### 第一类斯特林数的求法
考虑上述式子
$$x^{\overline{n}}=\sum_{i=1}^ns_{n}^{i}{x}^i$$
可以看出上升幂就是这个数列的生成函数。
什么意思？
$$x^{\overline{n}}=\sum_{i=0}^{\infty}s_{n}^{i}{x}^i$$
所以我们把$x^{\overline{n}}$看成一个多项式，求出这个多项式的$i$次项系数就是$s_{n}^{i}$啦！
怎么求呢？暴力$FFT(NTT)$求出$(x)\times(x+1)\times...(x+n-1)$，这样时间复杂度就是$O(n^2\log_2n)$
考虑分治，用分治$FFT$，对于一段区间$[l,r]$，递归处理$[l,mid],[mid+1,r]$，然后乘起来，这样时间复杂度是$O(n\log^2_2n)$的。
倍增写法先坑着...