我的集训队论文——对互异关系的容斥

· · 个人记录

写在前面

本文最初的 idea 是在笔者初中的时候想出来的，当时有一个数学组同学问了一道竞赛题（就是本文引入问题的 k=2 的特例）。当时花了两天左右编做法，写了一张 A4 纸的解答，并被评价为字丑（哭哭）。后来又学了一些计数技巧，并对这个方法的功能进行了一些拓展，大概就是本文所涉及的内容了。

当然，文中也提到，原问题是有一个基于组合观察的相对简单的做法的。但我们可以看到，本文的方法已经可以处理一些仅凭组合观察处理不了的问题。另外，本文并没有穷尽这一思路的可能性。借助本文的思路可能可以解决更多的问题，欢迎读者自行探究。

由于网上似乎并没有资料提到过这个东西，笔者就把它写到了论文里。写作的时候 ddl 比较紧，可能有大量笔误，还请见谅。

前置技能：本文内容涉及一些数学知识，但不太需要特别高深的数学技巧，只需要理解容斥原理即可。

问题引入

问题的提出

我们从一道经典问题引入。

问题 给定奇质数 p 和正整数 k，试计算 \{1,2,...,kp\} 有多少个 p 元子集的各元素之和是 p 的倍数？\square

这个问题有一个较为简单的解法，我们将其放在本节的最后。下面来讲解如何运用针对互异关系的容斥来解决本题。

初步转化

考虑另一个问题。

问题 给定奇质数 p 和正整数 k，试计算正整数 (x_1,x_2,...,x_p) 的组数，使得：

注意到上述这个问题实际上相当于原问题中集合元素之间的顺序也纳入到考量的范围中。对一个 p 元集合，任意排列它共有 p! 种方案，因而显见本问题的答案是原问题的 p! 倍。

考虑对条件 B 应用容斥原理。我们将在所有的 (i,j) 中钦定若干对，并强制这些对中的两个元素值相等。不妨将钦定关系看作一张图上的所有边，则全部限制条件等价于每个连通块内的元素值相等。不妨设 E_n 是 n 阶完全图 K_n 的边集，V(E) 表示钦定了 E 的边集内的相等关系后，符合条件 A、C 的 (x_1,...,x_p) 数量。则可知答案为：

\sum_{E\subset E_p}(-1)^{|E|}V(E)

V(E) 的计算以及维度的上升

观察 设 c(E) 表示 E 中的边形成的连通块数。那么

