第七章组合数学.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,第七章组合数学,第七章组合数学第七章组合数学7.1基本的计数原则,加法原理：完成一个任务有两类方式，分别各有m和n种方法，则完成该任务的方法数是m+n,A1A2=A1+A2（A1A2=）,加法原理可推广到多类方式或多个集合的情况,注意加法原理中，各类方式或各个集合之间的不交要求,乘法原理：一个任务的实施可以分解为两个独立的步骤，分别各有m和n种方法，,则完成该任务的方法数是m*n,A1A2=A1*A2,7.1基本的计数原则,加法原理,：完成一个任务有两类方式，分别各有m和n种方法，则完成该任务的方法数是m+n,A1A2,=,A1,+,A2,（A1A2=,）,加法原理可推广到多类方式或多个集合的情况,注意加法原理中，各类方式或各个集合之间的不交要求,乘法原理,：一个任务的实施可以分解为两个独立的步骤，分别各有m和n种方法，,则完成该任务的方法数是m*n,A1A2,=,A1,*,A2,例8,计数函数。从一个n元集到一个m元集存在多少个函数？,解 一个函数对于定义域中m个元素中的每个元素都要选择倍域中n个元素中的一个元素来对应。因此，由乘积法则存在n*n*n=nm个从m元集到n元集的函数。,例9,一对一函数。从一个m元素集合到一个n元素集合存在多少个一对一函数？,解 首先注意到当mn时没有从m元集到n元集的一对一函数。现在令m,n。假设定义域中的元素是a1,a2,am。有n种方式选择函数在a1的值。因为函数是一对一的，可以有n-1种方式选择函数在a2的值。一般地，有n-k+1种方式选择函数在ak的值。由乘积法则，从一个m元素集合到一个n元素集合存在着n(n-1)(n-2)（n-m+1）个一对一函数。,例,10 IP,地址的计算,因特网上的计算机有多少不同的有效,IPv4,地址？,解 令,X,是因特网上计算机的有效地址数，,XA,XB,和,XC,分别表示,A,类、,B,类和,C,类的有效地址数。由求和法则，,X=XA+XB+XC,。,（接下页）,（接上页）,为了找到XA,由于1111111是无效的，故存在27-1=127个A类的网络标识。对于每个网络标识，存在224-2=16 777 214个主机标识，这是由于全0和全1组成的主机标识是无效的。因此，XA=127*16 777 214=2 130 706 178。,为了找到XB 和 XC，首先注意到存在214=16 384个B类网络标识和212=2 097 152个C类网络标识。对每个B类网络标识存在着216-2=65 534个主机标识，而对每个C类网络标识，存在28-2=254个主机标识，这也是考虑到全0和全1是无效的主机标识。因而,XB=1 073 709 056，XC,=,532 676 608。我们可以断言IPv4有效地址的总数是:,X=XA+XB+XC=2 130 706 178+1 073 709 056+532 676 608=3 737 091 842。,7.2基本（不可重复）的排列与组合问题,集合的r-排列：,集合中的r个元素的有序序列,A,=n，A的r-排列数P(n,r)=n(n-1)(n-r+1)=,集合的r-组合：,集合的r个元素的子集,A,=n，A的r-组合数C(n,r)=P(n,r)/n!=,C(n,r)=C(n,n-r),关于二项式系数：注意它们的组合意义,C(n+1,k)=,C(n,k-1)+C(n,k),（帕斯卡恒等式）,C(m+n,r)=,（范德蒙恒等式）,（二项式定理）,7.3可重复的排列和组合问题,定理2,A,=n，A的允许重复（重复次数没有限制）的r-组合数是C(n+r-1,r),证明：,当允许重复时n元素集合的每个r-组合可以用n-1条竖线和r颗星的表表示。这n-1条竖线是用来标记n个不同的单元。每当集合的第i个元素出现在组合中，第i个单元就包含一颗星。例如，4元素集合的一个6-组合用3条竖线和6颗星来表示。这里*|*|*,代表了恰包含2个第一元素、1个第二元素、0个第三元素和3个第四元素的组合。,正如我们已经看到的，包含n-1条竖线和r颗星的每一个不同的表对应于n元素集合的允许重复的一个r-组合。这种表的个数是C(n+r-1,r)，因为每个表对应于从包含r颗星和n-1条竖线的n-1+r个位置中取r个位置来访r颗星的一种选择。,例,5,设一家甜点店有四种不同类型的甜点，那么从中选,6,块甜点有多少种不同的方式？假定只关心甜点的类型，而不管是哪一块甜点或者选择的次序。,解 选择,6,块甜点的方式数是具有,4,类元素集合的,6-,组合数。由定理,2,，这等于,C(4+6-1,6)=C(9,6),由于,C(9,6)=C(9,3)=(9*8*7)/(1*2*3)=84,选择,6,块甜点的不同方式数有,84,种。,例,6,方程,x1+x2+x3=11,有多少个解？其中,x1,x2,和,x3,是非负整数。,解 为计数解的个数，注意到一个解对应了从,3,元素集合中选,11,个元素的方式，以使得,x1,选自第一类，,x2,选自第二类，,x3,选自第三类。因此，解的个数等于,3,元素集合允许重复的,11-,组合数。由定理,2,存在,C(3+11-1,11)=C(13,11)=C(13,2)=(13*12)/(1*2)=78,个解。,例,7,在下面的伪码被执行后,k,的值是什么？,k:=0,for,i,1,:=1,to,n,for,i,2,:=1,to,i,1,for,i,m,:=1,to,i,m-1,k:=k+1,解：,k,的初值是,0,，且对于一组满足,1i,m,i,m-1,i,1,n,的整数,i,1,，,i,2,，,i,m,，每次执行这个嵌套循环时,k,的值就加,1.,这种整数的组数是从,1,2,n,中允许重复地选择,m,个整数的方式数,.(,因为一旦这组整数选定以后，如果按非降序排列它们,这就唯一地确定了一组对,i,m,i,m-1,i,1,的赋值。相反，每个这样的赋值对应了一个唯一的无序集合。）所以由定理,2,得出在代码被执行后,k=C(n+m-1,m),。,定理,3,n,1,个,1,类物体，,n,2,个,2,类物体，,，,n,k,个,k,类物体，,n=,n,i,这,n,个物体的全排列数是,证明：,分别确定每类物体的排列位置，再用乘法原则,为确定排列数，首先注意到可以用,C(n,n,1,),中方式在,n,个位置中方类型,1,的,n,1,个物体，剩下,n-n,1,个空位。然后用,C(n-n,1,n,2,),种方式来放类型,2,的物体，剩下,n-,n,1,-,n,2,个空位。继续放类型,3,的物体，,，类型,k-1,的物体，直到最后可用,C(n-,n,1,-,n,2,-,n,k-1,n,k,),种方式放类型,k,的物体。因此，由乘积法则，不同排列的总数是,C(n,n,1,)C(n-n,1,n,2,)C(n-n,1,-n,2,-n,k-1,n,k,),=,*,=,定理,4,n=,n,i,个不同物体，放入,k,个盒子，第,1,个盒子,n,1,个，第,2,个盒子,n,2,个，,，第,k,个盒子,n,k,个，,方法数是,证明：先对,n,个物体（任意）排序。为第,i,个盒子设计,n,i,个相同的标记，对这,n,个标记做全排，根据全排列的结果分配物体入盒子,例,11,有多少种方式把,52,张标准的扑克牌发给,4,个人使得每人,5,张牌？,解 我们将使用乘积法则求解这个问题。开始，第一个人得到,5,张牌可以有,C(52,5),种方式。第二个人得到,5,张牌可以有,C(47,5),种方式，因为只剩下,47,张牌。第三个人得到,5,张牌可以有,C(42,5),种方式。最后，第四个人得到,5,张牌可以有,C(37,5),种方式。因此，发给,4,个人,5,张牌的方式总数是,C(52,5)C(47,5)C(42,5)C(37,5)=*,=,汇报结束,谢谢大家,!,请各位批评指正,