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