s31容斥原理引论 第三章容斥原理和鸽巢原理 §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 容斥原理引论
§32容斥原理 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 容斥原理
§32容斥原理 容斥原理研究有限集合的交或并 的计数。 DeMorgan定理]论域U,补集A A={x|x∈U且x≠A},有 (a)A∪B=A∩B ()A∩B=AB
容斥原理研究有限集合的交或并 的计数。 [DeMorgan定理] 论域U，补集 A A x x U x A = { | } 且 ,有 §3.2 容斥原理 (a) A B A B = (b) A B A B =
§32容斥原理 证:(a)的证明 设 ∈H∩B,则xg A∪B xA∪B相当于xA和xEB 同时成立,亦即 A∈A∪B→x∈A∩B(1)
证：(a)的证明。 设 ,则 相当于 和 同时成立，亦即 x A B x AB x AB x A xB A A B x A B (1) §3.2 容斥原理
§32容斥原理 反之,若x∈A∩B,即x∈Ax∈B 故xA和x∈B亦即xA∩B x∈A∩B→x∈A∪B(2) 由(1)和(2)得 x∈A∩B分x∈A∪B (b)的证明和(a)类似,从略
反之，若 x A B x A x B , 即 和 故 x A x B x A B 和 亦即. x x A B A B (2) 由（1）和（2）得 x A B x A B (b)的证明和（a)类似，从略. §3.2 容斥原理