离散数学-3-3 包含与排斥原理.ppt

第三章 集合与关系3-3 包含与排斥原理授课人：李朔Email:1一、有限集的计数一个集合若其组成集合的元素个数是有限的，则称作有限集有限集。n设A1、A2为有限集，其元素个数分别记为|A1|，|A2|nP96有限集记数有如下几个性质：na）|A1A2|A1|+|A2|nb）|A1A2|min(|A1|,|A2|)nc）|A1A2|A1|A2|nd）|A1A2|=|A1|+|A2|2|A1 A2|n以上公式可以通过文氏图直接得到说明2二、容斥原理定理定理3-3.1 设A1，A2为有限集合，其元素个数分别为|A1|，|A2|，则|A1A2|=|A1|+|A2|A1 A2|A2A1EA1 A23二、容斥原理定理定理 设A1，A2，A3为有限集合，其元素个数分别为|A1|，|A2|，|A3|则有|A1A2 A3|=|A1|+|A2|+|A3|A1 A2|A1 A3|A2 A3|+|A1 A2 A3|4二、容斥原理A1A2A3A1 A2A1 A3A2 A3 A1 A2 A35二、容斥原理例例 一个学校只有三门课程：数学、物理、化学。已知修这三门课的学生分别有170、130、120人；同时修数学、物理两门课的学生45人；同时修数学、化学的20人；同时修物理化学的22人。同时修三门的3人。问这学校共有多少学生？6二、容斥原理例例 一个学校只有三门课程：数学、物理、化学。已知修这三门课的学生分别有一个学校只有三门课程：数学、物理、化学。已知修这三门课的学生分别有170、130、120人；同时修数学、物理两门课的学生人；同时修数学、物理两门课的学生45人；人；同时修数学、化学的同时修数学、化学的20人；人；同时修同时修物理化学的物理化学的22人。人。同时修三门的同时修三门的3人。问这学校共有多少学生？人。问这学校共有多少学生？解：解：令令 M为修数学的学生集合；P 为修物理的学生集合；C 为修化学的学生集合；则：书例 P96 例题1、27二、容斥原理定理定理 设A1，A2，A3，A4为有限集合，其元素个数分别为|A1|，|A2|，|A3|，|A4|，则|A1 A2 A3 A4|=|A1|+|A2|+|A3|+|A4|A1 A2|A1 A3|A1 A4|A2 A3|A2 A4|A3 A4|+|A1 A2 A3|+|A2 A3 A4|+|A1 A3 A4|+|A1 A2 A4|A1 A3 A2 A4|8二、容斥原理P97 定理定理3-3.(推广到n个有限集情况）设A1,A2,An为有限集合，其元素个数分别为|A1|，|A2|,|An|，则|A1A2 An|=|Ai|Ai Aj|+|Ai Aj Ak|+(-1)n-1|A1 A2 An|证明：P989练习例例 求从1到500的整数中能被3或5除尽的数的个数。10练习例例 求从1到500的整数中能被3或5除尽的数的个数。解：解：令A为从1到500的整数中被3除尽的数的集合，B为被5除尽的数的集合 被3或5除尽的数的个数为11练习P99 书例3例 求不超过120的素数个数。提示提示：因 ，故不超过120的合数是2、3、5、7的倍数，而且不超过120的合数的因子不可能都超过11。设 Ai 为不超过120的数i 的倍数集，i=2，3，5，7。12练习例 求不超过120的素数个数。解：13练习14练习注意：注意：27并非就是不超过120的素数个数，因为这里排除了2，3，5，7着四个数，又包含了1这个非素数。2，3，5，7本身是素数。故所求的不超过120的素数个数为：27+4-1=3015本课小结有限集计数包容排斥原理16作业 P100（3）17