离散数学第七章计数.ppt

《离散数学第七章计数.ppt》由会员分享，可在线阅读，更多相关《离散数学第七章计数.ppt（42页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第七章第七章 计数计数7.1 基本计数原理基本计数原理1.加法原理2.乘法原理加法原理加法原理加法原理又称为和计数原理，也称和规则，存在三种表述形式，其本质是说，整体等于其部分之和。若集合X是不相交非空子集S1，S2，Sm的并，则|X|=若E1，E2，Em是彼此互斥事件，并且E1发生有e1种方式，E2发生有e2种方式，Em发生有em种方式，则E1或E2或或Em发生有e1+e2+em种方式。应该指出的是，事件E1和E2互斥是说，E1和E2发生但两者不能同时发生。l 如果选择事物O1有n1种方法，选择事物O2有n2种方法，选择事物Om有nm种方法，并且选择诸事物方法不重叠，则选取O1或O2或或Om

2、有n1+n2+nm种方法。加法原理加法原理l例例 一个学生想选修一门数学课或一门生物学课，但不能同时选修两门课。如果该生对5门数学课和3门生物学课具有选课条件，试问该生有多少方式来选修课程？乘法原理乘法原理l乘法原理又称有序计数原理，也称积规则，类似加法原理，也有三种表述形式。l 若S1，S2，Sm是非空集合，则笛卡尔积S1S2Sm的元素个数是l 若事件E1，E2，Em发生分别有e1，e2，em种方式，并且诸事件是独立的，则事件E1或E2或或Em依次发生有e1e2em种方式。乘法原理乘法原理l 如果选取事物O1，O2，Om分别有n1，n2，nm种方法，并且选取诸事物方法不重叠，则事物O1与O2

3、与与Om依次选取有n1n2nm种方法。乘法原理乘法原理l例例 一个学生要选修两门课，第一门课在上午4小时内任选1小时，第二门课在下午3小时内也可任选1小时，试问该生有多少种可能的时间安排？l例例 计数因特网地址。在由计算机的物理网络互连而构成的因特网中，每台计算机的网络连接被分配一个因特网地址。在网际协议版本IPV4中，一个地址是32位的位串，它以网络标识netid开始，后跟随主机标识hostid，该标识把一个计算机认定为某个指定网络成员。乘法原理乘法原理乘法原理乘法原理l根据网络标识和主机标识位数的不同目前使用3类地址形式：l用于最大规模网络的A类地址，由0后跟7位网络标识和24位的主机标识

4、构成。l用于中等规模网络的B类地址，由位串10后跟14位的网络标识和16位的主机标识构成。l用于最小规模网络的C类地址，由位串110后跟21位的网络标识和8位的主机标识构成。l此外，又规定位串1111111在A类的网络标识中是无效的，全0和全1组成的主机标识对任何网络都是无效的。试计数因特网上的计算机有多少不同的有效IPV4地址？乘法原理乘法原理l令D是因特网上计算机的有效地址数，DA,DB,DC分别表示A类B类和C类的有效地址，根据加法原理D=DA+DB+DClA类的网络标识有27-1=127个（1111111无效），主机标识224-2=16777214（全0和全1组成的主机标识无效），根据

5、乘法原理，DA=127*16777214乘法原理乘法原理lB类的网络标识有214个，主机标识216-2个，根据乘法原理，DB=214*（216-2）lC类的网络标识有221个，主机标识28-2个，根据乘法原理，DB=221*（28-2）lD=DA+DB+DC=37370918427.2 鸽洞原理鸽洞原理l若n+1只鸽子入住n个鸽洞，则至少有1个鸽洞里至少有2只鸽子。l例例 在任意一群366人中，至少有2人生日相同。l例例 抽屉里有3副手套，随意抽出4只手套，则其中至少有一副手套。鸽洞原理鸽洞原理l例例 一个学生用37天准备考试。根据以往的经验他知道需要复习的时间不超过60个小时，他打算每天至少

