2019-04-26 21:56 已编辑山东大学 Web前端

关注

【博客】斯特林数、容斥和反演整理

斯特林数

第一类斯特林数

s(n, m)表示将n个元素分成m个圆排列的方案数
也可以记作 $\begin{bmatrix}n\\m\end{bmatrix}$
递推式
$\begin{bmatrix}n\\m\end{bmatrix} = \begin{bmatrix}n - 1\\m - 1\end{bmatrix} + (n - 1)\begin{bmatrix}n - 1\\m\end{bmatrix}$
表示可以自己单独拿出来成为一个环，也可以放在任意一个元素的前面
性质1
$\sum_{i=0}^n \begin{bmatrix}n\\i\end{bmatrix} = n!$
证明：每个排列实际上对应着一个置换
考虑s(n,i)分成的i个环，实际上就是对应着循环节个数为i的一种置换，一一对应过去就是所有置换方案就是全排列了
性质2
$\displaystyle x^{\underline{n}}=\sum_{i=0}^n\begin{bmatrix}n\\i\end{bmatrix}(-1)^{n-i}x^i$
证明：使用数学归纳法
对于 $n == 1$ 的情况，显然成立
对于 $n > 1$ 的情况

$\begin{aligned}x^{\underline{n+1}}&=(x-n)x^{\underline n}\\ &=(x-n)*\sum_{i=0}^n\begin{bmatrix}n\\i\end{bmatrix}(-1)^{n-i}x^i\\ &=\sum_{i=0}^{n+1}\begin{bmatrix}n\\i-1\end{bmatrix}(-1)^{n-i-1}x^i+n\sum_{i=0}^{n+1}\begin{bmatrix}n\\i\end{bmatrix}(-1)^{n-i+1}x^i\\ &=\sum_{i=0}^{n+1}(\begin{bmatrix}n\\i-1\end{bmatrix}+n*\begin{bmatrix}n\\i\end{bmatrix})(-1)^{n+1-i}x^i\\ &=\sum_{i=0}^{n+1}\begin{bmatrix}n+1\\i\end{bmatrix}(-1)^{n+1-i}x^i \end{aligned}$

同理要证明

$\displaystyle x^{\overline n}=\sum_{i=0}^n \begin{bmatrix}n\\i\end{bmatrix}x^i$

$\begin{aligned} x^{\overline {n + 1}}&=(x + n) \sum_{i = 0}^n \begin{bmatrix}n\\i\end{bmatrix} x ^ i\\ &= \sum_{i = 0}^{n + 1} \begin{bmatrix}n\\i - 1\end{bmatrix} x ^ i + n\sum_{i = 0}^{n + 1} \begin{bmatrix}n\\i\end{bmatrix} x ^ i\\ &=\sum_{i = 0}^{n + 1}( \begin{bmatrix}n\\i - 1\end{bmatrix} + n\begin{bmatrix}n\\i\end{bmatrix})x ^ i\\ &= \sum_{i = 0} ^ {n + 1}\begin{bmatrix}n + 1\\i\end{bmatrix} x ^ i \end{aligned}$

自然幂数和问题

记录 $S_k(n) = \sum_{i = 1} ^ n i ^ k$
那么考虑

$\begin{aligned} x^{\underline{n}}&=\sum_{i=0}^n\begin{bmatrix}n\\i\end{bmatrix}(-1)^{n-i}x^i\\ x ^n&=x^{\underline{n}} - \sum_{i = 0}^{n - 1}\begin{bmatrix}n\\i\end{bmatrix}(-1) ^ {(n - i)} x^i\\ \end{aligned}$

把这个带进式子求得

$\begin{aligned} S_k(n) &= \sum_{i = 1}^n i ^ k\\ &= \sum_{i = 1} ^ n (i^{\underline{k}} - \sum_{j = 0}^{k - 1} \begin{bmatrix}k\\j\end{bmatrix} (-1) ^ {k - j}i^j)\\ &=\sum_{i = 1} ^ n i ^{\underline{k}} - \sum_{j = 0} ^ {k - 1} \begin{bmatrix}k\\j\end{bmatrix} (-1) ^ {k - j}(\sum_{l = 1} ^ {n} l ^ j)\\ &= \frac{(n + 1) ^ {\underline{k + 1}}}{k + 1}- \sum_{j = 0} ^ {k - 1} \begin{bmatrix}k\\j\end{bmatrix} (-1) ^ {k - j}s_{j}(n) \end{aligned}$

递推即可
预处理方法
分治fft
构造第一类斯特林数生成函数

$\sum_{i=0}^n\begin{bmatrix}n\\i\end{bmatrix} x^i=\prod_{i=0}^{n-1}(x+i)$

显然可行
倍增法
记 $\displaystyle F_n(x)=\prod_{i=0}^{n-1}(x+i)$
那么存在 $F_{2n}(x)=F_n(x)F_{n}(x+n)$
递归求解 $F_n(x)$ , 然后考虑快速求解 $F_n(x + n)$
考虑设 $F_n(x) = \sum_{i = 0} ^ {n - 1} a_i x ^ i$
则

