数组合数学

组合数学4-容斥原理,鸽巢原理

字数统计: 3.1k字   |   阅读时长: 14分
, ,

摘要: 组合数学：容斥原理、鸽巢原理

【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】
我的网站：潮汐朝夕的生活实验室
我的公众号：算法题刷刷
我的知乎：潮汐朝夕
我的github：FennelDumplings
我的leetcode：FennelDumplings

在 组合数学1-排列组合 中我们详细梳理了组合数学的基本模型以及相关公式；在 组合数学2-母函数,递推关系 中我们详细学习了母函数、递推关系；在文章 组合数学3-特殊计数序列,指数型母函数 中我们详细学习了指数型母函数、特殊计数序列。

本文我们看一下组合数学的第四部分，容斥原理和鸽巢原理，主要内容如下：

  • 容斥原理
    • 加法法则
    • 容斥原理的证明
      • De Morgan 定理
    • 容斥原理的应用
  • 鸽巢原理
    • n + 1 个鸽子飞 n 个巢，至少 1 巢有 2 只
    • kn + 1 个 鸽子飞 n 个巢，至少 1 巢有 k + 1 只
    • 大量例子(难点是什么是鸽，什么是巢)
    • 韩信点兵
    • 中国剩余定理
    • 六人行
    • Ramsey 数

容斥原理

加法法则

$|A| = m, |B| = n$，如果 $A \cap B = \varnothing$，则 $|A \cup B| = m + n$。

容斥原理

证明用数学归纳法即可，过程中用到 De Morgan 定理：

$A_{1}, A_{2}, .. A_{n}$ 为 $U$ 的子集，则

De Morgan 定理的证明也是数学归纳法。

应用1 : 排列组合

  • 例题1：abcd 构成的 n 位串，abc 均至少出现一次的串的数目是多少。

$A_{1}$: A 不出现的串的数量
$A_{2}$: B 不出现的串的数量
$A_{3}$: C 不出现的串的数量

再求 $|A_{1} \cap A_{2}|$, $|A_{1} \cap A_{3}|$, $|A_{2} \cap A_{2}|$

再求 $|A_{1} \cap A_{2} \cap A_{3}|$

然后用容斥原理计算结果。

  • 例题2：abcdef 的全排列中不出现 ace 和 df 的个数

$S$: 全排列个数，$|s| = 6!$
$A_{1}$: ace 相连的个数
$A_{2}$: df 相连的个数

答案为 $|S| - |A_{1}| - |A_{2}| + |A_{1} \cap A_{2}|$

应用2： 数论

  • 例题1：[1, 500] 中能被 3, 5 整除的个数

$A_{1}$: 被 3 整除的个数, $|A_{1}| = \lfloor\frac{500}{3}\rfloor$
$A_{2}$: 被 5 整除的个数, $|A_{1}| = \lfloor\frac{500}{5}\rfloor$

$|A_{1} \cup A_{2}| = |A_{1}| + |A_{2}| - |A_{1} \cap A_{2}| = \lfloor\frac{500}{3}\rfloor + \lfloor\frac{500}{5}\rfloor - \lfloor\frac{500}{15}\rfloor$

题解参考 最大公约数算法以及C++17组件。

  • 例题3：不超过 120 的质数个数

$120 < 11^{2}$, 因此 120 以内的数要是有因子，无非 2, 3, 5, 7

$A_{1}$: 120 以内 2 的倍数，$|A_{1}| = \lfloor\frac{120}{2}\rfloor = 20$
$A_{2}$: 120 以内 3 的倍数，$|A_{2}| = \lfloor\frac{120}{3}\rfloor = 12$
$A_{3}$: 120 以内 5 的倍数，$|A_{3}| = \lfloor\frac{120}{5}\rfloor = 8$
$A_{4}$: 120 以内 7 的倍数，$|A_{4}| = \lfloor\frac{120}{7}\rfloor = 8$

$|A_{1} \cap A_{2}| = \lfloor\frac{120}{2 \times 3}\rfloor$

类似地再依次计算各个交集即可:

$|A_{1} \cap A_{3}|$
$|A_{1} \cap A_{4}|$
$|A_{2} \cap A_{3}|$
$|A_{2} \cap A_{4}|$
$|A_{3} \cap A_{4}|$

$|A_{1} \cap A_{2} \cap A_{3}|$
$|A_{1} \cap A_{2} \cap A_{4}|$
$|A_{2} \cap A_{3} \cap A_{4}|$