V(E)=\left\{\begin{aligned} kp, \quad c(E)=1\\ (kp)^{c(E)-1}\times k, \quad c(E) > 1\\ \end{aligned} \right .

证明 c(E)=1 时所有 p 个变量的取值全部相等，则这些变量都可以任意取值，共 kp 种。c(E)>1 时，全部连通分量大小都与 p 互质，我们可以任取一个连通块，对每一种其他连通块的任意取值（总计 (kp)^{c(E)-1} 种），该连通块变量的取值都被限定在一个唯一的剩余类里，也就是 k 种。\square

即使我们得到了这一公式，将其直接代入计算仍然有难度。我们需要一些巧妙的观察。注意到：对任意整数 t\in \{1,2,...,p-1\} 和边集 E，我们仿照上面的做法计算在钦定 E 中的相等关系后，\sum_{i=1}^px_i\equiv t\pmod p 的方案数，记为 V(E,t)。方便起见，下面记 V(E,0)=V(E)。可以观察到，当 c(E) > 1 时，V(E,t)=V(E,0)；当 c(E)=1 时 v(E,t)=0。也就是说，

V(E,t)=\left\{\begin{aligned} kp, \quad c(E)=1,t=0\\ 0, \quad c(E)=1,t>0\\ (kp)^{c(E)-1}\times k, \quad c(E) > 1\\ \end{aligned} \right .

我们再回到待解问题上。这次我们定义对每个剩余类都定义一个新问题，总共得到了 p 个问题，分别是问题 0,1,...,(p-1)：

问题 t 给定奇质数 p 和正整数 k，试计算正整数 (x_1,x_2,...,x_p) 的组数，使得：

记这 p 个问题的答案分别为 a_0,a_1,...,a_{p-1}。可知

a_t=\sum_{E\subset E_p}(-1)^{|E|}V(E,t)

不难得到：

如果能计算出

f_p=\sum_{E\subset E_p,c(E)=1}(-1)^{|E|}

的值，我们就可以解出 a_0 了。

计算 f

我们用反面考虑的方法来计算各项 f_n。假设 E 使得 c(E) > 1，即图不连通。我们枚举 1 所在的那个连通块的大小，即可完成计算。即：

观察 设 g_n=\sum_{E\subset E_n}(-1)^{|E|}。那么

f_n=g_n-\sum_{i=1}^{n-1}\binom{n-1}{i-1}f_ig_{n-i}

证明 枚举的 i 即为 1 所在连通块大小。需要从剩下 n-1 个点中选 i-1 个和 1 放进同一连通块，方法数为 \binom{n-1}{i-1}；接着图被分为两部分，一部分是强制连通的，其总和为 f_i；另一部分可以任意连边，总和为 g_{n-i}。即得上式。\square

注意到 g 大部分值都为 0。准确来说，g_1=1，g_i=0\ (i\geq 2)。这样我们可以解出：

f_n=0-(n-1)g_1f_{n-1}=-(n-1)f_{n-1}

由上即可得：

f_n=(-1)^{n-1}(n-1)!

这样我们终于求得了原问题的答案。因为 p 是奇数，故 (-1)^{p-1}=1。可以计算得到 a_0=\dfrac{p!\binom{kp}{p}+kp(p-1)(p-1)!}{p}。代回即可得到原问题的答案 =\dfrac{a_0}{p!}=\dfrac{\binom{kp}{p}+k(p-1)}{p}。

从上面的做法容易推出：对任意整数 c，若 c 不是 p 的倍数，则 \{1,2,...,kp\} 的 c 元子集中，模 p 余每种余数的集合个数都相等。证明留给读者。我们将在之后再详细分析这个问题。

与其他做法的对比

本题有一个简单的做法：考虑把全部 pk 个数排成一个 p 行 k 列的数表，第 i(1\leq i\leq p) 行第 j(1\leq j\leq k) 列填的数为 (j-1)k+i。对每一个 p 元子集，如果它的的元素不全在同一列，那么我们找到最小的出现了至少一个元素的列，并给这一列每个元素顺次向下挪 1 位，挪 2 位，……，挪 (p-1) 位（每次如果某个元素在最下面一行，挪动之后就变成这一列最上面一行的元素）。容易证明得到的 p 个集合的元素和恰好遍历模 p 的完系。故我们可以将这些集合分成 p 个一组，每组中元素和模 p 余 0,1,2,...,(p-1) 各一个。剩下还有 k 个集合没有考虑到，这些集合全部元素都在同一列。由于 p 是奇数，这 k 个集合的元素和都是 p 的倍数。这样我们就推得了和上面类似的结论，可以计算答案了。

这个做法的优点是简单明了、计算量很少，缺点是可扩展性不足。接下来我们将研究更多的问题，从而充分展现针对互异关系的容斥这一思路的丰富应用。

更多应用

关于异或

问题 给定正整数 n,k。集合 \{0,1,...,2^k-1\} 有多少 n 元子集异或和为 0？\square

我们沿用 2.2 \sim 2.4 中的思路。令 m=2^k，同样是考虑加入顺序，将问题变为 m 个，并容斥一个边集表示强制相等的元素对。令 V(E,t) 表示容斥的边集为 E 时，各元素异或和为 t 的方案数。可知

V(E,t)=\left\{\begin{aligned} m^{c(E)}, \quad E\ \text{中全部连通块大小均为偶数},t=0\\ 0, \quad E\ \text{中全部连通块大小均为偶数},t>0\\ m^{c(E)-1},\quad E\ \text{中至少一个连通块大小为奇数}\\ \end{aligned} \right .

设 a_t 表示问题 t 的答案。可得：

a_0-a_1=\sum_{E\subset E_n,E\ \texttt{中全部连通块大小均为偶数}}(-1)^{|E|}m^{c(E)}

不妨记上述结果为 h_n。我们来推导计算 h_n 的方法。同样，我们来枚举 1 所在的连通块大小，可得：

h_n=\sum_{2\leq i\leq n,2\mid i}m\binom{n-1}{i-1}f_ih_{n-i}

其中 f_i 表示大小为 i 的连通图中，偶数边数的图的数量减去奇数边数的图的数量。由 2.4 中的结果知 f_i=(-1)^{i-1}(i-1)!。由于 i 都是偶数，可以将 f_i=-(i-1)! 代入得：

h_n=\sum_{2\leq i\leq n,2\mid i}-m(i-1)!\binom{n-1}{i-1}h_{n-i}=\sum_{2\leq i\leq n,2\mid i}-m(i-1)!\binom{n-1}{i-1}h_{n-i}=(n-1)!\sum_{2\leq i\leq n,2\mid i}-m\dfrac{h_{n-i}}{(n-i)!}

令 h(x)=\sum_{i=0}\dfrac{h_i}{i!}x_i 为 h 的指数型生成函数。可得：

h'=-m(x+x^3+x^5+\cdots)h=-\dfrac{m}{2}(\dfrac{1}{1-x}-\dfrac{1}{1+x})h

可以解得：

h(x)=\mathrm{e}^{-\frac{m}{2}({-\ln(1-x)-\ln(1+x)})+C}=\mathrm{e}^C\times (1-x^2)^{\frac{m}{2}}

由于 h_0=1，可以得到 C=0。故

h(x)=(1-x^2)^\frac{m}{2}

故

h_n=\left\{\begin{aligned} (-1)^{n/2}\binom{m/2}{n/2}, \quad n\equiv 0\pmod 2\\ 0, \quad n\equiv 1\pmod 2\\ \end{aligned} \right .

代回即可求得答案。可以发现，用传统的做法很难求得答案。

对第 2 节结论的拓展

问题 给定奇质数 p 和正整数 k,n，试计算 \{1,2,...,kp\} 有多少个 n 元子集的各元素之和是 p 的倍数？\square

用 2.5 中提到的画数表的方法，可以简单得到：当 p\nmid n 时，元素和落入各剩余类的数量相等；p\mid n 时，落入剩余类 0 的比其他类要多 \binom{k}{n/p}。下面我们来利用容斥的方法验证这一结论。

大部分定义同第 2 节。方便起见，令 m=kp。由于 n 可能大于 p，我们需要补充 V(E,t) 的定义：

V(E,t)=\left\{\begin{aligned} m^{c(E)}, \quad E\ \text{中全部连通块大小均为}\ p\ \text{的倍数},t=0\\ 0, \quad E\ \text{中全部连通块大小均为}\ p\ \text{的倍数},t>0\\ m^{c(E)-1},\quad E\ \text{中至少一个连通块大小不为}\ p\ \text{的倍数}\\ \end{aligned} \right .

仿照 3.1 节中的思路，我们来计算 h_n=a_0-a_1。

h_n=\sum_{p\leq i\leq n,p\mid i}(-1)^{i-1}m(i-1)!\binom{n-1}{i-1}h_{n-i}=\sum_{p\leq i\leq n,p\mid i}(-1)^{i-1}m(i-1)!\binom{n-1}{i-1}h_{n-i}=(n-1)!\sum_{p\leq i\leq n,p\mid i}(-1)^{i-1}m\dfrac{h_{n-i}}{(n-i)!}

同样令 h(x)=\sum_{i=0}\dfrac{h_i}{i!}x_i 为 h 的指数型生成函数。可得：

h'=m(x^{p-1}-x^{2p-1}+x^{3p-1}-x^{4p-1}+\cdots)h=m\dfrac{x^{p-1}}{1+x^p}h

可以解得

h=\mathrm{e}^{\frac{m}{p}\ln(1+x^p)+C}=\mathrm{e}^C\times (1+x^p)^{m/p}

显见 C=0。故可得

h_n=\left\{\begin{aligned} \binom{m/p}{n/p}n!, p\mid n\\ 0, \quad p\nmid n\\ \end{aligned} \right .

这与我们已经得到的结果是一致的。

结语

本文内容到此告一段落。欢迎广大读者继续研究这个想法，期待能得到更有价值的结果！