组合数学第2章答案(8)

特征方程为：

解得a、b为2重根。 设

分析上式结构可得：

把n=2代入可解得：

代入an

可得方程组

解得

2.58 在河内塔中A柱上共有从1到n编号的n个盘，现在要将偶数编号与奇数编号的盘分别套在B柱和C柱上，试问共要作多少盘次的转移，规则不变。 解 设n为偶数

1）先把n-1个盘通过B移到C 2）把第n个盘移到B

3）把n-3个盘通过B移到A 4）把第n-2个盘移到B

对n为奇数时上述四步仍然成立，但是B、C对调。 所以K(n)=H(n-1)+1+H(n-3)+1+K(n-3)

其中K(1)=1,K(2)=2,K(3)=5,H(k)为河内塔数列。 K(n)-K(n-3)=2n-1+2n-3 2[K(n-1)-K(n-4)]=2n-1+2n-3 可得特征方程：

(x-2)(x3-1)=0

(x-2)(x-1)(x2+x+1)=0 解得

X1=1,x2=2,x3,4=

K(n)=A2n+B+Ccosn代入初值可解得

?n k(n)?? 2??7?7??53

2.59 设一矩阵ABCD，其中AB：AD =

12(1?5)，作C1B1使AB1C1D是一正方

形，试证B1C1CB和ABCD相似，试证继续这一过程可得一个与原矩形相似的矩形序列

解：...

把AD看成1 则AB为

继续重复此过程，那么下一个矩形同理会相似于B1C1CB，所以也会相似于原矩形。 2.60：试证：

=

解： 用数学归纳法 1：n=2时，

=

成立

2： 设n=k时成立即 当n=k+1时

=

=

==

由1,2得证题设成立.

2．61 求长度为n的符号串,只在最后两位才出现00的符号串总数.

解:设所求的串的个数为an,相邻不同为0的串的个数为bn bn=bn?1+bn?2; an=bn?3 则an=bn?4+bn?5 ,即an=an?1+an?2

特征方程为: x2-x-1=0.

特征根为: x1=(1+5)/2 ,x2=(1-5)/2 通解为: an=A*((1+5)/2)n+B*((1-5)/2)n 由初始条件a1=0, a2=1 得

an=((1-5)2/2(5-5))((1+5)/2)n +(2/(5-5))((1-5)/2)n 2.62 在一圆周上取n个点，过一对定点可做一弦，不存在三弦共点的现象，求弦把圆分割成几部分?

解 ：n-1个点把圆分为an-1部分，加上第n个点则对于前n-1个点来说，每选取3个点都有3条弦构成一个三角形，而中间的一点和第n点的连线把中间点与第n点间的弦分为两个部分，增加了一个域。而对第n点与其他n-1点的连线有把第1、n-1、n点构成的三角形分为n个域。

2．63 求n位二进制数中相邻两位不出现11的数的个数

解 设所求个数为an,第n位为0或1，是0，有an-1；是1，则n-1位为0,有an-2. an?an?1?an?2, a0?1,a1?2,a2?3,a3?5

1?251?25 特征方程为 x2?x?1?0,?x1?an?Ax1?Bx2

A?B?1?? 1?5?1?5A?B?2?2?2nn, x2?

代入得

2?1?1?5???A????2??5?? ?2??11?5???B?????2?5???所以an?1?1?5n?21?5n?2???()?()?

225??

2.64 从n个文字中取k个文字做允许重复的排列，但不允许一个文字连续出现3次，求这样的排列的数目。 答案：

设所求为ak则

ak?(n?1)ak?1?(n?1)ak?2

233a1?n，a2?n，a?n?n

特征方程为：x2?(n?1)x?(n?1)?0 解得

x?(n?1)?(n?1)(n?3)2

可设 an?Aan?B?n

把初值代入即可求得A，B=>an

2.65 求 14+24+34+…+n4的和.

解：??Sn?1?Sn?1?Sn??1?n?4是n的4次方

∴Sn?1满足递推关系

Sn?6Sn?1?15Sn?2?20Sn?3?15Sn?4?6Sn?5?Sn?6?0 代入可解得

?A1?A?2? ?A3?A?4??A5?1?15?50 ?60?24 Sn?32.66 求矩阵??0??3解：设??0??3n?1?n??n??n??n??n???????????1???15???50???60???24??? 12345???????????1??2??n100

an??3??n?1??2??0n?1?3n?1??=???02???1??3?=??2???0n?1?1??3n?1???2???0?3n?1an?1?? n?1?2?nn?2an?1?3an?1?2,an?1?2,an?2?3

?3所以??0??1??2??100?3100=??0?2100?31001002?? ??2.67 求

百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说综合文库组合数学第2章答案(8)在线全文阅读。