$|A_{1} \cap A_{2} \cap A_{3} \cap A_{4}|$

更详细的内容参考 素数筛。

应用3: 欧拉函数

$\phi(n) :=$ 小于等于 n 且与 n 互质的正整数的个数。

由算术基本定理有：$n=p_{1}^{a_{1}}p_{2}^{a_{2}}…p_{k}^{a_{k}}$

定义 $A_{i}$ : 1~n 中为 $p_{i}$ 倍数的数的集合, 于是 $|A_{i}| = \frac{n}{p_{i}}, i=1,2,…,k$

对于两个集合 $A_{i}$、$A_{j}$ 的交集，$p_{i} \neq p_{j}$ 时， $|A_{i} \cap A_{j}| = \frac{n}{p_{i}p_{j}}$。多个集合的交集，公式类似。

欧拉函数的性质：

  • (1) $\phi(n)$ 是积性函数：当 n 和 m 互质时，$\phi(mn) = \phi(n)\phi(n)$
  • (2) n 为质数则 $\phi(n) = n - 1$
  • (3) n 为奇数则 $\phi(2n) = \phi(n)$
  • (4) 若 a 为质数, $b \equiv a \mod 0$, 则 $\phi(ab) = a\phi(b)$
  • (5) n 为 $p^{k}$ 则 $\phi(n) = p^{k} - p^{k-1}$
  • (6) $\sum\limits_{d|n}\phi(d) = n$

欧拉函数可以用线性筛来求，参考文章 素数筛。

题解参考 力扣372-超级次方。

应用4 : 不定方程

考虑问题：求 $x_{1} + x_{2} + x_{3} = 15$ 的非负整数解。

不定方程的非负整数解可以抽象成可重组合。可以用隔板法或直接套公式 $\dbinom{3 + 15 - 1}{15}$，参考 组合数学1

当对 $x_{1}, x_{2}, x_{3}$ 有更强约束的时候，例如 $0 \leq x_{1} \leq 5, 0 \leq x_{2} \leq 6, 0 \leq x_{3} \leq 7$，传统的隔板法和公式法就不能用了。

但是可以用容斥原理：

$A_{1}$: $x_{1} \ge 6$ 的解, $x_{1} - 6 + x_{2} + x_{3} = 15$
$A_{2}$: $x_{2} \ge 7$ 的解, $x_{1} - 7 + x_{2} + x_{3} = 15$
$A_{3}$: $x_{3} \ge 8$ 的解, $x_{1} - 8 + x_{2} + x_{3} = 15$

$|A_{i}|$ 均可套传统方法求出。

最终要求 $|\overline{A_{0}} \cap \overline{A_{1}} \cap \overline{A_{2}}|$

应用5 : 带障碍格路

题解参考：组合数

应用6 : 第二类 Stirling 数和错排问题

在 组合数学3 中，我们学习了错排问题和第二类 Stirling 数，可以抽象成放球模型，并通过指数型母函数推出了错排问题的通项公式：

以及通过放球模型和指数型母函数推出了第二类 Stirling 数的通项公式：

以下从容斥原理的角度解释：

(1) 第二类 Stirling 数的容斥原理解释

其对应的放球模型为：n 个有区别的球，放入 m 个无区别的盒，不能有空盒。

$A_{i}$: 第 i 个盒子为空的集合

与用指数型母函数推导时的做法一样考虑, n 个有区别的球，放入 m 个有区别的盒。全体为$|S|$

  • $|S| = m^{n}$
  • $|A_{i}| = (m - 1)^{n}$，共 $\dbinom{m}{1}$ 个
  • $|A_{i} \cap A_{j}| = (m - 2)^{n}$，共 $\dbinom{m}{2}$ 个

要求的是 $|\overline{A_{1}} \cap \overline{A_{2}} \cap .. \cap \overline{A_{n}}|$

(2) 错排问题的容斥原理解释

$A_{i}$: i 在第 i 位上的全排列。 $|A_{i}| = (n - 1)!$
$A_{i} \cap A_{j} = (n - 2)!$

鸽巢原理

鸽巢原理直观理解就是下面这两件事：

  • n + 1 个鸽子飞 n 个巢，至少 1 巢有 2 只。
  • kn + 1 个 鸽子飞 n 个巢，至少 1 巢有 k + 1 只。

