离散数学及其应用-第2版 课件 第6章计数

第6章

计数第6章计数6.1基本计数规则6.2排列于组合6.3容斥原理6.1基本计数规则6.1.1加法法则6.1.2乘法法则6.1.1加法法则加法法则：事件A有m种产生方式，事件B有n种产生方式，当A与B产生的方式不重叠时，“事件A或B”有m+n种产生方式。加法法则使用的条件是事件A与B产生的方式不能重叠。加法法则的推广：设A1，A2，…，An是n个事件，它们的产生方式分别有P1，P2，…，Pn，当其中任何两个事件产生的方式都不重叠时，事件“A1或A2或…或An”有P1＋P2＋…＋Pn种产生的方式。例题例6.1.1在下面的程序代码段被执行后，k的值是多少？k:=0fori1:=1ton1k:=k+1fori2:=1ton2k:=k+1forim:=1tonmk:=k+1

解：k的值是n1

+n2

+…+nm。

6.1.2乘法法则乘法法则：事件A有m种产生方式，事件B有n种产生方式，当A与B产生的方式彼此独立时，“事件A与B”有mn种产生方式。乘法法则使用的条件是事件A与B产生的方式彼此独立，即，事件A对产生方式的选择不影响事件B对产生方式的选择，反之也对。乘法法则的推广：设A1，A2，…，An是n个事件，它们的产生方式分别有P1，P2，…，Pn种，当其中任何两个事件产生的方式都彼此独立时，事件“A1与A2与…与An”有P1P2…Pn种产生的方式。例题例6.1.2设A为n元集合，B为m元集合，回答下列问题：A上的函数有多少个？其中双射函数有多少个？A到B的函数有多少个？其中有多少个一对一函数？A上的自反关系有多少个？A上的对称关系有多少个？例题（续）解（1）A上有nn个不同的函数，可以构成n(n-1)(n-2)…1=n!个双射函数。（2）有

mn个A到B的函数.

当n>m时，不存在A到B的一对一函数。当n<=m时，A到B的一对一函数有

个。（3）自反关系有

个。（4）有个对称矩阵。IP地址编码方案

08162432A类0网络地址（7位）主机地址（24位）B类10网络地址（14位）主机地址（16位）C类110网络地址（21位）主机地址（8位）D类1110组播地址（28位）E类11110保留地址A、B、C

三类在全球范围内统一分配，D类地址用于在IP网络中的组播，E类地址保留作研究之用。例题例6.1.3TCP/IP网络中，A类地址中，全0和全1不做网络地址，A、B、C三类地址中全0和全1都不作为主机地址。在Internet中有多少个可统一分配的有效的IP地址？解在Internet中有可统一分配的有效的IP地址为A、B、C三类地址，令这三类地址总数为N，A类、B类、C类的有效IP地址数分别为NA、NB、NC。由加法法则，N=NA+NB+NC。令Wi和Ci(i

{A,B,C})表示每类地址的网络地址数和主机地址数，由乘法法则，Ni=Wi

Ci(i

{A,B,C})。

例题（续）A类地址中，全0和全1不做网络地址，故网络地址有

个，对每个网络地址有

个主机地址，因而，

。B类地址，有

个网络地址，对每个网络标识有

个主机地址，

。C类地址，有

个网络地址，对每个网络标识有

个主机地址，

。在A类、B类和C类地址中，全0和全1都不作为主机标识，主机标识数需减2。因此N=NA+NB+NC=3720364628。6.2排列与组合6.2.1排列6.2.2组合6.2.3多重集的排列于组合6.2.4二项式定理6.2.1排列

定义6.2.1从n元集S中有序、不重复选取的r个元素称为S的一个-排列，S的所有-排列的个数记作P（n，r）。

定理6.2.1设n，r为自然数，具有n个不同元素的集合S的-排列为特别地，当r＝n时，称排列为S的全排列，有

定理6.2.1证明证明首先选择排列中的第一个元素，有n种选择的方式。然后选择排列的第二个元素，它只能取自剩下的n－1个元素，有n－1种选法。以此类推，选择第三个元素，第四个元素，……，第r个元素的方式数依次为n－2，n－3，…，n－r＋1。根据乘法法则，总的选法数为容易看出全排列数P（n，n）=n！。例题例6.2.1假定有10个运动员参加长跑比赛，第一、二、三名分别得到金、银、铜牌（假定没有并列名次出现）。如果比赛可能出现所有可能的结果，那么求颁奖的方式有几种？解颁奖方式就是10元集的3-排列数。因此存在P（10，3）=10*9*8=720种可能的颁奖方式。例题例6.1.2m个男孩，n个女孩排成一排，如果女孩不相邻，有多少种方法？解先排好男孩，这对应于m元集合的全排列问题，有m！种方法。为使得女孩不相邻，将男孩看作格子分界，将女孩放入格子中间，m个男孩构成了m十1个格子（包含男孩的全排列之外的头尾两个位置在内），从中选出n个放入女孩，选法数是P（m＋1，n）。根据乘法法则所求的方法数是m！P（m＋1，n）。例题例6.2.1有一个快递员要给n个学校派送快递。假定他必须从指定的某个学校开始，但对其他n-1个学校的派送顺序可以按照他想要的任何次序进行。他派送完所有这些学校时，可以有多少种可能的次序？解由于第一个学校是确定的，所以他派送完所有学校的路径数是n-1个元素的全排列数，因此，快递员有（n-1）!种可能的派送次序。比如当n=8时，共有7！=5040种派送次序，如果要从中找出具有最短距离的路径，并计算每一条可能路径的总距离，则要计算5040条路径。6.2.2组合定义6.2.2从n元集S中无序、不重复选取的r个元素称为S的一个r-组合，S的所有r-组合的个数记作C（n，r）。下面的定理是关于C（n，r）的公式。定理6.2.2设n，r为自然数，

