组合数学学习笔记

容斥原理

简单容斥

统计方案时经常会因为状态的设计而不得不算出重复的方案，故而需用容斥原理将答案改变为正确的值。

最简单的形式，即小学我们就学过的数数问题。

即 你有 $k$ 个属性， 你想知道满足属性集合 $S$ 的数有哪些， 查询这个函数 $f(S)$，总有 $f(\varnothing)=0$

我们曾经学过的知识说，答案就是

$\sum_{S \subseteq U}f(S)(-1)^{|S|+1}$

推广到任意 $k$ 都是成立的。

考虑对于每一个实际的物品，他的属性会被如何统计到。

对于一个有 $n$ 个属性的物品，当 $n = 0$ 时贡献为 $0$

当 $n > 0$ ，枚举这些属性会被哪些组合统计。

即

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

这时所有的属性恰被统计一次。

容斥的推广

因此可以推广。

假设我们有属性集合 $k$， 有 $q(S)$ 集合 $S$ 里面的物品个数， $g(k)$ 表示满足 $k$ 个属性的物品的贡献，$f(x)$ 是容斥系数。

最后我们要求 $\sum_{S \subseteq U}q(S)f(|S|)$

考虑每个物品对答案的贡献，对于一个有 $n$ 个属性的物品， 其贡献就是。

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

这个式子可以 $n^2$ 计算。

我们发现通过一系列 钦定， 我们将原先需要指数枚举的集合，变为了枚举属性集合的大小来大大降低复杂度。

计算容斥系数

对于计算 容斥系数 $f$

将上述式子展开即可，显然有

$\frac{g(n)}{n!}=\sum_{i=0}^n\frac{1}{(n-i)!}\frac{f(i)}{i!}$

这是一个十分显式的减法卷积形式。

方程的解

求

$\sum_{i=1}^nx_i=y$

的若干组解。

直接插板答案自然是

$\binom{n+y-1}{n-1}$

考虑有 $y$ 个小球，可以不选，插 $n - 1$ 个板构成这些数。

考虑有 $n$ 个属性，规定 $x_i \ge k_i + 1$，求方案数。

我们这里的属性是与题中的限制相反的，我们要求的是满足至少一个属性的方案数，用全集减去他。

令 $x_i=x_i+k_i+1$ 就是不满足限制的。

我们就可以计算 $f(S)$ 表示集合 $S$ 中满足限制的方案数

$f(S)=\binom{n+y-\sum_{i\in S}(k_i+1)}{n-1}$

然后直接容斥即可。

$\begin{aligned} T&=\sum_{S \subseteq U}(-1)^{|S|}f(S)\\ &=\sum_{S \subseteq U}(-1)^{|S|}\binom{n+y-\sum_{i\in S}k_i+1}{n-1} \end{aligned}$

我们发现，所有的反演都是容斥下容斥系数的特殊化，容斥系数可以是二项式系数，斯特林数等各种系数。

子集容斥

等我寒假把数树写了一定更！

由于莫比乌斯函数的定义，莫比乌斯反演就是在因子多重集上的反演。

二项式反演

想自己写一点证明。

一个引理。

$\begin{aligned} &\sum_{i=k}^n(-1)^{n-i}\binom{n}{i}\binom{i}{k}=\epsilon(n=k)\\ =&\sum_{i=k}^n(-1)^{n-i}\frac{n!}{i!(n-i)!}\frac{i!}{k!(i-k)!}\\ =&\sum_{i=k}^n(-1)^{n-i}\frac{n!}{k!}\frac{(n-k)!}{(i-k)!(n-i)!}\\ =&\sum_{i=k}^n(-1)^{n-i}\binom{n}{k}\binom{n - k}{i - k}\\ =&\binom{n}{k}\sum_{i=0}^{n-k}(-1)^{n-i-k}\binom{n-k}{i}\\ =&\binom{n}{k}\sum_{i=0}^n(-1)^{n-i}\binom{n}{i} \end{aligned}$

讨论当 $n > k$ 时 $n$ 得奇偶性， 发现总会容斥为 $0$ ，即值为 $[n = k]$

二项式反演得证明即构造两个矩阵，他们互逆，用以上原理乘起来就是一个单位矩阵。

还可以用这两个函数得 $EGF$ ，不需要使用上面的引理， 由于 $EGF$ 的卷积展开就是 二项卷积， 将其卷起来展开并移项，即为二项式反演的形式。