例子

  • 30人，至少多少人同月出生
  • 哈希冲突为何无法避免
  • 10双蓝鞋，12双白鞋，随机取几次可以凑成一对
  • n + 1 个正整数，全都 $\leq 2n$。求证：(1) 一定有 2 个数互质；(2) 一定有两个数，其中一个是另一个的倍数
  • $a_{1}…a_{100}$ 是由 1, 2 组成的序列，已知从任意数开始的连续10个数的和 $\leq 16$，即 $a_{i} + … + a_{i+9}, (1 \leq i \leq 91)$。求证：至少存在 h > k 使得 $a_{h} + … + a_{k} = 39$

记 $S_{j} = \sum\limits_{i=1}^{j}a_{i}, (j=1,2,…,100)$，$S_{1} < S_{2} < … < S_{100}$

其中：

$S_{100} + 39 \leq 160 + 39 = 199$, 作序列 $S_{1}, S_{2}, …, S_{100}, S_{1} + 39, …, S_{100} + 39$，共 200 项。其中最大项为 199，则其中必有两项是相等的。

又因为 $S_{i}$ 单调，因此相等的两项一定有意向来自$S_{1}, S_{2}, …, S_{100}$, 另一项来自 $S_{1} + 39, …, S_{100} + 39$。 即 $S_{k} = S_{h} + 39$。

  • 六合彩：从1~49中摇6个数，以及第七个特别号，开奖的正选号码中至少有两个的第一位一样。

鸽巢原理可以证明至少有两个的第一位一样，但鸽巢原理无法给出具体是哪两个。

  • 20件衬衫，3种颜色(4, 7, 9)，取多少件有至少4件同色。

韩信点兵

韩信点兵：

3人一排余2人
5人一排余3人
7人一排余2人

这是同余式:

解这个同余式，有以下两种方法：

(1) 列出 $3a+2, 5b+3, 7c+2$ 这三个集合，取交集

(2) 构造法

记 s 是 5 和 7 的公倍数，且除 3 余 1， s=70，则 2s 是 5,7 的公倍数且除 3 余 2。

记 t 是 3 和 7 的公倍数，且除 5 余 1， t=21，则 3t 是 3,7 的公倍数且除 5 余 3。

记 h 是 3 和 5 的公倍数，且除 7 余 1， h=15，则 2t 是 3,5 的公倍数且除 7 余 2。

则 $2s + 3t + 2h = 233$ 满足同余式。若要找最小的，答案为 233 % (3*5*7)。

中国剩余定理

m 和 n 为互质正整数，对任意非负整数 a, b($a < m, b < n$)，必存在正整数 x，使得下式成立：

证明方法是鸽巢原理：

考虑 n 个整数：$a, m+a, 2m+a, …, (n-1)m+a$，均模 m 余 a(满足第一式)

其中若存在模 n 余数相同的两个数，则不能保证对任意 b 成立。

若此 n 个数模 n 均不同，则可以保证对任意 b 成立。

假设有相同的情况：$im+a$ 和 $jm+a$, $(0 \leq i \leq j \leq n - 1)$

$(j - i)m = (q_{j} - q_{i})n$，n 是 (j - i)m 的因子，但是 m, n 互质并且 $0 \leq i \leq j \leq n - 1$，n 不可能是 $(j - i)m$ 的因子。

中国剩余定理的推广

$m_{1}, …, m_{k}$ 两两互质：$gcd(m_{i}, m_{j}) = 1, i \neq j$

则以下同余式有解：

六人行

任意六个人，要么 3 个人互相认识，要么 3 个人互相不认识。

这可以抽象为完全图的染色问题：完全图 $K_{6}$，对边进行红/蓝着色，则存在同色的完全子图$K_{3}$。

证明方法：决策树+鸽巢

Ramsey 数

Ramsey数：$R(p, g)$

$n \ge R(p, g)$时，$K_{n}$ 的红蓝二着色必有红 $K_{p}$ 或蓝 $K_{g}$。

对于六人行问题，相当于 $R(3, 3) = 6$。

$n < R(p, g)$时，$K_{n}$ 的红蓝二着色不能保证必有红 $K_{p}$ 或蓝 $K_{g}$。

已知的 Ramsey 数非常少，至今仍是组合数学前沿问题。例如：

$R(3, 3) = 6$；$R(3, 4) = 9$；$R(4, 4) = 8$

$R(5, 5)$ 还未知，仅知道在 43 到 49 之间。因为验证涉及到枚举，目前是不可行的。











Share