鸽巢原理 容斥原理.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|=135容斥原理定理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之间的整数构成全集EA、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=12510