具体来说设 $f_n$ 和 $g_n$ 对应的生成函数是 $f(x)$ 和 $g(x)$

有

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

由 $EGF$ 的定义显然可以发现

$g(x)=f(x)e^x$

可以得到

$f(x)=g(x)e^{-x}$

展开即可

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

题目

集合计数

考虑设 $f(k)$ 为交集恰好为 $k$ 的方案数， $g(k)$ 为交集至少为 $k$ 的方案数。

容易写出

$g(k)=\binom{n}{k}2^{2^{n-k}-1}$

即考虑钦定选其中 $k$ 个，剩下的所有集合无所谓的方案数。

容易发现对于任意的 $k > 1$ 的交集 会被统计若干次答案。

考虑对于钦定的一个 $k$ 在从若干个里面挑选 $k$ 即他的贡献是

$\sum_{i=k}^n\binom{i}{k}$

可以写出相应的式子来。

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

因此可以用二项式反演来省略掉推到容斥系数的部分。

我们同样可以直接考虑这个题。

我们钦定 $k$ 个元素为交集。

现在要求 $m = n - k$ 个元素，任取集合，交集为空的方案数。

用全集减去， 全集为 $2^{2^{m}}-1$ 。

考虑再次钦定交集大小，即又用钦定的方式代替了枚举集合的指数复杂度，因为在这道题中属性集合 $k$ 通过钦定贡献是相同的。

这就是求有多少物品是至少有一个属性的，直接容斥即可。

$\binom{n}{k}(2^{2^{m}-1}+\sum_{i=0}^m(-1)^i\times(2^{2^{m-i}}-1))$

已经没有什么好害怕的了

假设对应 $x$ 组 $a > b$ ，则有 $n - x$ 组 $b > a$ ，即 $x - (n - x) = k$ 则要求 $x = \frac{n+k}{2}$

考虑 $dp$ 设 $g_{i,j}$ 表示 $a$ 的前 $i$ 个位置， 匹配上 $j$ 个。

转移是平凡的。

$\begin{aligned} &g_{i,j}=g_{i,j}+g_{i-1,j}\\ &g_{i,j}=g_{i,j}+g_{i-1,j-1}\times(k-j) \end{aligned}$

其中 $k$ 为 $a_i$ 在 $b$ 中的第一个 $a_i < b_k$ 的位置， 可以预处理得到。

考虑要求的 至少匹配 $k$ 对，剩下的任意填是个阶乘，因此能得到。

$g(k)=g_{n,k}\times(n-k)!$

考虑每次匹配到的 $k$ 对 对答案的贡献，在考虑小于 $k$ 对的时候都会贡献到。

可以理解为在 $dp$ 过程中，对于第二个序列的每个大小为 $j$ 的子集是没有差别的，都会进行若干次贡献，同样对于 第一个序列指针向右的过程中他的贡献依然重复。因此在用 $f$ 描述 $g$ 的时候需要组合数。

即我们熟悉的二项式反演的形式。

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

Positions in Permutations

我们发现这和上一道题基本一样，因此不难想到他集合中的贡献也是其钦定的组合数。

因此可以直接使用二项式反演。

考虑求出 钦定匹配了 $j$ 个， 剩下随意分配的方案数，为 $g(x)$。

则答案 $f(x)$ 为

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

和上一个题不同，我们影响当前能不能填需要知道当前这个数能否填，所以记录到状态里面。

设 $f_{i,j,0/1,0/1}$ 表示前 $i$ 个位置， 钦定匹配了 $j$ 个， 选不选 $i$ 这个数， 选不选 $i+1$这个数

转移也是比较平凡的。

$i$ 这一位要转移 ， 放的是 $i - 1$，只需要保证上一 位不放 $i - 1$

$\begin{aligned} &f[i][j][0][0]+=f[i-1][j-1][0][0]\\ &f[i][j][1][0]+=f[i-1][j-1][0][1] \end{aligned}$

$i$ 这一位要转移 ， 放的是 $i + 1$，上一位可以随意放。

$\begin{aligned} &f[i][j][0][1]+=f[i-1][j-1][0][0]+f[i-1][j-1][1][0]\\ &f[i][j][1][1]+=f[i-1][j-1][0][1]+f[i-1][j-1][1][1] \end{aligned}$

$i$ 这一位不转移，看情况转移即可。

