0%

浅谈集合划分容斥

这里将浅显的介绍标题里的东西,以及他的特例:斯特林反演。

例题:计算将 $n!$ 分解为 $n!=\prod\limits_{i=1}^k a_i$,其中 $a_i$ 两两不同的方案数。$n\leq 10^4,k \leq 30$。

我们考虑用容斥来处理 $a_i$ 两两不同的限制。考虑现在有一组分解方案 $\prod b_i$,我们将其中相同的数字划为一个等价类,则合法的方案都是等价类个数等于 $k$ 的方案。我们考虑枚举每个等价类的大小,注意这里大小相同的等价类是没有区别的。然后对于 $n!$ 的唯一分解 $\prod p_i^{q_i}$ 考虑 $p_i,q_i$,对于每个质因子将它的指数用完全背包划分到各个等价类中,然后我们就得到了在当前钦定等价类分布情况下的方案数。

接下来要做的事情是调配容斥系数。首先显然这个容斥系数会跟等价类大小有关。我们希望,一个方案被计算的次数是 $\prod f_{size}$ 次,其中 $size$ 是当前方案里每个极大等价类的大小。显然要满足 $f_1=1,f_{i>1}=0$。观察到,在上面我们钦定方案的过程里,一个真实情况的里的极大等价类的每种划分都会被枚举到,如果以类似的方式给钦定方案中每个等价类分配一个容斥权值 $g_{size}$ 的话,我们会有 $F(x)=\exp G(x)$(分别是两个数列的 EGF),因为 $\exp$ 的组合意义就相当于是将一些元素集合按有标号的方式拼合,其实就等价于我们上面提到的划分。那么我们还需要令 $f_0=1$,然后就可以得到 $G(x)=\ln F(x)=\ln (1+x)=\sum\limits_{i=0} (-1)^{i+1}\frac{x^i}{i}$,便有 $g_i= (-1)^{i+1} (i-1)!$。

扩展

将原本的元素两两不同的限制改为恰好 $t$ 个等价类,还能套用之前的方法吗?

不能。因为我们之前的方法,是基于 “合法情况每个等价类大小为 $1$” 的前提,而当我们无法用等价类大小的限制来表示需要的限制时,之前的方法也就失效了。

考虑升维,我们用一个占位符 $y$ 来表示等价类个数,那么期望一组真实的划分方案中每个等价类贡献 $y$ 的权值,则最后要求的答案即是所得幂级数的第 $t$ 次项系数。在插值后,可以直接套用上面的容斥系数计算方法。

UPD:斯特林反演

其实斯特林反演本质上是斯特林数的推导产物。

最基本的斯特林反演公式:
$$
f_n=\sum\limits_{i=0}^n\begin{Bmatrix}n \ i\end{Bmatrix} g_i \
g_n = \sum\limits_{i=0}^n (-1)^i \begin{bmatrix} n \ i \end{bmatrix} f_i\
$$
基于平时的经验,我们赋予 $f_n,g_n$ 组合意义:$g_n$ 是恰好 $n$ 个等价类的方案数,$f_n$ 是钦定了 $n$ 个等价类的方案数。

考虑这个公式的证明过程(应用反转公式)
$$
g_n=\sum\limits_{i=0}^n [i=n] g_i \
=\sum\limits_{i=0}^n g_i \sum \limits_{j=i}^n (-1)^{n-j} \begin{bmatrix}n \j\end{bmatrix} \begin{Bmatrix} j\i \end{Bmatrix} \
= \sum\limits_{j=0}^n (-1)^{n-j} \begin{bmatrix}n \j\end{bmatrix} \sum\limits_{i=0}^j \begin{Bmatrix} j\i \end{Bmatrix}g_i
$$
假设这是个集合划分容斥,那么我们和式里枚举的 $i$ 是恰好有多少个等价类,并将这些等价类用钦定划分成了 $j$ 个等价类,对应上面的爆搜,然后因为方案数只跟等价类个数相关,而跟等价类具体长啥样无关,就可以直接用第二类斯特林数来划分,得到钦定的权值。至于在钦定的等价类方案中每个大小为 $s$ 的等价类会贡献 $(-1)^{s+1} (s-1)!$ 的容斥系数这回事,会发现这个 $(s-1)!$ 本质上是长为 $s$ 的圆排列个数,也就是说对于一种将 $n$ 个元素钦定划分成 $j$ 个等价类时贡献的容斥系数是每个等价类里元素个数的圆排列的方案数之乘积再乘上 $(-1)^{n-j}$,前面也说了方案数只跟 $j$ 有关,因此对容斥系数求和就会得到 $(-1)^{n-j} \begin{bmatrix}n \j\end{bmatrix}$。

至此我们就从集合划分容斥的角度介绍了斯特林反演。可以发现他们之前的关系与 “二项式反演和集合容斥” 的关系十分类似,只是这里的形式复杂了许多。因此当计算“钦定划分等价类”情景的方案数需要知道具体划分情况的时候,我们就需要集合划分容斥。当这个方案数与具体划分情况无关,只跟划分出多少个等价类有关的时候就可以使用斯特林反演,本质上就是一个东西。