鸽巢原理+容斥原理.ppt

1
容斥原理
容斥原理（相容排斥原理）是组合计数中常用到的一种方法。
例1 求不超过20的正整数中是2的倍数或3的倍数的数的个数。
不超过20的正整数中是2的倍数的数有10个，即2, 4, 6, 8, 10, 12, 14, 16, 18, 20。不超过20的正整数中是3的倍数的数有6个，即3, 6, 9, 12, 15, 18。
但是不超过20的正整数中是2的倍数或3的倍数的数的个数不是10+6=16个，而是13个，因为其中6, 12, 18这三个数既是2的倍数又是3的倍数。
2
容斥原理
集合论加法法则：
若|A|=m，|B|=n，AB= ， 则|AB|=m+n。
思考：若A、B为任意的有限集合，则|AB|=？
3
容斥原理
定理1 若A、B为任意的有限集合，则
4
容斥原理
例1 求不超过20的正整数中是2的倍数或3的倍数的数的个数。
解：设A、B分别表示不超过20的正整数中2的倍数的数的集合和3的倍数的数的集合，则问题转化为求|AB|
易见|A|=10，|B|=6，|AB |=3
因此|AB|=|A|+|B|- | AB |=13
5
容斥原理
定理2 若A、B、C为任意的有限集合，则
6
容斥原理
利用数学归纳法可获得容斥原理的一般形式：
定理3 设
是有限集合，则
7
容斥原理
容斥原理的等价形式：
定理4 设
是有限集合，则
8
容斥原理
例2 一个学校只有三门课程：数学、物理、化学。已知修这三门课的学生分别有170、130、120人；同时修数学、物理两门课的学生45人；同时修数学、化学的20人；同时修物理、化学的22人。同时修三门的3人。问这学校共有多少学生？
解 令M、P、C分别为修数学、物理、化学的学生集合
则该问题转化为求|MPC|
9
容斥原理
例3 求1~1000中不能被5、6和8中任何一数整除的整数的个数
解：设1~1000之间的整数构成全集E
A、B、C分别表示其中可被5，6，8整除的数的集合
则问题转化为求|~A~B~C|
由于ABC=1000/[5，6，8]=1000/120=8
AB=1000/[5，6]=33
AC=1000/[5，8]=25
BC=1000/[6，8]=41
A=1000/5=200
B=1000/6=166
C=1000/8=125
10