$\begin{aligned} &f[i][j][0][0]+=f[i-1][j][0][0]+f[i-1][j][1][0]\\ &f[i][j][1][0]+=f[i-1][j][0][1]+f[i-1][j][1][1] \end{aligned}$

最后拿 $dp$ 出来的结果乘个阶乘即可求出 $g$。

染色

设 $g(k)$ 表示 $n$ 个位置中至少有 $k$ 种颜色出现了 $S$ 次的方案数。

$f(x)$ 表示 $n$ 个位置中至少有 $k$ 种颜色出现了 $S$ 次的方案。

钦定选 $k$ 个颜色， 他们出现的次数都是 $S$ ，剩下的任选，方案是

$\begin{aligned} &\binom{n}{k}\prod_{j=0}^{k-1}\binom{n-j\times s}{s}(n-k\times s)^{m-k}\\ =&\binom{n}{k}\frac{n!}{(s!)^k(n-sk)!}(n-k\times s)^{m-k} \end{aligned}$

考虑计算重复的贡献。

对于 $f(x_1)$ 来讲， 在 $g(x_2)$ 进行任意钦定 $x_2$ 合法的时候， 都会对 $x_1$ 有贡献。

具体例子， 全集 $U = \{a,b,c,d\}$, $g(4)$ 在 $f(3)$ 钦定 $\{a,b,c\},\{a,b,d\},\{a,c,d\},\{b,c,d\}$ 的时候，都会对其有贡献。

因此符合我们熟知的式子

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

其实上面的所有题的贡献都举这种例子可以最好的解释。

就可以进行二项式反演了。

可能还需要点多项式来辅助计算，这都是小问题

$\begin{aligned} f(k)=&\sum_{i=k}^n(-1)^{i-k}\binom{i}{k}g(i)\\ =&\sum_{i=k}^n(-1)^{i-k}\binom{i}{k}g(i)\\ =&\sum_{i=k}^n(-1)^{i-k}\frac{i!}{k!(i-k)!}g(i)\\ =&\sum_{i=k}^n\frac{(-1)^{i-k}}{(i-k)!}\frac{i!}{k!}g(i)\\ =&\frac{1}{k!}\sum_{i=k}^n\frac{(-1)^{i-k}}{(i-k)!}i!g(i) \\ \end{aligned}$

很明显能卷一下， 令 $h(i)=\frac{(-1)^i}{i!}$, $z(i)=i!g(i)$

$f(k)\times k!=\sum_{i=k}^nh(i-k)z(i)$

朴素的减法卷积即可。

斯特林数

第二类斯特林数·行

对第二类斯特林数考虑这样一个式子。

$m^n=\sum_{k=0}^m\binom{m}{k}{n \brace k}k!$

其组合意义为，左边的是盒子有标号可以非空。枚举非空盒子个数，组合数是枚举非空，阶乘是无标号。

考虑二项式反演。

$\begin{aligned} f(n)&=\sum_{i=0}^n\binom{n}{i}g(i)\\ g(n)&=\sum_{i=0}^n(-1)^{n-i}\binom{n}{i}f(i) \end{aligned}$

即令$f(m)=m^n$ $g(m)=m!{n\brace m}$

则

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

考虑展开组合数

$\begin{aligned} {n\brace m}&=\sum_{i=0}^n(-1)^{m-i}\frac{m!i^n}{i!(m-i)!m!}\\ &=\sum_{i=0}^n\frac{(-1)^{m-i}}{(m-i)!}\times\frac{i^n}{i!} \end{aligned}$

卷！

还有一种考虑方式。

还是最初的式子，我们把组合数展开。

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

发现这就是一个下降幂多项式。

斯特林数就是其系数，所以我们可以先处理出点值$idk$，在将点值改为系数即可。

第二类斯特林数·列

求出一列斯特里数，这里给出使用生成函数的推倒。

我们考虑当只有一个盒子的时候，我们容易写出他的 $EGF$ 为 $e^z-1$， 代表的是数列 $\left<0,1\dots\right>$ 的 $EGF$

考虑到有 $k$ 个盒子， 所以答案的生成函数 $F$ 为 $G^k=(e^z-1)^k$

注意到上面的操作中 盒子也是区分开的， 并不满足斯特林数中相同集合的定义， 因此答案除去一个 $k!$ 即可。

既有式子

$\begin{aligned} &k!\sum_{i=0}^m {i \brace k}\frac{x^i}{i!}=(e^z-1)^k \end{aligned}$