《包含排斥原理》PPT课件

3-3 包含排斥原理(容斥原理)要求：掌握n个集合的包含排斥原理，并应用它求解实际问题。n复习：集合的运算（交、并、补、对称差）1、交集、交集定义：定义：设任意两个集合A和B，由A和B的所有共同元素组成的集合，称为A和B的交集，记为AB。AB=x|x Ax B文氏图2、并集、并集定义：定义：设任意两个集合A和B，所有属于A或属于B的元素组成的集合，称为A和B的并集，记作AB。AB=x|x Ax B文氏图3、差集、补集、差集、补集定义：定义：设A、B是任意两个集合，所有属于A而不属于B的元素组成的集合称为B对A的补集，或相对补，(或A和B差集)记作A-B。A-B=x|xAxB文氏图4、对称差定义：定义：设A、B是任意两个集合，集合A和B的对称差，其元素或属于A，或属于B，但不能既属于A又属于B，记作AB。AB=(A-B)(B-A)文氏图(1)max(|A|，|B|)|AB|A|+|B|(2)|AB|min(|A|，|B|)(3)|A|-|B|A-B|A|(4)|AB|=|A|+|B|-2|AB|一、有限集合的计数一、有限集合的计数 设A，B为有限集合，其元素个数分别为|A|，|B|，根据集合运算的定义，显然以下各式成立。二、包含排斥原理二、包含排斥原理1、定理：、定理：设A1，A2为有限集合，其元素个数分别为|A1|，|A2|，则|A1A2|=|A1|+|A2|-|A1A2|，此定理被称作包含排斥原理。证明：a)当A1A2=，则|A1A2|=|A1|+|A2|b)若A1A2，则|A1|=|A1A2|+|A1A2|，|A2|=|A1A2|+|A1A2|所以|A1|+|A2|=|A1A2|+|A1A2|+|A1A2|+|A1A2|=|A1A2|+|A1A2|+2|A1A2|而|A1A2|+|A1A2|+|A1A2|=|A1A2|故|A1A2|=|A1|+|A2|-|A1A2|解：设解：设A A为从为从1 1到到500500的整数中，能被的整数中，能被3 3除尽的数的集合。除尽的数的集合。B B为从为从1 1到到500500的整数中，能被的整数中，能被5 5除尽的数的集合。除尽的数的集合。则则 A A=500/3=166=500/3=166（xx表示不超过表示不超过x x的最大整数）的最大整数）B B=500/5=100=500/5=100 A A B B=500/=500/（3 3*5 5）=33=33由包含排斥原理：由包含排斥原理：A A B B=A A+B B-A A B B=166+100-33=233=166+100-33=233即从即从1 1到到500500的整数中，能被的整数中，能被3 3或或5 5除尽的数有除尽的数有233233个。个。例例1 1：求从：求从1 1到到500500的整数中，能被的整数中，能被3 3或或5 5除尽的数的个数。除尽的数的个数。解：设职员和学生的集合分别是解：设职员和学生的集合分别是A和和B。由已知条件。由已知条件 A=10，B=12，A B=5，有，有 A B=A+B-A B=10+12-5=17，则，则(A B)=E-A B=20-17=3。有有3名青年既不是职员又不是学生。名青年既不是职员又不是学生。例例2：在：在20名青年中有名青年中有10名是公司职员，名是公司职员，12名是学生，名是学生，其中其中5名既是职员又是学生，问有几名既不是职员，名既是职员又是学生，问有几名既不是职员，又不是学生。又不是学生。例题例题3 3 假设在假设在1010名青年中有名青年中有5 5名是工人，名是工人，7 7名是学名是学生，其中兼具工人和学生双重身份的青年有生，其中兼具工人和学生双重身份的青年有3 3名，名，问有几名既不是工人又不是学生。问有几名既不是工人又不是学生。解：设工人的集合为解：设工人的集合为W W，学生的集合为，学生的集合为S S。则根据。则根据题设有题设有|E|=10|E|=10，W W=5=5，S S=7=7，W W S S=3=3，则则 W W S S=W W+S S-W W S S=5+7-3=9=5+7-3=9，则则(A(A B)B)=E E-A A B B=10-9=1=10-9=1。有有1 1名既不是工人又不是学生。名既不是工人又不是学生。2、三个集合的包含排斥原理：、三个集合的包含排斥原理：对于三个集合A1，A2和A3，其元素个数分别为|A1|，|A2|，|A3|，则|A1A2A3|=|A1|+|A2|+|A3|-|A1A2|-|A1A3|-|A2A3|+|A1A2A3|例题例题4 在某工厂装配在某工厂装配30辆汽车，可供选择的设备是收音机、辆汽车，可供选择的设备是收音机、空气调节器和对讲机。已知其中有空气调节器和对讲机。已知其中有15辆汽车有收音机，辆汽车有收音机，8辆辆有空气调节器，有空气调节器，6辆有对讲机，而且其中有辆有对讲机，而且其中有3辆汽车这三样辆汽车这三样设备都有。我们希望至少有多少辆汽车没有任何设备。设备都有。我们希望至少有多少辆汽车没有任何设备。解：设解：设A1，A2和和A3分别表示配有收音机、空气调节器和对讲机的汽车分别表示配有收音机、空气调节器和对讲机的汽车集合。因此集合。因此|A1|=15，|A2|=8，|A3|=6，|A1 A2 A3|=3，故，故|A1 A2 A3|=|A1|+|A2|+|A3|-|A1 A2|-|A1 A3|-|A2 A3|+|A1 A2 A3|=15+8+6-|A1 A2|-|A1 A3|-|A2 A3|+3=32-|A1 A2|-|A1 A3|-|A2 A3|因为因为|A1 A2|A1 A2 A3|，|A1 A3|A1 A2 A3|，|A2 A3|A1 A2 A3|所以所以|A1 A2 A3|32-3-3-3=23即至多有即至多有23辆汽车有一个或几个选择的设备，因此至少有辆汽车有一个或几个选择的设备，因此至少有7辆汽车不提辆汽车不提供任何可选择的设备。供任何可选择的设备。练习：练习：某年级有某年级有59名学生，期末考高等数学、线性代数名学生，期末考高等数学、线性代数和英语三门课。已知高等数学、线性代数和英语和英语三门课。已知高等数学、线性代数和英语各门课的及格人数分别为各门课的及格人数分别为47人、人、49人和人和50人。人。其中高等数学、英语都及格的有其中高等数学、英语都及格的有43人，线性代数人，线性代数和英语都及格的有和英语都及格的有42人，三门课都及格的有人，三门课都及格的有40人，人，三门课都不及格的有三门课都不及格的有1人。问高等数学和线性代人。问高等数学和线性代数都及格的有多少人？只有一门课及格的有多少数都及格的有多少人？只有一门课及格的有多少人？人？解 设全集U为该年级全体学生的集合。A为高等数学及格的学生的集合。B为线性代数及格的学生的集合。C为英语及格的学生的集合。3、n个集合的包含排斥原理个集合的包含排斥原理定理定理3-3.2 设A1，A2，An为有限集合，其元素个数分别为|A1|，|A2|，|An|，则解：设解：设1 1到到250250间分别能被间分别能被2 2，3 3，5 5，7 7整除的整数集合为整除的整数集合为A A1 1，A A2 2，A A3 3，A A4 4。设。设 x x 表示不大于表示不大于x x最大整数，最大整数，A A1 1=250/2250/2=125=125，A A2 2=250/3250/3=83=83，A A3 3=250/5250/5=50=50，A A4 4=250/7250/7=35=35 A A1 1 A A2 2=250/(2250/(2*3)3)=41=41，A A1 1 A A3 3=250/(2250/(2*5)5)=25=25，A A1 1 A A4 4=250/(2250/(2*7)7)=17=17，A A2 2 A A3 3=250/(3250/(3*5)5)=16=16，A A2 2 A A4 4=250/(3250/(3*7)7)=11=11，A A3 3 A A4 4=250/(5250/(5*7)7)=7=7，例题例题5 5 求求1 1到到250250之间能被之间能被2 2，3 3，5 5，7 7任一数整除的整数个数。任一数整除的整数个数。A A1 1 A A2 2 A A3 3=250/(2250/(2*3 3*5)5)=8=8，A A1 1 A A2 2 A A4 4=250/(2250/(2*3 3*7)7)=5=5，A A1 1 A A3 3 A A4 4=250/(2250/(2*5 5*7)7)=3=3，|A|A2 2 A A3 3 A A4 4=250/(3250/(3*5 5*7)7)=2=2，|A|A1 1 A A2 2 A A3 3 A A4 4|=|=250/(2250/(2*3 3*5 5*7)7)=1=1 A A1 1 A A2 2 A A3 3 A A4 4=125+83+50+35|-41-25-17-16-=125+83+50+35|-41-25-17-16-11-7+8+5+3+2-1=19311-7+8+5+3+2-1=193练习99页(1)-(5)