$\begin{aligned} F_n(x+n)&=\sum_{i=0}^{n-1}a_i (x+n)^i\\ &=\sum_{i=0}^{n-1}a_i\sum_{j=0}^i{i\choose j}n^{i-j}x^j\\ &=\sum_{i=0}^{n-1}(\sum_{j=i}^n {j\choose i}n^{j-i}a_j)x^i \end{aligned}$

后面显然可以卷积
第二类斯特林数
S(n,m)表示把n个元素划分成m个子集的方案数
记作 $\begin{Bmatrix}n\\m\end{Bmatrix}$
递推式
$\begin{Bmatrix}n\\m\end{Bmatrix}=\begin{Bmatrix}n-1\\m-1\end{Bmatrix}+m*\begin{Bmatrix}n-1\\m\end{Bmatrix}$
组合意义是放到任意一个集合中或者新建一个集合
性质1
$\begin{aligned} \begin{Bmatrix}n\\m\end{Bmatrix} &= \frac{1}{m!} \sum_{i = 0} ^ m (-1) ^ i \binom{m}{i}(m - i) ^ n\\ &= \sum_{i = 0}^m \frac{(-1) ^ i}{i!} \frac{(m - i) ^ n}{(m - i) !} \end{aligned}$
可以看做进行容斥，枚举多少个集合不放置，其余的集合随便放置，最后每一种情况会统计m！次
显然可以卷积求解
性质2
$m ^ n = \sum_{i = 0}^m \begin{Bmatrix}n\\i\end{Bmatrix} m^{\underline{i}}$
证明：可以看作将n个求放到m个带标号的盒子内，那么我们枚举哪些盒子不为空，则

$\begin{aligned} m ^ n &= \sum_{i = 0}^m \begin{Bmatrix}n\\i\end{Bmatrix} \binom{m}{i} i!\\ &=\sum_{i = 0}^m \begin{Bmatrix}n\\i\end{Bmatrix} m^{\underline{i}} \end{aligned}$

容斥

经典容斥系数的解

证明每个地方只要被覆盖了就会被统计1次答案，假如这个地方被覆盖了n次，那么 $\begin{aligned} ans&=\sum_{i = 1} ^ n (-1) ^{ (i - 1)} \binom{n}{i}\\ &= \sum_{i = 1} ^ n (\binom{n - 1}{i} + \binom{n - 1}{i - 1}) (-1)^{i - 1}\\ &= \sum_{i = 1} ^ {n - 1} \binom{n - 1}{i} (-1) ^{i - 1} + \sum_{i = 1} ^ n \binom{n - 1}{i - 1} (-1) ^{i - 1}\\ &= \sum_{i = 1} ^ {n - 1} \binom{n - 1}{i} (-1) ^{i - 1} + \sum_{i = 1} ^ {n - 1} \binom{n - 1}{i} (-1) ^{i} + \binom{n}{0}\\ &=1 \end{aligned}$
错排问题
考虑枚举那些地方强制相同，然后其余地方随便放置。

$\begin{aligned} f[n] &= \sum_{i = 0} ^ n \binom{n}{i} (-1)^i(n - i)!\\ &=\sum_{i = 0} ^ n (-1) ^i \frac{n!}{i!}\\ &= (-1) ^ n + n\sum_{i = 0} ^ {n - 1}(-1) ^ i \frac{(n - 1)!}{i!}\\ &= (-1) ^ n + nf[n - 1] \end{aligned}$

min-max容斥

设S是一个可重集合，max(S)和min(S)分别表示集合中的最大值和最小值，则有如下式子成立:

$\begin{aligned} max(S) &= \sum_{T\subseteq S} (-1) ^ {|T| + 1} min(T)\\ min(S) &= \sum_{T\subseteq S} (-1) ^ {|T| + 1} max(T) \end{aligned}$

证明
以第一个式子为例，设max(S)=x，那么只有T={x} 时的min(T) 为x（可能有多个相同的最大值，这时候随便钦点一个就可以了;
对于除此之外的所有T，肯定至少存在一个集合A∩T = ?, 使得min(T和A每个子集的并)等于min(T)，
然后由于从A中选择奇数偶数个元素的方案数相同，所以正负抵消，最后只剩下了x

推广1

在期望下该式子也是成立的，即

$\begin{aligned} E[max(S)] &= \sum_{T\subseteq S} (-1) ^ {|T| + 1} E[min(T)]\\ E[min(S)] &= \sum_{T\subseteq S} (-1) ^ {|T| + 1} E[max(T)] \end{aligned}$

反演

反演本质

给定数列 ${f_i}$ 和 ${g_i}$ 存在关系

$g_n = \sum_{i = 0} ^ n a[n][i] f_i$

这里使用f推出了g，那么我们反演的过程就是使用g推出f
也就是找到系数数组b，使得

$f_n = \sum_{i = 0} ^ n b[n][i] g_i$

引入克罗内克函数（为了好写） $\delta(i,j)=\begin{cases}1&i=j\\0&i\neq j\end{cases}$
整合两个式子得到

