离散数学计数省公共课一等奖全国赛课获奖课件.pptx

第七章第七章 计数计数第1页7.1 基本计数原理基本计数原理1.加法原理2.乘法原理第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发生但二者不能同时发生。第3页l 假如选择事物O1有n1种方法，选择事物O2有n2种方法，选择事物Om有nm种方法，而且选择诸事物方法不重合，则选取O1或O2或或Om有n1+n2+nm种方法。第4页加法原理加法原理l例例7.1.1 一个学生想选修一门数学课或一门生物学课，但不能同时选修两门课。假如该生对5门数学课和3门生物学课含有选课条件，试问该生有多少方式来选修课程？第5页乘法原理乘法原理l乘法原理又称有序计数原理，也称积规则，类似加法原理，也有三种表述形式。l 若S1，S2，Sm是非空集合，则笛卡尔积S1S2Sm元素个数是l 若事件E1，E2，Em发生分别有e1，e2，em种方式，而且诸事件是独立，则事件E1或E2或或Em依次发生有e1e2em种方式。第6页乘法原理乘法原理l 假如选取事物O1，O2，Om分别有n1，n2，nm种方法，而且选取诸事物方法不重合，则事物O1与O2与与Om依次选取有n1n2nm种方法。第7页乘法原理乘法原理l例例7.1.2 一个学生要选修两门课，第一门课在早晨4小时内任选1小时，第二门课在下午3小时内也可任选1小时，试问该生有多少种可能时间安排？第8页l例例7.1.3 计数因特网地址。在由计算机物理网络互连而组成因特网中，每台计算机网络连接被分配一个因特网地址。在网际协议版本IPV4中，一个地址是32位位串，它以网络标识netid开始，后跟随主机标识hostid，该标识把一个计算机认定为某个指定网络组员。乘法原理乘法原理第9页乘法原理乘法原理l依据网络标识和主机标识位数不一样当前使用3类地址形式：l用于最大规模网络A类地址，由0后跟7位网络标识和24位主机标识组成。l用于中等规模网络B类地址，由位串10后跟14位网络标识和16位主机标识组成。l用于最小规模网络C类地址，由位串110后跟21位网络标识和8位主机标识组成。l另外，又要求位串1111111在A类网络标识中是无效，全0和全1组成主机标识对任何网络都是无效。试计数因特网上计算机有多少不一样有效IPV4地址？第10页乘法原理乘法原理l令D是因特网上计算机有效地址数，DA,DB,DC分别表示A类B类和C类有效地址，依据加法原理D=DA+DB+DClA类网络标识有27-1=127个（1111111无效），主机标识224-2=16777214（全0和全1组成主机标识无效），依据乘法原理，DA=127*16777214第11页乘法原理乘法原理lB类网络标识有214个，主机标识216-2个，依据乘法原理，DB=214*（216-2）lC类网络标识有221个，主机标识28-2个，依据乘法原理，DB=221*（28-2）lD=DA+DB+DC=3737091842第12页7.2 鸽洞原理鸽洞原理l若n+1只鸽子入住n个鸽洞，则最少有1个鸽洞里最少有2只鸽子。l例例7.2.1 在任意一群366人中，最少有2人生日相同。l例例7.2.2 抽屉里有3副手套，随意抽出4只手套，则其中最少有一副手套。第13页鸽洞原理鸽洞原理l例例7.2.3 一个学生用37天准备考试。依据以往经验他知道需要复习时间不超出60个小时，他打算天天最少复习1小时，证实不论他怎样安排学习时间表（假定天天学习时数为整数），必存在相继若干天，他恰好共学习13小时。第14页鸽洞原理鸽洞原理l设t1是第一天学习时数，t2是前2天学习时数，t3是前3天学习时数l因为天天最少学习1小时，所以t11,数列t1,t2,t37是严格单调递增：t1t2t37l复习时间不超出60个小时,所以t3760l数列t1+13,t37+13也是严格递增，而且t37+13 73第15页鸽洞原理鸽洞原理l所以74个数t1,t2,t37,t1+13,t37+13都位于1和73之间，依据鸽洞原理，它们之中必有两个数相等l因为前37个数和后37个数都是彼此不相等，故存在两个数i和j，使得ti=tj+13l于是j+1，j+2，i这些天中，该生恰好学习13小时第16页鸽洞原理推广鸽洞原理推广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只鸽子矛盾第17页7.3 容斥原理容斥原理有限集合中容斥定理,在无限集合中不一定成立.l2个集合情形：|AB|=|A|+|B|AB|l3个集合情形：|ABC|=|A|+|B|+|C|AB|AC|BC|+|ABC|l普通情形：第18页设S为全集，又因为则有2个集合情形：=|S|(|A|+|B|)+|AB|3个集合情形：=|S|(|A|+|B|+|C|)+(|AB|+|AC|+|BC|)|ABC|第19页例 一个班里有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|)=17 50+26+21=14有14人两次考试都得5分第20页7.4 排列与组合排列与组合 我们以前讨论排列称为线排列更为确切，因为它隐含着将所选择r元素排成在一直线上，若使线排列首末元素相邻就得了“圆排列”。定定义义7.4.2 从n元集S中有序选择r个元素并排成一个圆周称为S一个r圆排列，不一样r圆排列总数记为K(n，r)或 。第21页 因为在圆排列中主要是元素彼此间相对位置，所以一个圆排列经过旋转后得到仍是同一个圆排列，而线排列则不然了，只要有一个元素位置发生改变便得到不一样排列。考虑到对每一个固定n个元素取r个圆排列均恰有r种不一样方式展成r个不一样线排列，不一样圆排列展成线排列彼此也必不一样，全部圆排列展出恰好就是全部线排列，所以线排列数是圆排列数r倍，于是K(n，r)=P(n，r)/r尤其当r=n时，K(n，n)=P(n，n)/n=(n-1)!第22页l例例7.4.2 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”和“FEDCBA”是一样（想象一下手镯，你平放着，你再翻转一下，还是原来手镯，不过你一样是顺时针编号，得出号码是恰好调转），于是在圆排列基础上你要除以2，得到P(6,6)/6/2=60种。第23页l例例7.4.3 6个人坐成一个圆形,能够有多少种坐法?l你只要考虑“圆排列”了，因为你不能把人底朝天翻转，于是答案是P（6，6）/6=120种 第24页 下面我们主要讲解重集排列与组合 所谓重集是指其元素能够屡次出现集合，某元素ai出现次数ni(ni=1，2，)称为该元素重复数或重复度。如重集S中有k个元素a1，a2，ak，其重复数分别为n1，n2，nk，则S=n1a1，n2an，nkak。l重集排列 定义：从重集S=n1a1，n2an，nkak中有序选择r个元素称为S一个r排列，当r=n1+n2+nk时也称S全排列或S排列。第25页定理定理7.4.5 设重集S=a1，a2，ak，则Sr排列数是kr。推推论论 设重集S=n1a1，n2a2，nkak，且nir，1ik，则Sr排列数是kr。下面我们来看重集全排列。先看下面这个例子。第26页 例：1个m，4个i，5个s，2个p全部使用，共能组成多少个单词？解：有12个空格：把145212个字母全部放进这12个格子中即算完成这件事。先从12个格子中选1个放m，再从剩下12111个格子中选4个放i，再从剩下12147个格子中选5个格式放s，再从最终121452个格子中选2个放p，由乘法原理知，共有 种方法。第27页 定理定理7.4.6 设重集S=n1a1，n2an，nkak，且n1+n2+nk=n,则S全排列数是第28页l重集组合 定义：设重集S=n1a1,n2an,nkak，S中r个元素子重集称为Sr组合。由定义知，若S有n个元素，即n1+n2+nk=n，则Sn组合只有一个，即S本身。若S含有k个不一样元素，则存在k个S1组合。比如：S=3a,1b,2c，则a,a,a,b,a,c,b,c,c,c都是S2组合。第29页定理定理7.4.7 设重集S=a1，a2，ak，则Sr组合数是C(k+r-1，r)。证：S每个r组合能够用k-1条竖线和r颗星形式来表示。其中k-1条竖线表示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颗星一个选择。第30页推推论论1 设重集S=n1a1，n2a2，nkak，且nir，1ik，则Sr组合数是C(k+r-1，r)。推推论论2 设重集S=a1，a2，ak，且rk，则S中每个元素最少选择一个r组合数是C(r-1，k-1)。第31页例例7.4.6 面包店供给8种面点。假如一盒装12个面点，而且面包店有大量（每种最少12个）各种面点，问能供给多少不一样面点盒？解 设8种面点分别记为a1，a2，a8，所求不一样面点盒个数是重集=a1，a2，a8或=12a1，12a2，12a812组合数，即C(8+12-1,12)C(19,12)C(19,7)第32页7.5 递推关系定定义义7.5.1 将数列H(0)，H(1)，H(n)，中任一项H(n)与其前一些项H(i)用相等、小于等于或大于等于联结起来式子，称为递推关系，其中n0i1，c为正实数，则下面举一例说明定理7.5.1应用第40页比如，分析二分检索算法。若n为偶数时，二分检索算法把对某个元素在长度为n搜索序列中搜索转化为对一元素在长度为n/2搜索序列中二分检索。所以，规模为n问题被分解成规模为n/2问题。为执行这个分解需要2次比较，1次是为了确定要用到表哪二分之一，另1次是为了确定表是否还有项留下来。所以，若f(n)是在规模为n搜索序列中搜索一个元素所需要比较次数，则当n是偶数时，f(n)=f(n/2)+2。依据定理7.5.1知，a=1，b=2，c=2，所以f(n)是O(log2n)。第41页普通说来，对于简单递推关系能够用上面讲一些方法来求解，尤其是母函数法更为有效。不过，因为递推关系多样性，其解方法也会有差异。对于一些特殊结构递推关系还有程序化方法求解，这里就不再介绍了。第42页