详细揭秘：详细揭秘：集合划分容斥的容斥系数

宝宝都会的集合划分容斥，从多项式角度推导容斥系数

参考文献：

详细揭秘：集合划分容斥的容斥系数

2024.12.23 闲话

浅谈集合划分容斥

容斥系数简单来说就是当我们产生贡献的集合里面有极大等限制词语时用来拆掉这个限制所人为构造的一组系数

我们现在有两种算法

我们希望在 2 的做法中加入容斥系数使得答案和 1 算出来一样

设当前等价类合并（不限制极大的元素合并成极大的元素）的函数为 \(G\)，而在 1 中的极大集合的贡献系数是 \(F\)

那么我们构造的函数 \(H\) 满足 \(G(H(x))=F(x)\) 答案就正确了

原因就是你把所有的 \(H\) 拼起来等于它应该的系数，和正常容斥一个道理

例题

首先划分等价类，找到我们要容斥的东西，肯定是要对 \(0\) 的长度进行容斥

那么有 \(F(x)=x,G(x)=\dfrac{1}{1-x}-1\)

可以发现最终 \(H(x)=\dfrac{x}{1+x}\)

那么就可以直接做了，答案的生成函数是 \(\dfrac{1}{1-H(x)-mx}\)

首先划分等价类，肯定划分一段连续的链是等价类

考虑如何计算，发现 \(k\) 段生成树的方案是 \(\prod\limits_i c_i n^{k-2}\)

显然合并是 \(G(x)=\dfrac{1}{1-x}-1\)，\(F(x)=\dfrac{x^2}{1-x}\)

于是 \(H(x)\) 可以简单求出，答案的生成函数就是 \(\dfrac{1}{1-\sum\limits_i ni [x^i]H(x)}\)

这里加系数是没有问题的，因为合并的时候限制了连接方式，每个合并的依然只会被多算一次

这个题很经典了，考虑划分等价类是 \(\text{ABCAB}\) 这样的段，因为段长最大是 \(2\)，因此生成函数是

\(F(x)=x+x^2,G(x)=\dfrac{1}{1-x}-1\) 容易知道容斥系数 \(H(x)=1-\dfrac{1}{1+x+x^2}\)

那么我们带上容斥系数连续段的生成函数是 \(\dfrac{x+y+z-3xyz}{1-xyz}\)

答案是 \([x^ay^bz^c]\dfrac{1-xyz}{1-x-y-z+2xyz}\)，手动提取系数即可