离散作业布置及讲评(4).ppt

单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,单击此处编辑母版标题样式,*,*,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,单击此处编辑母版标题样式,*,*,闽南师范大学 计算机学院,2014,年,11,月,第四部分 组合数学 作业,作业讲评,12-1,从集合,1,2,1000,中选,3,个数使得其和是,4,的倍数，问有多少种方法？,解：,A=除以4余数为0，B=除以4余数为1，,C=除以4余数为2，D=除以4余数为3,A、B、C、D各有250个数,1）3个均从A取，C(250,3)种,2）,B取2个、C取1个，C(250,2)C(250,1)种,C取2个、A取1个C(250,2)C(250,1)种,D取2个、C取1个，C(250,2)C(250,1)种,3）ABD各取1个,C(250,1)C(250,1)C(250,1)种,N=C(250,3)+3C(250,2)C(250,1)+C(250,1)C(250,1)C(250,1)=41,541,750,作业讲评,12-2,以凸,n,边形顶点为顶点，以内部对角线为边的三角形有多少个？,解：三角形的边，含多边形两边、一边、无,所有三角形：C(n,3),1）含2条多边形边作为边的三角形数：n,2)含1条多边形边作为边的三角形数：n(n-4),3),无边即内部对角线所构成三角形:,N=C(n,3)-n(n-4)-n=n(n-4)(n-5)/6,作业讲评,12-17 假设计算机系统的每个用户有一个,4-6,个字符的登录密码，每个字符是大写字母或者数字，且每个密码必须包含一个数字，问有多少个可能的登录密码？,解：,大写字母26个,数字10个,字母和数字,36,个,k=,4-6个字符：4 个字符、5个字符、6个字符,k,位可重复选取，全部可能有36,K,，全字母有26,k,包含4个字符有：(36,4,-26,4,),包含5个字符有：(36,5,-26,5,),包含6个字符有：(36,6,-26,6,),所以全部：,N=,(36,4,-26,4,),+,(36,5,-26,5,),+,(36,6,-26,6,),N=1222640+48584800+1867866560=1917674000,作业讲评,12-20 计算11,4,结果是什么？用二项式定理马上给出这个结果,解：用二项式定理计算：,11,4,=(10+1),4,=10,4,+4*10,3,+6*10,2,+4*10+1=14641,11,4,的结果从高位到低位恰好是二项式展开式中各项系数。,13-2 设f,n,是Fibonacci数，计算f,0,-f,1,+f,2,-.+(-1),n,f,n,解：f,0,-f,1,+f,2,-.+(-1),n,f,n,=(,(-1),n,f,n,-1,+,(-1),n,f,n,-2,)+(,(-1)n,-1,f,n,-2,+,(-1),n,-1,f,n,-3,)+,(,(-1),n,-2,f,n,-3,+,(-1),n,-2,f,n,-4,)+(,(-1),2,f,1,+,(-1),2,f,0,)+(,-f,1,)+f,0,=,(-1),n,f,n,-1,+f,0,=f,0,+,(-1),n,f,n,-1,作业讲评,13-6 求解递推方程,解：,(1)特征方程为x,2,-7x+12=0,特征根为,x,1,=3,x,2,=4,通解为：,a,n,=c,1,3,n,+c,2,4,n,代入初值得到：c,1,+c,2,=4 和 3c,1,+4c,2,=6,解得：c,1,=10，c,2,=-6,齐次方程的解为：a,n,=10*3,n,-6*4,n,或a,n,=10*3,n,-,3,*,2,2n+1,作业讲评,13-6 求解递推方程,解:,特征方程为x,2,-3x+2=0,特征根,x,1,=1,x,2,=2,齐次通解为：,因为,f(n)=,1，设特解为P,n,，代入方程得到P=-1,因此原递推方程的通解为：,代入初值得到：c,1,=1,c,2,=3,从而得到原递推方程的解为：,a,n,=3,*,2,n,-n+1,13-,7,已知方程,C,0,H,n,+C,1,H,n-1,+C,2,H,N-2,=6,的解是,3,n,+4,n,+2,其中,C,0,C,1,C,2,是常数，求,C,0,C,1,C,2,解,(,一,),:,递推方程,的解为,：,H,n,=3,n,+4,n,+2,令,n=0,1,2,3,代入得：,H,0,=4,，,H,1,=9,，,H,2,=27,，,H,3,=93,，,H,4,=339,将上述值代入已知条件得下述方程组,27C,0,+9,C,1,+4,C,2,=6,93,C,0,+27,C,1,+9,C,2,=6,339,C,0,+93,C,1,+27,C,2,=6,解,得,C,0,=1/2,C,1,=-7/2,C,2,=6,13-,7,已知方程,C,0,H,n,+C,1,H,n-1,+C,2,H,N-2,=6,的解是,3,n,+4,n,+2,其中,C,0,C,1,C2,是常数，求,C,0,C,1,C,2,解,(,二,),:由已知条件,递,推方程,的具有下述形式：,由于它的解是,H,n,=3,n,+4,n,+2,，因此上述递推方程的特征根是,3,和,4,，特解是,2,，从而递推方程具有形式：,H,n,-7H,n-1,+12H,n-2,=P,对比这个方程的两种形式，得到,C,1,=-7,C,0,C,2,=12,C,0,由于特解是,2,，因此得到：,C,0,=1/2,进而,C,1,=-7/2,C,2,=6,13-,8,有,n,条封闭的曲线，两两相交于两点，并且任意三条都不交于一点，求这,n,条封闭曲线把平面划分成的区域个数。,解,:设,a,n,为,n,条封闭曲线划分成的区域个数，假设前,n,条封闭曲线已经存在，当加入第,n+1,条封闭曲线时，这条曲线与前,n,条曲线交于,2n,个点，这些交点将第,n+1,条曲线划分成,2n,段，每段都会增加一个区域，因此,解,得：,13,-,15,使用两个不同的信号通信信道发送信息，传送一个信号需要,2,微秒，传送另一个信号要,3,微秒，一个信息的每个信号紧跟下一个信号。,(1),求与在,n,微秒中可以发送的不同信号数有关的递推方程,(2),递推方程,(1),的,初始条件？,(3),在,12,微秒内可以发送多少个不同的信息,解,:：,(1),设,a,n,表示,n,微秒内传送的不同信息数，,那么：,a,n,=,a,n-2,+,a,n-3,(2),a,1,=0,a,2,=1,a,3,=1,(3),从,a,4,=a,2,+a,1,=1,，,a,5,=a,3,+,a,2,=2,a,6,=a,4,+a,3,=2,a,7,=a,5,+a,4,=3,，,a,8,=a,6,+a,5,=4,，,a,9,=a,7,+a,6,=5,，,a,10,=a,8,+a,7,=7,a,11,=a,9,+a,8,=9,，,a,12,=a,10,+a,9,=12,在,12,秒内可以发送信息个数,a,12,=12,13,-,16,已知数列,a,n,的生成函数是,A(x)=(1+x-x,2,)/(1-x),求,a,n,解:,作业讲评,13-23 把,n,个苹果,(n,为奇数,),恰好分给,3,个孩子，如果第一个孩子和第二人孩子分的苹果数不同，问有多少种分法？,解：,每个孩子至少得到一个苹果的分法数是方数 x,1,+x,2,+x,3,=n-3 的非负整数解的个数，其生成函数为：,A(y)=(1+y+y,2,+.),3,=1/(1-y),3,展开式中y,n-3,项的系数为(n-1)(n-2)/2,前两个孩子苹果数相等的分法数为方程,2x,1,+x,3,=n-3 的非负整数解的个数，,当n为奇数时,x,3,为偶数,有(n-1)/2种取法,于是：,N=(n-1)(n-2)/2-(n-1)/2=(n-1)(n-3)/2,作业讲评,13-28,解：,an,的指数生成函数为：,于是：,作业讲评,13-29,解：设组成,n,位数的个数为,an,则,an,的指数生成函数,于是：,作业讲评,13-28 一个1*n的方格图形用红、蓝、绿或橙色涂色，如果有偶数个方格被涂成红色，还有偶数个方格被涂成绿色，问有多少种方案。,解：设方案为a,n,则a,n,的指数生成函数是：,作业讲评,13-29 确定由n个奇数字组成并且1和3每个数字出现偶数次的数的个数。,解：设组成n位的个数为a,n,则a,n,的指数生成函数是：,作业讲评,13-31 证明：,证明：等式右边对应了将n个不同的球放到x个不同的盒子且允许空盒子的方法数，即x,n,将这些方法按照有球的盒子数进行分类，只放入k个盒子的方法是：,因此总方法数需要对k求和，这就是得到等式左边的公式x,n,作业讲评,闽南师范大学 计算机学院,2014,年,11,月,第四部分 组合数学 作业,