组合数学讲义及答案 4章 容斥原理.pdf

《组合数学》 第四章 容斥原理 第四章 容斥原理  是组合学中的一个基本计数理论。也称 “包容与排斥原理”、 “入与出原理”、“包含排斥原理”或“交互分类原理”。  加法法则的限制：要求将计数的集合划分为若干个互不相交 的子集，且这些子集都比较容易计数。  问题：实际中又有很多计数问题要找到容易计数而又两两不 相交的子集并非易事。但往往能够知道某一集合的若干相交 子集的计数，进而把所要求的集合中的元素个数计算出来。 §4.1 引 言 （一） 研究内容 （1）实例 【例】求不超过20 的正整数中是2 的倍数或3 的倍数的数的 个数。 20  ① 不超过20 的正整数中是2 的倍数的数有 2 ＝10 个，   即A ＝{ 2, 4, 6, 8, 10, 12, 14, 16, 18, 20}； 20  ② 是3 的倍数的数有 3 ＝6 个，即B ＝{ 3, 6, 9, 12, 15,   18 }； ③ 二者相加为10＋6＝16 个。 ④ 实际为13 个：即2, 3, 4, 6, 8, 9, 10, 12, 14, 15, 16, 18, 20； ⑤ 原因：把既是2 的倍数，又是3 的倍数的数重复算了一  20  次，这样的数恰好有2 3 ＝3 个，即6, 12, 18。   ⑥ 正确的统计方法：10＋6－3 ＝13 个。 （2）内容 研究若干个有限集合的交或并的计数问题。 1/49 《组合数学》 第四章 容斥原理 （二） 集合的表示 用大写字母表示一个集合，如 A、B、C、S 等，用小写字母 表示集合的元素，如a、b、c、x、y、z 等。元素a 属于集合A，  记为a A ，不属于A，记为a A . 空集记为 。 （三） 集合的运算 （1） 并（和）：记为A B 或A ＋B； （2 ） 交（积）：记为A B 或AB ； （3 ） 差：记为A －B （4 ） 对立集（非）：即 ＝S－A A 显然有 A －B ＝ ＝A －AB A B （四） 优先级 先取非，次为交，再次为并或差。 出现在同一算式中的同级运算，按从左向右的顺序进行。 先括号内，后括号外。 （五） 运算定律 （1） 交换律： A ＋B ＝B＋A ， AB ＝BA； （2 ） 结合律： (A＋B)＋C＝A＋(B＋C), (AB)C＝A(BC) ； （3 ） 分配律：A(B ＋C)＝AB ＋AC, A ＋BC ＝(A＋B)(A＋C)； （4 ） De.Morgan 定律（互反律）：