$\begin{aligned}f_n&=\sum_{i=0}^n b[n][i]g_i\\&=\sum_{i=0}^n b[n][i]\sum_{j=0}^ia[i][j]f_j\\&=\sum_{i=0}^n f_i\sum_{j=i}^nb[n][j]*a[j][i]\end{aligned}$

同理

$g[n] = \sum_{i = 0} ^ n g_i \sum_{j = i} ^ n a[n][j] * b[j][i]$

显然，这里能够反演的前提条件是

$\begin{cases} \sum_{j = i} ^ n b[n][j] * a[j][i] &= \delta(n, i)\\ \sum_{j = i} ^ n a[n][j] * b[j][i] &= \delta(n,i) \end{cases}$

二项式反演

$f_n=\sum_{i=0}^n {n \choose i}g_i\iff g_n=\sum_{i=0}^n (-1)^{n-i}{n \choose i}f_i$

证明，即要证明

$\begin{cases} \sum_{j = i} ^ n \binom{n}{j}(-1) ^ {j - i}\binom{j}{i} &= \delta(n, i)\\ \sum_{j = i} ^ n (-1) ^ {n - j} \binom{n}{j} \binom{j}{i} &= \delta(n,i) \end{cases}$

仅证第一个，第二个类似

$\begin{aligned} \sum_{j=i}^n{n \choose j}(-1)^{j-i}{j \choose i}&=\delta(n, i)\\ \sum_{j=i}^n(-1)^{j-i}{n \choose i}{n-i \choose j-i}&=\delta(n,i)\\ {n \choose i}\sum_{d=0}^{n-i}(-1)^{d}{n-i \choose d}&=\delta(n, i)\\ \end{aligned}$

后面这堆式子仅当n等于i的时候取值为1，否则取值为0，故得证
另一种形式是

$\begin{aligned}f_n&=\sum_{i=0}^n(-1)^i{n \choose i}g_i\\g_n&=\sum_{i=0}^n(-1)^i{n\choose i}f_i\end{aligned}$

证明

$\begin{aligned} \sum_{j = i} ^ n (-1) ^ j \binom{n} {j} (-1) ^ i \binom{j}{i}&= \delta(n, i)\\ \sum_{j = i} ^ n (-1) ^{i + j} \binom{n}{i} \binom{n - i}{j - i}&=\delta(n,i)\\ \binom{n}{i} \sum_{j = i} ^ {n}(-1) ^{j - i}\binom{n - i}{j - i} &= \delta(n,i) \end{aligned}$

得证

斯特林反演

式子是 $\begin{aligned} f(n)=\sum_{i=1}^n \begin{Bmatrix}n\\i\end{Bmatrix}g(i)\iff g(n)=\sum_{i=0}^n(-1)^{n-i}\begin{bmatrix}n\\i\end{bmatrix}f(i)\end{aligned}$
需要证明

$\begin{cases}\sum_{j=i}^n(-1)^{n-j}\begin{bmatrix}n\\j\end{bmatrix}\begin{Bmatrix}j\\i\end{Bmatrix}=\delta(n,i)\\\sum_{j=i}^n(-1)^{j-i}\begin{bmatrix}j\\i\end{bmatrix}\begin{Bmatrix}n\\j\end{Bmatrix}=\delta(n,i)\end{cases}$

首先容易得到

$\begin{aligned} x^{\underline{n}}=(-1)^n(-x)^{\overline{n}}\\ x^{\overline{n}}=(-1)^n(-x)^{\underline{n}} \end{aligned}$

那么

$\begin{aligned} \displaystyle m^n&=\sum_{i=0}^{n}\begin{Bmatrix}n\\i\end{Bmatrix}(-1)^i(-m)^{\overline{i}}\\ &=\sum_{i=0}^{n}\begin{Bmatrix}n\\i\end{Bmatrix}(-1)^i\sum_{j=0}^i\begin{bmatrix}i\\j\end{bmatrix}(-m)^j\\ &=\sum_{i=0}^n m^i\sum_{j=i}^{n}\begin{Bmatrix}n\\j\end{Bmatrix}\begin{bmatrix}j\\i\end{bmatrix}(-1)^{j-i} \end{aligned}$

莫比乌斯反演

式子是

$f_n=\sum_{d|n}g_d\iff g_n=\sum_{d|n}\mu_{\frac{n}{d}}f_d$

需要证明

$\begin{cases} \sum_{j = i} ^ n [j | n] \mu(\frac{n}{j})[i | j] = \delta(i, n)\\ \sum_{j = i} ^ n [j | n] [i | j] \mu(\frac{j}{i}) = \delta(i, n) \end{cases}$

我们来证明

$\sum_{j = i} ^ n [j | n] [i | j] \mu(\frac{j}{i}) = \delta(i, n)$

首先n不是i倍数的时候答案一定是0
假设n是i的倍数，那么

$\begin{aligned} &\ \ \ \ \ \sum_{j = i} ^ n [j | n] [i | j] \mu(\frac{j}{i})\\ &=\sum_{d = 1} ^ {\frac{n}{i}}[d | \frac{n}{i}] \mu(d)\\ &=\delta(n,i) \end{aligned}$