3-3 包含排斥原理.ppt

1、3-3 包含排斥原理 (容斥原理),要求： 掌握n个集合的包含排斥原理，并应用它求解实际问题。,复习：集合的运算 （交、并、补、对称差）,1、交集 定义3-2.1：设任意两个集合A和B，由A和B的所有共同元素组成的集合，称为A和B的交集，记为AB。 AB=x|x Ax B 文氏图,2、并集 定义3-2.2：设任意两个集合A和B，所有属于A或属于B的元素组成的集合，称为A和B的并集，记作AB。 AB=x|x Ax B 文氏图,3、差集、补集 定义3-2.3：设A、B是任意两个集合，所有属于A而不属于B的元素组成的集合称为B对A的补集，或相对补，(或A和B差集)记作A-B。 A-B=x|xAxB

2、文氏图,4、对称差 定义3-2.5：设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、定理3-3.1：设A1，A2为有限集合，其元素个数分别为|A1|，|A2|，则|A1A2|=|A1|+|A2|-|A1

3、A2|，此定理被称作包含排斥原理。,证明：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为从1到500的整数中，能被3除尽的数的集合。 B为从1到500的整数中，能被5除尽的数的集合。 则 A=500/3=166 （x表示不超过x的最大整数） B=500

4、/5=100 AB=500/（3*5）=33 由包含排斥原理： AB=A+B-AB=166+100-33=233 即从1到500的整数中，能被3或5除尽的数有233个。,例1：求从1到500的整数中，能被3或5除尽的数的个数。,解：设职员和学生的集合分别是A和B。由已知条件A=10，B=12，AB=5，有 AB=A+B-AB=10+12-5=17，则(AB)=E-AB=20-17=3。 有3名青年既不是职员又不是学生。,例2：在20名青年中有10名是公司职员，12名是学生，其中5名既是职员又是学生，问有几名既不是职员，又不是学生。,例题3 假设在10名青年中有5名是工人，7名是学生，其中兼具工

5、人和学生双重身份的青年有3名，问有几名既不是工人又不是学生。,解：设工人的集合为W，学生的集合为S。则根据题设有|E|=10，W=5，S=7，WS=3， 则WS=W+S-WS=5+7-3=9， 则(AB)=E-AB=10-9=1。 有1名既不是工人又不是学生。,2、三个集合的包含排斥原理：对于三个集合A1，A2和A3，其元素个数分别为|A1|，|A2|，|A3|，则 |A1A2A3|=|A1|+|A2|+|A3|-|A1A2|-|A1A3|-|A2A3|+|A1A2A3|,例题4 在某工厂装配30辆汽车，可供选择的设备是收音机、空气调节器和对讲机。已知其中有15辆汽车有收音机，8辆有空气调节器

6、，6辆有对讲机，而且其中有3辆汽车这三样设备都有。我们希望至少有多少辆汽车没有任何设备。,解：设A1，A2和A3分别表示配有收音机、空气调节器和对讲机的汽车集合。因此 |A1|=15，|A2|=8，|A3|=6， |A1A2A3|=3，故 |A1A2A3|=|A1|+|A2|+|A3|-|A1A2|-|A1A3|-|A2A3|+|A1A2A3| =15+8+6 -|A1A2|-|A1A3|-|A2A3|+3 =32 -|A1A2|-|A1A3|-|A2A3| 因为|A1A2|A1A2A3|，|A1A3|A1A2A3|， |A2A3|A1A2A3| 所以|A1A2A3|32-3-3-3=23 即

7、至多有23辆汽车有一个或几个选择的设备，因此至少有7辆汽车不提供任何可选择的设备。,练习： 某年级有59名学生，期末考高等数学、线性代数和英语三门课。已知高等数学、线性代数和英语各门课的及格人数分别为47人、49人和50人。其中高等数学、英语都及格的有43人，线性代数和英语都及格的有42人，三门课都及格的有40人，三门课都不及格的有1人。问高等数学和线性代数都及格的有多少人？只有一门课及格的有多少人？,解 设全集U为该年级全体学生的集合。 A为高等数学及格的学生的集合。 B为线性代数及格的学生的集合。 C为英语及格的学生的集合。,3、n个集合的包含排斥原理 定理3-3.2 设A1，A2，An为

8、有限集合，其元素个数分别为|A1|，|A2|，|An|，则,解：设1到250间分别能被2，3，5，7整除的整数集合为A1，A2，A3，A4。设x表示不大于x最大整数， A1=250/2=125，A2=250/3=83，A3=250/5=50，A4=250/7=35 A1A2=250/(2*3)=41，A1A3=250/(2*5)=25，A1A4=250/(2*7)=17， A2A3=250/(3*5)=16，A2A4=250/(3*7)=11，A3A4=250/(5*7)=7，,例题5 求1到250之间能被2，3，5，7任一数整除的整数个数。,A1A2A3=250/(2*3*5)=8，A1A2A4=250/(2*3*7)=5， A1A3A4=250/(