第七章-组合数学PPT课件

.,1,第七章组合数学,组合数学的两个重要问题：计数、枚举在计算机科学中的应用：算法的时间复杂性分析、密码学、IP地址某些算法,.,2,7.1基本的计数原则加法原理：完成一个任务有两类方式，分别各有m和n种方法，则完成该任务的方法数是m+nA1A2=A1+A2（A1A2=）加法原理可推广到多类方式或多个集合的情况注意加法原理中，各类方式或各个集合之间的不交要求乘法原理：一个任务的实施可以分解为两个独立的步骤，分别各有m和n种方法，则完成该任务的方法数是m*nA1A2=A1*A2,.,3,例8计数函数。从一个n元集到一个m元集存在多少个函数？解一个函数对于定义域中m个元素中的每个元素都要选择倍域中n个元素中的一个元素来对应。因此，由乘积法则存在n*n*n=nm个从m元集到n元集的函数。例9一对一函数。从一个m元素集合到一个n元素集合存在多少个一对一函数？解首先注意到当mn时没有从m元集到n元集的一对一函数。现在令mn。假设定义域中的元素是a1,a2,am。有n种方式选择函数在a1的值。因为函数是一对一的，可以有n-1种方式选择函数在a2的值。一般地，有n-k+1种方式选择函数在ak的值。由乘积法则，从一个m元素集合到一个n元素集合存在着n(n-1)(n-2)（n-m+1）个一对一函数。,.,4,例10IP地址的计算因特网上的计算机有多少不同的有效IPv4地址？解令X是因特网上计算机的有效地址数，XA,XB和XC分别表示A类、B类和C类的有效地址数。由求和法则，X=XA+XB+XC。（接下页）,.,5,（接上页）为了找到XA,由于1111111是无效的，故存在27-1=127个A类的网络标识。对于每个网络标识，存在224-2=16777214个主机标识，这是由于全0和全1组成的主机标识是无效的。因此，XA=127*16777214=2130706178。为了找到XB和XC，首先注意到存在214=16384个B类网络标识和212=2097152个C类网络标识。对每个B类网络标识存在着216-2=65534个主机标识，而对每个C类网络标识，存在28-2=254个主机标识，这也是考虑到全0和全1是无效的主机标识。因而,XB=1073709056，XC=532676608。我们可以断言IPv4有效地址的总数是:X=XA+XB+XC=2130706178+1073709056+532676608=3737091842。,.,6,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),.,7,关于二项式系数：注意它们的组合意义C(n+1,k)=C(n,k-1)+C(n,k)（帕斯卡恒等式）C(m+n,r)=（范德蒙恒等式）（二项式定理）,.,8,7.3可重复的排列和组合问题定理2A=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颗星的一种选择。,.,9,例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个解。,.,10,例7在下面的伪码被执行后k的值是什么？k:=0fori1:=1tonfori2:=1toi1forim:=1toim-1k:=k+1解：k的初值是0，且对于一组满足1imim-1i1n的整数i1，i2，im，每次执行这个嵌套循环时k的值就加1.这种整数的组数是从1,2,n中允许重复地选择m个整数的方式数.(因为一旦这组整数选定以后，如果按非降序排列它们,这就唯一地确定了一组对im,im-1,i1的赋值。相反，每个这样的赋值对应了一个唯一的无序集合。）所以由定理2得出在代码被执行后k=C(n+m-1,m)。,.,11,定理3n1个1类物体，n2个2类物体，nk个k类物体，n=ni这n个物体的全排列数是证明：分别确定每类物体的排列位置，再用乘法原则为确定排列数，首先注意到可以用C(n,n1)中方式在n个位置中方类型1的n1个物体，剩下n-n1个空位。然后用C(n-n1,n2)种方式来放类型2的物体，剩下n-n1-n2个空位。继续放类型3的物体，类型k-1的物体，直到最后可用C(n-n1-n2-nk-1,nk)种方式放类型k的物体。因此，由乘积法则，不同排列的总数是C(n,n1)C(n-n1,n2)C(n-n1-n2-nk-1,nk)=*=,.,12,定理4n=ni个不同物体，放入k个盒子，第1个盒子n1个，第2个盒子n2个，第k个盒子nk个，方法数是证明：先对n个物体（任意）排序。为第i个盒子设计ni个相同的标记，对这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)=*=,.,13,习题1.从集合1,2,n到集合1,0有多少个函数？