清华大学：《组合数学》课程教学资源（PPT课件讲稿）第三章 容斥原理和鸽巢原理

§3.1容斥原理引论 第三章容斥原理和鸽巢原理 §1容斥原理引论 例[1,20]中2或3的倍数的个数 解]2的倍数是:2,4,6,8,10, 12,14,16,18,20 10

第三章 容斥原理和鸽巢原理 §1 容斥原理引论 例 [1，20]中2或3的倍数的个数 [解] 2的倍数是：2，4，6，8，10， 12，14，16，18，20。 10个 §3.1 容斥原理引论

§3,2容斥原理 3的倍数是:3,6,9,12,15, 8。6个 但答案不是10+6=16个,因为6 12,18在两类中重复计数,应 减 去。故答案是:16-3=13

3的倍数是：3，6，9，12，15， 18。 6个 但答案不是10+6=16 个，因为6， 12，18在两类中重复计数，应 减 去。故答案是：16-3=13 §3.2 容斥原理

§3,2容斥原理 容斥原理研究有限集合的交或并 的计数。 Demorgan定理论域U,补集A A={x|x∈U且xA},有 (a)AUB=A∩B (b)A∩ B=A B

容斥原理研究有限集合的交或并 的计数。 [DeMorgan定理] 论域U，补集 A A{x | xU且x A} ,有 §3.2 容斥原理 (a) A  B  A  B (b) A  B  A  B

§3,2容斥原理 证:(a)的证明。 设 ∈∩B则xg A∪B x堡AUB相当于xA和xB 同时成立,亦即 A∈A∪B→x∈A∩B(x)

证：(a)的证明。 设 ,则 相当于 和 同时成立，亦即 x  A  B x A B x AB xA xB AABxAB (1) §3.2 容斥原理

§3,2容斥原理 反之,若x∈A∩B,即x∈A和x∈B 故xA和x∈B亦即x≠A∩B x∈A∩B→x∈A∪B(2) 由(1)和(2)得 x∈A∩Bx∈A∪B (b)的证明和(a)类似,从略

反之，若 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 容斥原理

§3,2容斥原理 DeMogan定理的推广:设 AA2,,4,是U的子集 则(a)A1∪A2U.Jn=A∩A21…A2 (p)UU"UN=￥∩平∩∩ 证明:只证(a).N-2时定理已证。 设定理对n是正确的,即假定:

DeMogan定理的推广：设 1, 2 ,..., A A An是U的子集 2 1 2 ... ... 则 1  A   An  A  A   An (a)A 2 1 2 ... ... 1  A   An  A  A   An (b)A 证明：只证(a). N=2时定理已证。 设定理对n是正确的，即假定： §3.2 容斥原理

§3,2容斥原理 A1∪A2∪.,JAn=A1∩A21∩…∩An正确 A1∪AU.A1∪A1=(A∪.JA)∪A1 =(A∪AU…A2∩A1 =A∩A1…A42∩A 即定理对n+1也是正确的

2 1 2 ... ... 1  A   An  A  A   An A 正确 2 1 1 2 1 2 1 1 1 1 ... ( ... ) ( ... ... n n n n n n n n A A A A A A A A A A A A A A                       1 则 A 即定理对n+1也是正确的。 §3.2 容斥原理

§32容斥原理 §2容斥原理 最简单的计数问题是求有限集合A 和B的并的元素数目。显然有 定理: AUB=|4+|B-A∩B( 即具有性质A或B的元素的个数等于具

§2 容斥原理 最简单的计数问题是求有限集合A 和B的并的元素数目。显然有 即具有性质A或B的元素的个数等于具 A B  A  B  A B (1) 定理： §3.2 容斥原理

§32容斥原理 有性质A和B的元素个数。 U A AnB B

有性质A和B的元素个数。 U A AB B §3.2 容斥原理

§32容斥原理 证若A∩B=,则|A∪B=A|+|B A|=|A∩(BUB) =(A∩B)U(A∩B) =A∩B|+A∩B(1 同理|B|=|B∩A|+|B∩A|(2 A∪B|=(A∩(BUB)U(B(AUA (A∩B)∪(A∩B)∪(B∩A)∪(B∩A川 A∩B|+A∩B|+|B∩A(3)

§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 )