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

1、闽南师范大学 计算机学院 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

2、(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个字符的登录密码，每个字符是大写字母或者数字，且每个密码必须包含一个数字，问有多少个可能的登录密码？ 解：大写字母2

3、6个,数字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=1222640+48584800+1867866560=1917674000,作业讲评,12-20 计算114结果是什么？用二项式定理马上给出这个结果 解：用二项式定理计算： 114=(10+1)4=104+4*103+6*102+4*10+1=14641 114的结果

4、从高位到低位恰好是二项式展开式中各项系数。,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

5、=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

6、=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

7、=P 对比这个方程的两种形式，得到 C1=-7C0, C2=12C0 由于特解是2，因此得到 ： C0=1/2, 进而C1=-7/2, C2=6,13-8 有n条封闭的曲线，两两相交于两点，并且任意三条都不交于一点，求这n条封闭曲线把平面划分成的区域个数。 解:设an为n条封闭曲线划分成的区域个数，假设前n条封闭曲线已经存在，当加入第n+1条封闭曲线时，这条曲线与前n条曲线交于2n个点，这些交点将第n+1条曲线划分成2n段，每段都会增加一个区域，因此 解得：,13-15 使用两个不同的信号通信信道发送信息，传送一个信号需要2微秒，传送另一个信号要3微秒，一个信息的每个信号紧跟下一个信号。 (1

8、) 求与在n微秒中可以发送的不同信号数有关的递推方程 (2) 递推方程(1) 的初始条件？ (3) 在12微秒内可以发送多少个不同的信息 解:： (1) 设an表示n微秒内传送的不同信息数， 那么： an= an-2+ an-3 (2) a1= 0, a2= 1, a3= 1 (3) 从a4= a2+a1=1， a5= a3+ a2 =2, a6= a4+ a3 =2 a7= a5+ a4 =3， a8= a6+ a5 =4， a9= a7+ a6 =5， a10= a8+ a7 =7, a11= a9+ a8 =9， a12= a10+ a9 =12 在12秒内可以发送信息个数 a12=12

9、,13-16 已知数列an的生成函数是 A(x)=(1+x-x2)/(1-x), 求an 解:,作业讲评,13-23 把n个苹果(n为奇数)恰好分给3个孩子，如果第一个孩子和第二人孩子分的苹果数不同，问有多少种分法？ 解：每个孩子至少得到一个苹果的分法数是方数 x1+x2+x3=n-3 的非负整数解的个数，其生成函数为： A(y)=(1+y+y2+.)3=1/(1-y)3 展开式中yn-3项的系数为(n-1)(n-2)/2 前两个孩子苹果数相等的分法数为方程 2x1+x3=n-3 的非负整数解的个数， 当n为奇数时, x3为偶数,有(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的方格图形用红、蓝、绿或橙色涂色，如果有偶数个方格被涂成红色，还有偶数个方格被涂成绿色，问有多少种方案。 解：设方案为an,则an的指数生成函数是：,作业讲评,13-29 确定由n个奇数字组成并且1和3每个数字出现偶数次的数的个数。 解：设组成n位的个数为an,则an的指数生成函数是：,