§3.1 容斥原理引论第三章 容斥原理和鸽巢原理 §1 容斥原理引论例 [1,20]中2或3的倍数的个数 [解] 2的倍数是：2,4,6,8,10, 12,14,16,18,20。 10个
§3.2 容斥原理3的倍数是：3,6,9,12,15, 18。 6个 但答案不是10+6=16 个，因为6, 12,18在两类中重复计数，应减 去。故答案是：16-3=13
§3.2 容斥原理容斥原理研究有限集合的交或并 的计数。 [DeMorgan定理] 论域U,补集 A
A {x | x U 且x A} ,有(a) A B A B
(b) A B A B
§3.2 容斥原理证：(a)的证明。 设 x A B ,则 x A B x A B 相当于 x A和 x B 同时成立，亦即
A A B x A B
(1)
§3.2 容斥原理反之，若 x A B, 即x A和x B 故 x A和x B.亦即x A B x A B x A B (2)
由(1)和(2)得 x A B x A B (b)的证明和(a)类似，从略.
§3.2 容斥原理DeMogan定理的推广：设 A1, A2 ,..., An是U的子集
则 (a)A1 A2 ... An A1 A2 ... An(b) 1 A2 ... An A1 A2 ... An A
证明：只证(a). N=2时定理已证。 设定理对n是正确的，即假定：
§3.2 容斥原理A1 A2 ... An A1 A2 ... An正确,则 A1 A2 ... An An 1 ( A1 ... An ) An 1 ( A1 A2 ... An An 1 A1 A2 ... An An 1
即定理对n+1也是正确的。
§3.2 容斥原理
§2定理：
容斥原理
最简单的计数问题是求有限集合A 和B的并的元素数目。显然有
A B A B A B (1)即具有性质A或B的元素的个数等于具
§3.2 容斥原理有性质A和B的元素个数。 U A A B
B
§3.2 容斥原理证 若A∩B=φ,则 | A∪B |= |A| + |B| | A |=| A ∩( B∪B) | =| (A∩B)∪(A∩B)| =| A∩B | + | A∩B | (1) 同理 | B | =| B∩A | + | B∩A | ( 2 ) | A∪B |=|(A∩( B∪B))∪(B∩(A∪A))| =|(A∩B)∪(A∩B)∪(B∩A)∪(B∩A)| =| A∩B| + |A∩B | + | B∩A| ( 3 )
§3.2 容斥原理( 3 ) -( 1 ) -( 2 ) 得 | A∪B |-| A |-| B | =| A∩B| + |A∩B | + | B∩A| -( | A∩B | + | A∩B | ) -( | B∩A | + | B∩A | ) =- | A∩B | ∴| A∪B |=| A | + | B |-| A∩B |
§3.2 容斥原理定理：A B C A B C A B - A C B C A B C (2)
证明： A B C ( A B) C A B C ( A B) C
§3.2 容斥原理根据 ( A B) C ( A C ) ( B C ) A B C A B C A B ( A C) (B C) A B C A B - A C B C A B C
§3.2 容斥原理AA BA C
B
B C
C
C B A
§3.2 容斥原理一个学校只有三门课程：数 学、物理、化学。已知修这三门课的 学生分别有170、13
0、120人；同时修 数学、物理两门课的学生45人；同时 修数学、化学的20人；同时修物理化 学的22人。同时修三门的3人。问这学 校共有多少学生？
例
§3.2 容斥原理令：M为修数学的学生集合； P 为修物理的学生集合； C 为修化学的学生集合；
M 170, P 130, C 120, M P 45 M C 20, P C 22, M P C 3
