组合数学笔记 | qkoqhh

参考链接

https://rqy.moe/Algorithms/generating-function/

前言

题做的少，也不造组合数学主要考点在哪，就在这里记一下(东抄抄西摘摘)自己不会且感觉比较有价值的东西

~~如果被rqy发现他不会打窝把~~

二项式反演

这个知识点本身不难。。只是窝的题做得比较少。。

基本内容

如果

$g(n)=\sum_{i=0}^n\binom{n}{i}f(i)$

则

$f(n)=\sum_{i=0}^n(-1)^{n-i}\binom nif(i)$

证明

基于 $\sum(-1)^i \binom ni=[n=1]$ ，有

$\begin{aligned} f(n)=&\sum_{i=0}^n[n=i]\binom nif(i) \\=&\sum_{i=0}^n\sum_{j=0}^{n-i}(-1)^j\binom{n-i}jf(i) \\=&\sum_{j=0}^n(-1)^j\sum_{i=0}^{n-j}\binom ni\binom{n-i}jf(i) \\=&\sum_{j=0}^n(-1)^j\sum_{i=0}^{n-j}\binom nj \binom {n-j}if(i) \\=&\sum_{j=0}^n(-1)^j\binom njg(n-j) \\=&\sum_{j=0}^n (-1)^{n-j}\binom njg(j) \end{aligned}$

推论

这个公式有一个更优美的形式~~(但是好像没什么卵用)~~

将 $f(n)\rightarrow(-1)^nf(n)$ ，可以得到

若

$g(n)=\sum_{i=0}^n(-1)^i\binom nif(i)$

则

$f(n)=\sum_{i=0}^n(-1)^i\binom nig(i)$

还有另一个方向的二项式反演：

若

$g(n)=\sum_{i\ge n}(-1)^{i}\binom in f(i)$

则

$f(n)=\sum_{i\ge n}(-1)^{i}\binom in g(i)$

证明

好像网上都没有找到证明，这里就写一下。。

同样的方法

$\begin{aligned} f(n)=&\sum_{i\ge n}(-1)^{i-n}\binom in[i=n]f(i) \\=&\sum_{i\ge n}(-1)^{i-n}\binom in\sum_{j=0}^{i-n}(-1)^j\binom{i-n}j f(i) \\=&\sum_{j\ge 0}\sum_{i\ge n+j}(-1)^{i-n}(-1)^j\binom in\binom{i-n}jf(i) \\=&\sum_{j\ge n}\sum_{i\ge j}(-1)^{i-n}(-1)^{j-n} \binom in\binom{i-n}{j-n}f(i) \\=&\sum_{j\ge n}\sum_{i\ge j}(-1)^{i+j}\binom ij \binom jnf(i) \\=&\sum_{j\ge n}(-1)^j\binom jn\sum_{i\ge j}(-1)^i\binom ijf(i) \\=&\sum_{j\ge n}(-1)^j\binom jng(j) \end{aligned}$

生成函数

普通型生成函数(OGF)

普通型生成函数($ordinary$ $generating$ $function$，下称 $OGF$ )的形式大致如下：

对数列 $f=f_0,f_1,f_2… $ ，其生成函数为

$F(x)=\sum_{k=1}^{\infty}f_kx^k$

常见的 $OGF$

数列	OGF
$<1,0,0,...>$	$1$
$<1,1,1,...>$	$\frac{1}{1-x}$
$<1,2,3,...>$	$\frac{1}{(1-x)^2}$
$<1,-1,1,-1,...>$	$\frac{1}{1+x}$
$<1,2,1,0,0,...>$	$(1+x)^2$
$<1,4,6,4,1,0,0,...>$	$(1+x)^3$

$OGF$ 的性质

$\begin{aligned} \alpha F(x)+\beta G(x)&=\sum_n(\alpha f_n+\beta g_n)x^n\\ x^mF(x)&=\sum_n[n\geq m]f_{n-m}x^n\\ \frac{F(x)-\sum_{i=0}^{m-1}f_ix^i}{x^m}&=\sum_nf_{n+m}x^n\\ F(cx)&=\sum_nc^nf_nx^n\\ F^\prime(x)&=\sum_n(n+1)f_{n+1}x^n\\ \int_0^xF(t)\mathrm{d}t&=\sum_n[n>0]\frac{f_{n-1}}nx^n\\ F(x)G(x)&=\sum_n\left(\sum_{i=0}^nf_ig_{n-i}\right)x^n \end{aligned}$

性质都是多项式的性质，比较好记

指数型生成函数(EGF)

指数型生成函数( $exponential$ $generating$ $function$，简称 $EGF$ )的形式大致如下：

对数列 $f=$ ，其生成函数为

$F(x)=\sum_{k=1}^{\infty}f_k\frac{x^k}{n!}$

其意义体现在其乘法操作上：

$F(x)G(x)=\sum_n\left(\sum_{i=0}^n\binom nif_ig_{n-i}\right)x^i$

多出来的 $\binom{n}{i}$ 告诉我们它适用于排列的计算（相对于 $OGF$ 的普通卷积对应组合）。

常见的 $EGF$

数列	EGF
$<1,1,1,...>$	$e^x$
$<0,1,2,...>$	$xe^x$
$<1,c,c^2,...>$	$e^{cx}$

