离散作业布置及讲评.pptVIP

闽南师范大学 计算机学院 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位可重复选取，全部可能有36K，全字母有26k 包含4个字符有：(364-264) 包含5个字符有：(365-265) 包含6个字符有：(366-266) 所以全部：N= (364-264)+ (365-265) + (366-266) N=12226401867866560=1917674000 作业讲评 12-20 计算114结果是什么？用二项式定理马上给出这个结果 解：用二项式定理计算： 114=(10+1)4=104+4*103+6*102+4*10+1=14641 114的结果从高位到低位恰好是二项式展开式中各项系数。 13-2 设fn是Fibonacci数，计算f0-f1+f2-...+(-1)nfn 解： f0-f1+f2-...+(-1)nfn =((-1)nfn-1+(-1)nfn-2)+((-1)n-1fn-2+(-1)n-1fn-3)+ ((-1)n-2fn-3+(-1)n-2fn-4)+…+((-1)2f1+(-1)2f0)+(-f1)+f0 = (-1)nfn-1+ f0 = f0 + (-1)nfn-1 作业讲评 13-6 求解递推方程 解： (1)特征方程为x2-7x+12=0, 特征根为x1=3,x2=4 通解为：an=c13n+c24n 代入初值得到：c1+c2=4 和 3c1+4c2=6 解得：c1=10，c2=-6 齐次方程的解为：an=10*3n - 6*4n 或an=10*3n - 3*22n+1 作业讲评 13-6 求解递推方程 解:特征方程为x2-3x+2=0,特征根x1=1,x2=2 齐次通解为： 因为f(n)=1，设特解为Pn，代入方程得到P=-1,因此原递推方程的通解为： 代入初值得到：c1=1, c2=3 从而得到原递推方程的解为： an=3 * 2n - n + 1 13-7 已知方程C0Hn+C1Hn-1+C2HN-2=6的解是 3n+4n+2,其中C0,C1,C2,是常数，求C0,C1,C2 解(一):递推方程的解为： Hn=3n+4n+2 令n=0,1,2,3,代入得： H0=4，H1=9，H2=27，H3=93，H4=339 将上述值代入已知条件得下述方程组 27C0+9C1+4C2=6 93C0+27C1+9C2=6 339C0+93C1+27C2=6 解得C0=1/2, C1=-7/2, C2=6 13-7 已知方程C0Hn+C1Hn-1+C2HN-2=6的解是 3n+4n+2,其中C0,C1,C2,是常数，求C0,C1,C2 解(二):由已知条件递推方程的具有下述形式： 由于它的解是Hn=3n+4n+2,，因此上述递推方程的特征根是3和4，特解是2，从而递推方程具有形式： Hn-7Hn-1+12Hn-2=P 对比这个方程的两种形式，得到 C1=-7C0, C2=12C0 由于特解是2，因此得到 ： C0=1/2, 进而C1=-7/2, C2=6 13-8 有n条封闭的曲线，两两相交于两点