离散数学课件：3-3 集合中元素的计数

1、包含排斥原理包含排斥原理(容斥原理容斥原理) ： 对任意两个对任意两个有限集有限集A和和B，有有|AB| = |A|+|B| |AB| | | ：集合的基数：集合的基数(元素个数元素个数)(一)集合计数的基本原理EAB又又 A=(A B)(AB)且且 (A B)(AB)= 从而从而 |AB|= | B | + | A B |(1)从而从而|A|=|A B| + |AB|(2)由式由式(1)(2)得，得，AB = B(A B)且且B (A B) = |AB|=|B|+|A| |AB|ABC | EABC推推 广广11111 + +(-1)niijiij nijkij k nnniiAAAAAAA

2、 |A| |B| |C|1niiA 三、集合中元素的计数三、集合中元素的计数 |AB | |AC| |BC| |ABC |( (二二) )实例实例一个班里有一个班里有50个学生，在第一次考试中有个学生，在第一次考试中有26人得人得5分，在第二次考试中有分，在第二次考试中有21人得人得5分。如分。如果两次考试中都没得果两次考试中都没得5分的有分的有17人，那么在人，那么在两次考试都得两次考试都得5分的有多少人？分的有多少人？又因为又因为 |AB| = |A| + |B| |AB|所以所以 |AB| = 26 + 21 33=33 设设A、B分别表示第一和第二次考试中得分别表示第一和第二次考试中得

3、5分学生的集合，分学生的集合，则则有有 |E| =50, |A| =26, |B| =21, |AB| =17.| AB| = |E-(AB)| 首先由首先由AB = (AB)知知= |E-AB| = |E|-|AB| |A| + |B| |AB| = 14三、集合中元素的计数三、集合中元素的计数某班有某班有25个学生，其中个学生，其中14人会打篮球，人会打篮球，12人人会打排球，会打排球，6人会打篮球和排球，人会打篮球和排球，5人会打篮人会打篮球和网球，还有两人会打这三种球，而球和网球，还有两人会打这三种球，而6个个会打网球的人都会打另外一种球会打网球的人都会打另外一种球(指篮球和指篮球和排

4、球排球)，求不会打这三种球的人数？，求不会打这三种球的人数？|A|=12，|AC |=6，|B|=6，|E|=25,|C|=14，|BC |=5， |ABC |=2. 用用A、B、C分别表示会打排球、网球、篮球分别表示会打排球、网球、篮球的学生集合，则有的学生集合，则有 ： 由于由于AB C = (AB C),先求先求 = |A|+|B|+|C| |AB| |AC | |BC | + |ABC |ABC |=12+6+14 6 5+2 |AB| = |A|+|B|+|C| |AB| |AC | |BC | + |ABC |ABC |又因为又因为6个会打网球的人都会打另外一种球，即个会打网球的人都会打另外一种球，即B AC ，所以，所以，B=B(AC)= B(A(CA) =(AB) (B C A) 从而，从而， |AB|= 6 ( 5 2 )|B|- |BCA| =|B|- (|BC |- |