$EGF$ 的性质

$\begin{aligned} \alpha F(x)+\beta G(x)&=\sum_n(\alpha f_n+\beta g_n)\frac{x^n}{n!}\\ x^mF(x)&=\sum_n[n\geq m]n^{\underline m}f_{n-m}\frac{x^n}{n!}\\ \frac{F(x)-\sum_{i=0}^{m-1}f_ix^i}{x^m}&=\sum_n\frac1{(n+m)^{\underline m}}f_{n+m}\frac{x^n}{n!}\\ F(cx)&=\sum_nc^nf_n\frac{x^n}{n!}\\ F^\prime(x)&=\sum_nf_{n+1}\frac{x^n}{n!}\\ \int_0^xF(t)\mathrm{d}t&=\sum_n[n>0]f_{n-1}\frac{x^n}{n!}\\ \sum_{n}n^{\underline k}\frac{x^n}{n!}&=x^ke^x \\ \sum_{n}(n-1)!\frac{x^n}{n!}&=\ln \frac{1}{1-x} \\ F(x)G(x)&=\sum_n\left(\sum_{i=0}^n\binom nif_ig_{n-i}\right)\frac{x^n}{n!} \end{aligned}$

看起来比较陌生了，这个得多熟悉熟悉

斯特林数

第一类斯特林数

第一类斯特林数是指将 $n$ 个元素划分成为 $m$ 个轮换(或者环)的方案数，记作 $S_1(n,m)$ ，具体数学记作 $n\brack m$

递推公式

${n\brack m}={n-1\brack m-1}+(n-1){n-1\brack m}$

证明：

考虑组合意义，当把第 $n$ 个数加入时，要么另开一个环，要么加到已有的环中，有 $n$ 个位置可以插入

求法

这个求法的复杂度是 $O(n^2)$ 的，网上有一个倍增求第一类斯特林数的复杂度为 $O(nlogn)$

构造 $F_n(x)=\sum {n\brack k}x^k$

然后由斯特林数的递推公式可得

$F_n(x)=xF_{n-1}(x)+(n-1)F_{n-1}(x)$

所以有

$F_n(x)=\prod_{i=0}^{n-1}(x+i)$

那么考虑分治处理，假设求出了前 $n$ 项系数 $a0…a{n-1}$ ，先求后 $n$ 项，有

$\begin{aligned} \prod_{i=n+1}^{2n-1}(x+i)&=\prod_{i=0}^{n-1}(x+n+i) \\&=\sum_{i=0}^{n-1}a_i(x+n)^i \\&=\sum_{i=0}^{n-1}a_i\sum_{j=0}^{i}\binom{i}{j}n^{i-j}x^j \\&=\sum_{i=0}^{n-1}\sum_{j=i}^{n-1}a_j\frac{j!}{i!(j-i)!}n^{j-i}x^i \\&=\sum_{i=0}^{n-1}\frac{1}{i!}\sum_{j=i}^{n-1}a_jj!\frac{n^{j-i}}{(j-i)!}x^i \end{aligned}$

对于差固定的卷积，我们可以对其中一个序列进行翻转，就变成普通的卷积了，然后再平移一下即可。。

具体代码

部分公式

$x^{\bar{n}}=\sum_{k=1}^n{n\brack k}x^k\\ \sum_{k=0}^n{n\brack k}=n!$

第二类斯特林数

第二类斯特林数是指将 $n$ 个元素划分成为 $m$ 个集合的方案数，记作 $S_2(n,m)$ ，具体数学记作 $n\brace m$

递推公式

${n\brace m}={n-1\brace m-1}+m{n-1\brace m}$

证明：

考虑组合意义，当把第 $n$ 个数加入时，要么另开一个集合，要么加到已有的环中，有 $m$ 个集合可以加入

求法

先证下式：

${n\brace m}=\frac{1}{m!}\sum_{k=0}^m\binom{m}{k}(-1)^k(m-k)^n$

证明：

考虑枚举空集 $k$ 的个数，容斥一下即可得到全为非空集的方案数

然后对他进行变形，变成卷积形式

${n\brace m}=\sum_{k=0}^{m}\frac{(-1)^k}{k!}\frac{(m-k)^n}{(m-k)!}$

然后上 $FFT$ 就可以了

部分公式

$x^n=\sum_{k=1}^{n}{n\brace k}x^{\underline{k}}$

关于斯特林数其实具体数学里面还有很多公式，不过窝还没能吸收qaq

五边形数

五边形数就是从五边形里面弄出来的一个数列，感觉没什么几何意义

五边形数列为 ${\frac{n(3n-1)}{2} }$

广义的五边形数是由 $\frac{n(3n-1)}{2}$ 和 $\frac{n(3n+1)}{2}$ 组成的

然后有一个经典的多项式，是组合数学上的欧拉函数

$\phi(x)=\prod_{i=1}^\infty (1-x^i)$

有一个结论

$\phi(x)=1+\sum_k (-1)^kx^{\frac{k(3k-1)}{2} }+\sum_k(-1)^kx^{\frac{k(3k+1)}{2} }$

也就是刚好是在广义五边形数上有系数

这个结论就非常舒服了，能够带来不少便利(但是证明很无聊，这里就不给出了)