离散数学第七章计数.ppt
第七章 计数,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发生但两者不能同时发生。, 如果选择事物O1有n1种方法，选择事物O2有n2种方法，选择事物Om有nm种方法，并且选择诸事物方法不重叠，则选取O1或O2或或Om有n1+n2+nm种方法。,加法原理,例7.1.1 一个学生想选修一门数学课或一门生物学课，但不能同时选修两门课。如果该生对5门数学课和3门生物学课具有选课条件，试问该生有多少方式来选修课程？,乘法原理,乘法原理又称有序计数原理，也称积规则，类似加法原理，也有三种表述形式。 若S1，S2，Sm是非空集合，则笛卡尔积S1S2Sm的元素个数是 若事件E1，E2，Em发生分别有e1，e2，em种方式，并且诸事件是独立的，则事件E1或E2或···或Em依次发生有e1e2em种方式。,乘法原理, 如果选取事物O1，O2，Om分别有n1，n2，nm种方法，并且选取诸事物方法不重叠，则事物O1与O2与与Om依次选取有n1n2nm种方法。,乘法原理,例7.1.2 一个学生要选修两门课，第一门课在上午4小时内任选1小时，第二门课在下午3小时内也可任选1小时，试问该生有多少种可能的时间安排？,例7.1.3 计数因特网地址。在由计算机的物理网络互连而构成的因特网中，每台计算机的网络连接被分配一个因特网地址。在网际协议版本IPV4中，一个地址是32位的位串，它以网络标识netid开始，后跟随主机标识hostid，该标识把一个计算机认定为某个指定网络成员。,乘法原理,乘法原理,根据网络标识和主机标识位数的不同目前使用3类地址形式： 用于最大规模网络的A类地址，由0后跟7位网络标识和24位的主机标识构成。 用于中等规模网络的B类地址，由位串10后跟14位的网络标识和16位的主机标识构成。 用于最小规模网络的C类地址，由位串110后跟21位的网络标识和8位的主机标识构成。 此外，又规定位串1111111在A类的网络标识中是无效的，全0和全1组成的主机标识对任何网络都是无效的。试计数因特网上的计算机有多少不同的有效IPV4地址？,乘法原理,令D是因特网上计算机的有效地址数，DA,DB,DC分别表示A类B类和C类的有效地址，根据加法原理D= DA+DB+DC A类的网络标识有27-1=127个（ 1111111无效），主机标识224-2=16777214（全0和全1组成的主机标识无效），根据乘法原理，DA=127*16777214,乘法原理,B类的网络标识有214个，主机标识216-2个，根据乘法原理，DB= 214 * （216-2） C类的网络标识有221个，主机标识28-2个，根据乘法原理，DB= 221 * （28-2） D= DA+DB+DC=3737091842,7.2 鸽洞原理,若n+1只鸽子入住n个鸽洞，则至少有1个鸽洞里至少有2只鸽子。 例7.2.1 在任意一群366人中，至少有2人生日相同。 例7.2.2 抽屉里有3副手套，随意抽出4只手套，则其中至少有一副手套。,鸽洞原理,例7.2.3 一个学生用37天准备考试。根据以往的经验他知道需要复习的时间不超过60个小时，他打算每天至少复习1小时，证明不管他如何安排学习时间表（假定每天学习时数为整数），必存在相继的若干天，他恰好共学习13小时。,鸽洞原理,设t1是第一天学习的时数，t2是前2天学习时数，t3是前3天学习时数 因为每天至少学习1小时，所以t11,数列t1,t2,t37是严格单调递增的：t1t2t37 复习的时间不超过60个小时,所以t3760 数列t1+13,t37+13也是严格递增的，并且t37+13 73,鸽洞原理,因此74个数t1,t2,t37,t1+13,t37+13都位于1和73之间，根据鸽洞原理，它们之中必有两个数相等 由于前37个数和后37个数都是彼此不相等的，故存在两个数i和j，使得ti=tj+13 于是j+1，j+2，i这些天中，该生恰好学习13小时,鸽洞原理的推广,设m1,m2,mn是正整数，并有m1+m2+mn-n+1只鸽子住进n个鸽洞，则或者 第1个鸽洞至少有m1只鸽子，或者第2个鸽洞至少有m2只鸽子，或者第n个鸽洞至少有mn只鸽子。 证明：反证法。假设第一个鸽洞住进的鸽子数少于m1只，第2个鸽洞住进鸽子数少于m2只于是，鸽子总数不超过（m1-1）+（m2-1）+（mn-1)=m1+m2+mn-n 与m1+m2+mn-n+1只鸽子矛盾,7.3 容斥原理,有限集合中的容斥定理,在无限集合中不一定成立. 2个集合的情形：|AB| = |A| + |B| |AB| 3个集合的情形：|ABC| = |A| + |B|+|C| |AB| |AC| |BC|+ |ABC| 一般情形：,设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|) = 17 50 + 26 + 21=14 有14人两次考试都得5分,7.4 排列与组合,我们以前讨论的排列称为线排列更为确切，因为它隐含着将所选择的r元素排成在一直线上，若使线排列的首末元素相邻就得了“圆排列”。 定义7.4.2 从n元集S中有序选择r个元素并排成一个圆周称为S的一个r圆排列，不同的r圆排列总数记为K(n，r)或 。,由于在圆排列中重要的是元素彼此间相对位置，因此一个圆排列经过旋转后得到的仍是同一个圆排列，而线排列则不然了，只要有一个元素的位置发生变化便得到不同的排列。考虑到对每一个固定的n个元素取r个的圆排列均恰有r种不同方式展成r个不同线排列，不同的圆排列展成的线排列彼此也必不同，全部圆排列展出的恰好就是全部线排列，因此线排列数是圆排列数的r倍，于是 K(n，r)=P(n，r)/r 特别当r=n时，K(n，n)=P(n，n)/n=(n-1)!,例7.4.2 6颗颜色不同的钻石，可穿成几种钻石圈? 圆排列就是在P（6，6）的基础上，本来在这里面ABCDEFG和BCDEFGA是不同的，但是“圆排列”这里因为形成了一个圆圈，所以，ABCDEFG和BCDEFGA是相同的，同样“CDEFGAB”等和他们也是相同的，可见，一个相同的圆排列在原有的P（6，6）中是被重复计算了6次，于是圆排列的结果是：P(6,6)/6=1*2*3*4*5=120 又因为钻石圈是可以翻转的，也就是在这里“ABCDEF”和“FEDCBA”是一样的（想象一下手镯，你平放着，你再翻转一下，还是原来的手镯，但是你同样是顺时针编号，得出的号码是正好调转的），于是在圆排列的基础上你要除以2，得到P(6,6)/6/2=60种。,例7.4.3 6个人坐成一个圆形,可以有多少种坐法? 你只要考虑“圆排列”了，因为你不能把人底朝天的翻转，于是答案是P（6，6）/6=120种,下面我们主要讲解重集的排列与组合 所谓重集是指其元素可以多次出现的集合，某元素ai出现的次数ni(ni=1，2，)称为该元素的重复数或重复度。如重集S中有k个元素a1，a2，ak，其重复数分别为n1，n2，nk，则S=n1·a1，n2·an，nk·ak。 重集的排列 定义：从重集S =n1·a1，n2·an，nk·ak中有序选择r个元素称为S的一个r排列，当r =n1+n2+nk时也称S的全排列或S的排列。,定理7.4.5 设重集S=·a1，·a2，·ak，则S的r排列数是kr。 推论 设重集S=n1·a1，n2·a2，nk·ak，且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个格子中选2个放p，由乘法原理知，共有 种方法。,定理7.4.6 设重集S =n1·a1，n2·an，nk·ak，且n1+n2+nk =n,则S的全排列数是,重集的组合 定义：设重集S =n1·a1,n2·an,nk·ak ，S中r个元素的子重集称为S的r组合。 由定义知，若S有n个元素，即n1+n2+nk =n，则S的n组合只有一个，即S自身。若S含有k个不同元素，则存在k个S的1组合。 例如： S=3·a, 1·b, 2·c，则a, a,a, b,a, c,b, c,c, c都是S的2组合。,定理7.4.7 设重集S = ·a1，·a2，·ak，则S的r组合数是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颗星的一个选择。,推论1 设重集S=n1·a1，n2·a2，nk·ak，且nir，1ik，则S的r组合数是C(k+r-1，r)。 推论2 设重集S=·a1，·a2，·ak，且rk，则S中每个元素至少选择一个的r组合数是C(r-1，k-1)。,例7.4.6 面包店供应8种面点。如果一盒装12个面点，并且面包店有大量（每种至少12个）各种面点，问能供应多少不同面点盒？ 解 设8种面点分别记为a1，a2，a8，所求不同面点盒个数是重集=·a1，·a2，·a8或=12·a1，12·a2，12·a8的12组合数，即C(8+12-1,12)C(19,12)C(19,7),7.5 递推关系,定义7.5.1 将数列H(0)，H(1)， H(n)，中任一项H(n)与其前某些项H(i)用相等、小于等于或大于等于联结起来的式子，称为递推关系，其中n0in，这里n0是一个非负整数。称H(0)，H(1)，H(n0)为初始条件。由初始条件和递推关系而导出通项的显示表达式，称为递推公式。也称递推公式是递推关系的解。,例7.5.1 汉诺塔游戏。它是由安装在三根固定的柱子上和不同尺寸的n个圆盘组成。开始时，这些圆盘按大小的次序放在第一根柱子上，使大圆盘在底下。游戏的规则是：每次把1个圆盘从一根柱子移到另一根柱子，但不允许这个圆盘放在比它小的圆盘上面。游戏的目标是把所有圆盘按照大小的次序都放到第二根柱子上，并且将最大的圆盘放在底部。 令Hn表示把n个圆盘从一根柱子移到另一根柱子所需要的移动次数。建立关于序列Hn的递推关系。,这一步实际有Hn-1步,这只需1步,这一步又需要Hn-1步,故移动n个圆盘的总步数Hn=Hn-1+1+Hn-1 =2Hn-1+1,以“Hn=2Hn-1+1，且H1=1”为例，求通项(递推公式)的常用方法有： 逐差求和(等差数列通项的求法) 逐商求积(等比数列通项的求法) 转化为等差或等比数列后利用等差或等比数列的通项公式求得 归纳法 迭代方法 母函数法(生成函数法),定义：对于序列an：a1，a2，an，构造一函数 G(x)= 称函数G(x)是序列an的生成函数，或母函数，或形式幂级数。 例如 (1+x)n是序列 的生成函数。 如若已知序列an，则对应的生成函数G(x)便可根据定义确定。反之，如若已求得序列的生成函数G(x)，则该序列也随之确定。,使用母函数法，要用到高数中有关级数的知识。这里我们就不详细举例求解了。 下面我们介绍一类特殊的递推关系分而治之递推关系。,例7.5.2 分而治之递推关系。在算法分析中，会分析一个规模为n的问题分成a个子问题的处理过程，其中每子问题的规模是n/b。此外，假设由于分解而需要额外运算为g(n)。若f(n)为求解该问题所需要的运算次数，于是得到f(n)满足的递推关系 f(n)=af(n/b)+g(n) 称上式为分而治之递推关系。,定理7.5.1 设f(n)满足递推关系 f(n)= af(n/b)+ c 的增函数，其中b|n，a1，b1，c为正实数，则 下面举一例说明定理7.5.1的应用,例如，分析二分检索算法。若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)。,一般说来，对于简单递推关系可以用上面讲的一些方法来求解，特别是母函数法更为有效。但是，由于递推关系的多样性，其解的方法也会有差别。对于一些特殊结构的递推关系还有程序化的方法求解，这里就不再介绍了。,
