斯特林数、容斥和反演整理-白红宇

斯特林数、容斥和反演整理

阅读量：5057 次

发布时间：2019-06-12

本文共 7843 字，大约阅读时间需要 26 分钟。

斯特林数

第一类斯特林数

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_{l}(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} \]