【精品课件】组合数学 (3).ppt

文档介绍：第三章 容斥原理和鸽巢原理
§1 容斥原理引论
例[1,20]中2或3的倍数的个数
[解] 2的倍数是:2,4,6,8,10,
12,14,16,18,20。 10个
§ 容斥原理引论
3的倍数是:3,6,9,12,15,
18。 6个
但答案不是10+6=16 个,因为6,
12,18在两类中重复计数,应减
去。故答案是:16-3=13
§ 容斥原理
容斥原理研究有限集合的交或并
的计数。
[an定理] 论域U,补集
,有
§ 容斥原理
(a)
(b)
证:(a)的证明。
设,则
相当于和
同时成立,亦即
(1)
§ 容斥原理
反之,若
故
(2)
由(1)和(2)得
(b)的证明和(a)类似,从略.
§ 容斥原理
DeMogan定理的推广:设
证明:只证(a). N=2时定理已证。
设定理对n是正确的,即假定:
§ 容斥原理
正确
即定理对n+1也是正确的。
§ 容斥原理
§2 容斥原理
最简单的计数问题是求有限集合A和B的并的元素数目。显然有
即具有性质A或B的元素的个数等于具
(1)
定理:
§ 容斥原理
有性质A和B的元素个数。
U
B
A
§ 容斥原理
§ 容斥原理
证若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 )