组合数学的一些知识小结（未完）
Fading
·
·
个人记录
二项式反演
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个项链的方案数。(圆排列个数)
比如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{行})\text{(题解)}
模板。
(\text{CF932E Team Work})\text{(题解)}
n^m=\sum_{i=0}^mC_n^iS_m^ii!
暴力代入就好了。
(\text{P4091 [HEOI2016/TJOI2016]求和)}\text{(题解)}
暴力代入第二类斯特林数通项公式，卷积就好了。
(\text{P4827 [国家集训队]Crash的文明世界})
神仙题，利用n^m=\sum_{i=0}^mC_n^iS_m^ii!
然后利用dp记录组合数和，换根+预处理第二类斯特林数。
(\text{[FJOI2016]建筑师})\text{(题解)}
简单的第一类斯特林数，推推式子。
斯特林反演
就是一个公式啦...
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)的。
倍增写法先坑着...