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

  |  

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

【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】
我的网站:潮汐朝夕的生活实验室
我的公众号:算法题刷刷
我的知乎:潮汐朝夕
我的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 - 6$
$A_{2}$: $x_{2} \ge 7$ 的解, $x_{1} - 7 + x_{2} + x_{3} = 15 - 7$
$A_{3}$: $x_{3} \ge 8$ 的解, $x_{1} - 8 + x_{2} + x_{3} = 15 - 8$

$|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