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

第三章集合论3.1集合3.2集合的运算和性质3.3集合中元素的计数3.4应用集合元素的个数容斥原理

3.3集合中的元素计数第3章集合

集合元素的个数集合元素的个数

计数问题在计算机科学中具有十分重要的地位。集合的运算在计数问题中有很好的应用。对一些简单集合的计数问题，可利用集合的交、并、差运算来解决。集合A中的元素个数被称为集合A的基数，对含有n个元素的有限集合，称其基数是n，记作：基数是表示集合中所含元素多少的量，也可记作A等于n。如果一个集合的基数是有限的，则称该集合为有限集；如果一个集合的基数是无限的，则称该集合为无限集。显然，空集的基数为0。

集合的表示定义3.8设A为集合，若存在自然数n使得CardA=n，则称A为有限集，否则称A为无限集。例如：{1,2,3}是有限集，而N、R、Z、Q、C都是无限集。因无限集的基数比较复杂，这里仅讨论有限集的基数问题。根据集合的运算，下面的式子显然成立：

集合的表示例3.7有96名程序员，其中51名熟悉Python语言，67名熟悉C语言，32名同时熟悉这两种语言。有多少人对这两种语言都不熟悉？解：设A、B分别表示熟悉Python语言和C语言的程序员的集合，则该问题可以用文氏图来表示，如图3.3所示。图3.3例3.7文氏图

集合的表示将熟悉两种语言的对应人数32填到

的区域内，则有从而得到所以,共有10人对两种语言都不熟悉。

集合的表示例3.8解：设只会英语、法语、德语的人数分别为x，y，z。会3种语言的人数为h根据题意，构造文氏图如图3.4所示，从而得到如下方程:图3.4例3.8文氏图

集合的表示解得所以，只会一种语言的人数是12人，会三语言的人数1人。

定义3.3.2容斥原理用文氏图来解决一些简单集合的计数问题非常方便。上面的例子中，首先计算所有元素的个数，然后减去（排斥掉）不符合条件的元素的个数。这实际上就是容斥原理（thePrincipleofInclusion-Exclusion）的基本思想，即先包含，后排斥。集合间的关系

集合间的关系定理3.6

设S为有限集合，P₁,P₂,…,P是n条性质，Aᵢ表示S中具有性质Pᵢ的元素构成的集合，则

集合间的关系证明：1）用数学归纳法该定理是证明两个集合相等的基本思路和依据。显然，当n=2时，成立，因为这把只属于A₁或只属于A₂的元素只计一次，而把既属于A₁又属于A₂的元素计了两次。

集合间的关系设

证明：由A⊆B知，对∀x∈A，则有∀x∈B。又由B⊆C，有∀x∈C，所以有A⊆C。有

集合间的关系因此有

所以（1）成立。（2）因为

所以有

集合间的关系此定理中（1）计数了S中至少具有一条性质的元素数，而（2）则计数了S中不具有任一性质的元素数。有了容斥原理，例3.7中所求的元素数为

集合间的关系定义3.9

设某班有100名学生，其中有68人英语成绩为优，有45人数学成绩为优，有23人英语和数学成绩均为优。问两门课程都不为优的学生有多少名？解：设分别表示英语成绩为优和数学成绩为优的集合，则有由包含排斥原理得所以

集合间的关系定义3.10

求1到500之间能被，2，3，5任何一个整除的整数个数。解：设A、B、C分别表示1到500之间能被2、3、5整除的整数集合，则有A中元素个数=⌊500÷2⌋=250B中元素个数=⌊500÷3⌋=166C中元素个数=⌊500÷5⌋=100

集合间的关系A∩B中元素个数=⌊500÷(2×3)⌋=83A∩C中元素个数=⌊500÷(2×5)⌋=50B∩C中元素个数=⌊500÷(3×5)⌋=33A∩B∩C中元素个数=⌊500÷(2×3×5)⌋=10则可得到：A∪B∪C的元素个数=A+B+C−A∩B−A∩C−B∩C+A∩B∩C=250+166+100−83−50−33+10=360

集合间的关系其中⌊x⌋表示小于或等于x的最大整数。即在1到500之间有360个整数可被2、3、5任一个整除。例3.11求1到1000之间不能被3或5，也不能被7整除的整数个数。解：设A、B、C分别表示1到1000之间能被3、5、7整除的整数集合，则有A中元素个数=⌊1000÷3⌋=333B中元素个数=⌊1000÷5⌋=200C中元素个数=⌊1000÷7⌋=142

集合间的关系A∩B中元素个数=⌊1000÷(3×5)⌋=66A∩C中元素个数=⌊1000÷(3×7)⌋=47B∩C中元素个数=⌊1000÷(5×7)⌋=28A∩B∩C中元素个数=⌊1000÷(3×5×7)⌋=9所以，既不能被3，5整除，也不能被7整数的整数有457个。例子3.12：求欧拉函数的值。欧拉函数ψ是数论中的一个重要函数，在密码学中有着重要作用。设n是正整数，ψ(n)表示{0,1,2,…,n−1}中与n互素的数的个数。例如，ψ(14)=6，因为与14互素的数有1、3、5、9、11、13。这里约定ψ(1)=1。下面用容斥原理给出欧拉函数的计算公式。

集合间的关系例如，ψ(14)=6，因为与14互素的数有1、3、5、9、11、13。这里约定ψ(1)=1。下面用容斥原理给出欧拉函数的计算公式。给定正整数n，若

为n的素因子分解式，令则有下面计算上述右边的各项。