6、复习1小时，证明不管他如何安排学习时间表（假定每天学习时数为整数），必存在相继的若干天，他恰好共学习13小时。鸽洞原理鸽洞原理l设t1是第一天学习的时数，t2是前2天学习时数，t3是前3天学习时数l因为每天至少学习1小时，所以t11,数列t1,t2,t37是严格单调递增的：t1t2t37l复习的时间不超过60个小时,所以t3760l数列t1+13,t37+13也是严格递增的，并且t37+13 73鸽洞原理鸽洞原理l因此74个数t1,t2,t37,t1+13,t37+13都位于1和73之间，根据鸽洞原理，它们之中必有两个数相等l由于前37个数和后37个数都是彼此不相等的，故存在两个数i和j，使得

7、ti=tj+13l于是j+1，j+2，i这些天中，该生恰好学习13小时鸽洞原理的推广鸽洞原理的推广l设m1,m2,mn是正整数，并有m1+m2+mn-n+1只鸽子住进n个鸽洞，则或者 第1个鸽洞至少有m1只鸽子，或者第2个鸽洞至少有m2只鸽子，或者第n个鸽洞至少有mn只鸽子。l证明：反证法。假设第一个鸽洞住进的鸽子数少于m1只，第2个鸽洞住进鸽子数少于m2只于是，鸽子总数不超过（m1-1）+（m2-1）+（mn-1)=m1+m2+mn-n与m1+m2+mn-n+1只鸽子矛盾7.3 容斥原理容斥原理有限集合中的容斥定理,在无限集合中不一定成立.l2个集合的情形：|AB|=|A|+|B|AB|l3

8、个集合的情形：|ABC|=|A|+|B|+|C|AB|AC|BC|+|ABC|l一般情形：设S为全集，又因为则有2个集合的情形：=|S|(|A|+|B|)+|AB|3个集合的情形：=|S|(|A|+|B|+|C|)+(|AB|+|AC|+|BC|)|ABC|例 一个班里有50个学生，在第一次考试中有26人得5分，在第二次考试有21人得5分如果两次考试中都没得5分的有17人，那么两次考试都得5分的有多少人？解 设A，B分别表示在第一次和第二次考试中得5分的学生的集合，那么有|S|=50,|A|=26,|B|=21,=17由 =|S|(|A|+|B|)+|AB|，得|AB|=|S|+(|A|+|B

9、|)=17 50+26+21=14有14人两次考试都得5分7.4 排列与组合排列与组合 我们以前讨论的排列称为线排列更为确切，因为它隐含着将所选择的r元素排成在一直线上，若使线排列的首末元素相邻就得了“圆排列”。定定义 从n元集S中有序选择r个元素并排成一个圆周称为S的一个r圆排列，不同的r圆排列总数记为K(n，r)或 。由于在圆排列中重要的是元素彼此间相对位置，因此一个圆排列经过旋转后得到的仍是同一个圆排列，而线排列则不然了，只要有一个元素的位置发生变化便得到不同的排列。考虑到对每一个固定的n个元素取r个的圆排列均恰有r种不同方式展成r个不同线排列，不同的圆排列展成的线排列彼此也必不同，全部

10、圆排列展出的恰好就是全部线排列，因此线排列数是圆排列数的r倍，于是K(n，r)=P(n，r)/r特别当r=n时，K(n，n)=P(n，n)/n=(n-1)!l例例 6颗颜色不同的钻石，可穿成几种钻石圈?l圆排列就是在P（6，6）的基础上，本来在这里面ABCDEFG和BCDEFGA是不同的，但是“圆排列”这里因为形成了一个圆圈，所以，ABCDEFG和BCDEFGA是相同的，同样“CDEFGAB”等和他们也是相同的，可见，一个相同的圆排列在原有的P（6，6）中是被重复计算了6次，于是圆排列的结果是：P(6,6)/6=1*2*3*4*5=120 l又因为钻石圈是可以翻转的，也就是在这里“ABCDEF

11、”和“FEDCBA”是一样的（想象一下手镯，你平放着，你再翻转一下，还是原来的手镯，但是你同样是顺时针编号，得出的号码是正好调转的），于是在圆排列的基础上你要除以2，得到P(6,6)/6/2=60种。l例例 6个人坐成一个圆形,可以有多少种坐法?l你只要考虑“圆排列”了，因为你不能把人底朝天的翻转，于是答案是P（6，6）/6=120种 下面我们主要讲解重集的排列与组合 所谓重集是指其元素可以多次出现的集合，某元素ai出现的次数ni(ni=1，2，)称为该元素的重复数或重复度。如重集S中有k个元素a1，a2，ak，其重复数分别为n1，n2，nk，则S=n1a1，n2an，nkak。l重集的排列