则定理6.2.2证明证明

首先无序地选出r个元素，然后再构造这r个元素的全排列。无序选择r个元素的方法数是C（n，r），针对每种选法，能构造P（r，r）=r！个不同的全排列，根据乘法法则，不同的r-排列数满足P（n，r）＝C（n，r）P（r，r）=C（n，r）r！所以

规定，当

时，C（n，r）=0。推论1推论1

设n，r为正整数，

，则

。证明左边=C（n，r）

右边

因此左边=右边，得证。对于一个n元素集合的r-组合数也有另一种常用的记号，即C（n，r）可写为

。

这个数也叫做二项式系数。推论2推论2

帕斯卡恒等式。设n，r为正整数，

，则证明利用定理6.2.2得

例题有多少种方式从8个选手的网球队中选出4个选手外出参加在另一个学校举行的网球比赛？解根据定理6.2.2，8个元素集合的一个4-组合是例题从1～300中任取3个数使得其和能被3整除有多少种方法？解

一个整数除以3的余数的可能取值有三个，分别是0,1和2，当一个整数除以3的余数为0时，这个整数可以被3整除。当几个不能被3整除的整数除以3的余数之和为3的倍数，这几个数之和可以被3整除。将1～300中除以3的余数相同的整数放在同一个集合，可以得到三个集合，令这三个集合为：

A＝{1，4，…，298}B＝{2，5，…，299}C＝{3，6，…，300}根据问题的要求，从1～300中任取3个数使得其和能被3整除的方法可分成以下2类：在A，B，C三个集合中的任意一个集合中任取3个数，它们之和都能被3整除。在一个集合中任取3个数，有

种选取方法，根据加法法则，在三个集合上共有3C(100，3)种选取方法。分别在A，B，C三个集合中各取1个数，它们除以3的余数之和为3，这三个数之和能被3整除。在A，B，C三个集合中各取1个数，根据乘法法则共有

种取法。根据加法法则，总选法数N＝3C(100，3)＋1003＝14851006.2.3多重集的排列与组合定理6.2.3具有n个元素的集合允许重复的r-排列数是nr。证明当允许重复时，在r-排列中对r个位置的每一个位置可以取n个元素中的任何一个，根据乘法法则，当允许重复时有nr个r-排列。例题用英文字母可以构成多少个长度为r的字符串？解

因为有26个英文字母，且每个字母可以被重复使用，由乘法法则可知可以构成26r个长度为r的字符串。定理定理6.2.4具有n个元素的集合允许重复的r-组合数是C（n+r-1，r）。证明

当允许重复时，n个元素的集合的每个r-组合可以用r个1和n-1个0的序列来表示。这里的0用来分隔r个1，n-1个0将r个1分隔成n段，每段对应集合的一个元素，每段中的1的个数表示这个元素在r-组合中出现的次数。例题例6.2.7从盛有苹果、梨子和橙子的果盆里取4个水果，如果取水果的顺序无关，且只关心水果的类型而不管取的是该类型的哪一个水果，且假设每种水果至少有4个，问取4个水果有多少种取法？解

这是3个元素集合的允许重复的4-组合问题。根据定理6.2.4，有C(3+4-1,4)=15种取法。不重复和允许重复的排列与组合类型是否允许重复公式r-排列不r-组合不r-排列是r-组合是6.2.4二项式定理定理6.2.5（二项式定理）设n是正整数，对一切x和y，有例题

的展开式是什么？=例题求在

的展开式x12y13的系数。解由二项式定理令i＝13得到展开式中x12y13的系数，即6.3容斥原理定理6.3.1（容斥原理）设,,,

是有穷集。那么例题例6.3.1对于4个集合的并集中的元素数给出一个公式。解应用容斥原理例题求不超过120的素数个数。解因为112＝121，不超过120的合数至少含有2，3，5或者7这几个素因子之一。先求在1～120之间不能被2，3，5或7整除的整数。由于2，3，5，7