12、定义：从重集S=n1a1，n2an，nkak中有序选择r个元素称为S的一个r排列，当r=n1+n2+nk时也称S的全排列或S的排列。定理定理 设重集S=a1，a2，ak，则S的r排列数是kr。推推论 设重集S=n1a1，n2a2，nkak，且nir，1ik，则S的r排列数是kr。下面我们来看重集的全排列。先看下面这个例子。例：1个m，4个i，5个s，2个p全部使用，共能组成多少个单词？解：有12个空格：把145212个字母全部放进这12个格子中即算完成这件事。先从12个格子中选1个放m，再从剩下的12111个格子中选4个放i，再从剩下的12147个格子中选5个格式放s，再从最后121452个格

13、子中选2个放p，由乘法原理知，共有 种方法。定理定理7.4.6 设重集S=n1a1，n2an，nkak，且n1+n2+nk=n,则S的全排列数是l重集的组合 定义：设重集S=n1a1,n2an,nkak，S中r个元素的子重集称为S的r组合。由定义知，若S有n个元素，即n1+n2+nk=n，则S的n组合只有一个，即S自身。若S含有k个不同元素，则存在k个S的1组合。例如：S=3a,1b,2c，则a,a,a,b,a,c,b,c,c,c都是S的2组合。定理定理 设重集S=a1，a2，ak，则S的r组合数是C(k+r-1，r)。证：S的每个r组合可以用k-1条竖线和r颗星的形式来表示。其中k-1条竖线

14、表示k个不同的单元。当集合的第i个元素出现在组合中，第i个单元就包含一颗星。如，4元素集合的一个6组合用3条竖线和6颗星来表示。例如|表示包含2个第一元素a1，1个第二元素a2，0个第三元素a3和3个第四元素a4的组合。所以包含k-1条竖线和r颗星的每一个不同的情况就对应于k元素集合的允许重复的一个r组合。所有这些情况的个数是 C(k+r-1，r)。因为每种情况对应于从包含r颗星和k-1条竖线共k-1+r个位置中取r个位置来放r颗星的一个选择。推推论1 设重集S=n1a1，n2a2，nkak，且nir，1ik，则S的r组合数是C(k+r-1，r)。推推论2 设重集S=a1，a2，ak，且rk，

15、则S中每个元素至少选择一个的r组合数是C(r-1，k-1)。例例 面包店供应8种面点。如果一盒装12个面点，并且面包店有大量（每种至少12个）各种面点，问能供应多少不同面点盒？解 设8种面点分别记为a1，a2，a8，所求不同面点盒个数是重集=a1，a2，a8或=12a1，12a2，12a8的12组合数，即C(8+12-1,12)C(19,12)C(19,7)7.5 递推关系定定义 将数列H(0)，H(1)，H(n)，中任一项H(n)与其前某些项H(i)用相等、小于等于或大于等于联结起来的式子，称为递推关系，其中n0i1，c为正实数，则下面举一例说明定理的应用例如，分析二分检索算法。若n为偶数时

16、，二分检索算法把对某个元素在长度为n的搜索序列中的搜索转化为对一元素在长度为n/2的搜索序列中的二分检索。因此，规模为n的问题被分解成规模为n/2的问题。为执行这个分解需要2次比较，1次是为了确定要用到表的哪一半，另1次是为了确定表是否还有项留下来。所以，若f(n)是在规模为n的搜索序列中搜索一个元素所需 要 的 比 较 次 数，则 当 n是 偶 数 时，f(n)=f(n/2)+2。根据定理知，a=1，b=2，c=2，因此f(n)是O(log2n)。一般说来，对于简单递推关系可以用上面讲的一些方法来求解，特别是母函数法更为有效。但是，由于递推关系的多样性，其解的方法也会有差别。对于一些特殊结构的递推关系还有程序化的方法求解，这里就不再介绍了。