組合數(shù)學課后習題答案

第一章答案

1.(a)45({1,6},{2,7},{3,8},...,(45,50))

(b)45x5+(4+3+2+l)=235

(1-2~6,2-3~7,3—4?8,…,45—46~50,46—47?50,47—48~50,49—50)

2.(a)5!8!

(b)7!P(8,5)

(c)2P(5,3)8!

3.(a)n!P(n+l,m)

(b)n!(m+l)!

(c)2!((m+n-2)+l)!

4.2P(24,5)20!

5.2x5xP(8,2)+3x4xP(8,2)

6.(n+l)!-l

7.用數(shù)學歸納法易證。

8.41x31

niIhnk

9.設n=pipi...pk,則i?的除數(shù)個數(shù)為(2p]+l)(2p,+l)…(2Pk+l).

10.1)用數(shù)學歸納法可證n能表示成題中表達式的形式；

2)如果某n可以表示成題中表達式的形式，則等式兩端除以2取余數(shù)，可以確

定山；再對等式兩端的商除以3取余數(shù)，又可得a2；對等式兩端的商除以4取余數(shù),

又可得a3；…；這說明表達式是唯一的。

11.易用C(m,n)=m!/(n!(m-n)!)驗證等式成立。

組合意義：

右：從n個不同元素中任取r+1個出來，再從這r+1個中取一個的全體組合的

個數(shù)；

左：上述組合中，先從n個不同元素中任取1個出來，每一個相同的組合要生

復C(n-l,r)次。

12.考慮tcW=(l+x)",求導數(shù)后有t匕產(chǎn)=〃(l+x)"T,

k=0k=0

令x=l,即知汽kC；=n2"-'.

k=0

13.設此n個不同的數(shù)由小到大排列后為a,,a2,....%.當?shù)诙M最大數(shù)為ak時，

第二組共有2k“種不同的可能，第一組有29一1種不同的可能。故符合要求的

”-1

不同分組共有Z2k-'(2"-k-1)=(71-2)2"T+1種。

k=l

(另解：設兩組共含k個數(shù)(k=2,3”..,n),則分組數(shù)為

nn

X2^C(n,k)(k-l)=n2-'-2+l.)

14.3x2x2.

15：用k表示數(shù)的位數(shù)，用i表示k位數(shù)中零的個數(shù)，則0出現(xiàn)的次數(shù)為

6k-\6k-\

ZZ9cL9"'i=EZ91yT

=9+9x2+9x2)+(93x1x3+92x2x3+9x3x1)+(94x1x4+93x2x6+92x3x4+9x4x1)+

+(95x1x5+94x2x10+93x3xl0+92x4x5+9x5x1)

=95X5+94X24+93X45+92X40+9X15.

16.C(n-1,r-1)(每盒中先放一個，再r中取n-r(可重復))

17.易用P(m,n尸m!/(m-n)!驗證等式成立。

18.5!C(8-3+l,3)(先將球作全排列，再作8中選3的不相鄰組合)

19.在n+m位中選出n位不相鄰的位放入1,其余位放入0。故符號串個數(shù)為

20.代表團中含乙單位男同志的個數(shù)只可能是1,2,3,故組團的方案總數(shù)為

C(15,1)C(10,2)C(l0,4)+C(l5,2)C(10,l)C(l0,3)4+C(15,3)C(10,2)C(4,2)

第次為白球，則

21.設4=1,i

0,第i次為黑球''

6

尸(4=1且zA,=3)

6a?C；]_

產(chǎn)凡=1IZ&=3)=]

62

1P(24=3)

1

22.(a)C(3+2,3)C(5+3,5)(b)C(3+2,3)C(4+3,4)

(c)C(3+2,3)C(3+l,3)C(2+4,2)(d)C(8+5,5)-C(3+2,3)C(4+3,4)

23.Z取k+1時，x,y共有k?種取法，故第一-個式子成立,k=l,2,...,n。

另外，(x,y,z)中x與y相同的取法有C；+1種，x,y,z互不相同的取法有2。；］種，

故第二個式子成立。

24.(a)只需確定長方形的左下角和右上角坐標即可。

在0-9中任選兩不同數(shù)，小的作為左下角x坐標，大的作為右上角x坐標，共

有種選法；在0-5中任選兩不同數(shù)，小的作為左下角y坐標，大的作為右上角y

坐標，共有種選法。故共有個長方形。

(b)只需確定正方形的邊長和左下角坐標即可。

邊長k的取值范圍為1~5。邊長為k時，正方形左下角x坐標可取O...9-k,y

坐標可取0...5-k,共有(10*)(6人)種選法。故正方形的個數(shù)為

5

Z(10-&)(6—％)=105.

25.(a)C|j—C5+1

(b)G；-c；

26.S中被5整除的數(shù)有200個，不能被整除的有800個。

分兩種情況:(l)a,b中一個被5整除，另一個不能被5整除,共有200x800種取

法；(2)a,b均能被5整除，共有200x200種取法。所以，符合要求的數(shù)偶個數(shù)為

200x800+200x200=200x1000=200000.

27.(a)5!6!(b)5!6!(c)P(6,2)8!

28.假設每張桌坐n人，則方案數(shù)為

「nCn"nClnC'nCln—"

°kiU(k-)nYn°(A-=k-,

n

29.P(n,r)/r.

31.因為&q._L=c：,根據(jù)組合意義它是一個整數(shù)。

〃！r!

32.根據(jù)要求，x,y的排列必須是xyxyx.將其作為--個整體與a,b,c,d,e,f--起作排列，

共有符合要求的排列7!種。

33.每個盒中先放入k個球，然后作允許有重復的組合。共有C(n+(r-nk)-l,r-nk)種

方案。

34.2x7!

35.由于任意四個不同頂點恰好對應一個對角線的交點，故交點共有個。

36.若m=n2,設n的素因數(shù)分解為n=pJp,嗎.2嗎則m的除數(shù)個數(shù)為(2p/l)

(2p+l),..(2p+l),這是一個奇數(shù)。反之，若m的除數(shù)個數(shù)是奇數(shù)，則它的素因

2m22mkmk

數(shù)分解必為m=q2m]...q,從而m=n2,其中n=qmiqm...q0

12k12k

37.右為原點到(m,n+r+l-m)的路徑數(shù),左邊分別為原點分別經(jīng)線段AB的路徑數(shù)之

11

和，其中點Aj的坐標為(i,n-m),點B[的坐標為(i,n-m+1),i

38:可看成“仄ai,a2,...,an+i中選r+1個不同元素作為一組，共有多少種選法”的問

題。

左端：

C(n,r):此組含an+i，還要在a1,a2,…,an中選r個；

C(n-1,r):此組不含a(i+i，但含a.還要在ai,a2,…,am中選r-1個;

C(n-2,r):此組不含an+i,an，但含%-i，還要在ai,a2,…,a2中選r-2個；

39.考慮以下組合問題：用紅、藍、黃三種顏色給m個不同的球上色，要求涂黃色

球為m-n個，其余的球可隨意涂紅藍色。

從中隨意選定n個球用于涂紅色或藍色,其余球涂黃色，因此方案總數(shù)為C：；?2"。

另一方面，對于任意k(0<k<n),由于恰好有k個球涂紅色且符合要求的方案有

C：C：渣個，故全部方案按紅色球個數(shù)分組后有

D「n_、、「k「n-k

乙C加一乙—加_&?

k=0

40.Q：=P：/r!

43.易證當k+l<n/2時C*<C；+1,利用C*=C'；；k知k>n/2時C：>C/。

44.(a)編號1,2,...,n的球每種兩個，全部排列的個數(shù)；

編號l,2,...,n的球每種三個，全部排列的個數(shù)；

(b)編號1,2,…,n的球每種n個，將此〃個球全部放入n個無區(qū)別的盒中，要

求每盒n個球，全部放法的方案數(shù)。

45.(a)C(n,n)+C(n,n-l)+...+C(n,0)=2n.

(b)C(2n+1,0)+C(2n+l,1)+C(2n+1,n)=22n+1/2=22n.

46.(a)設出現(xiàn)偶數(shù)次0的長為n的字符串個數(shù)為時,則考慮末位為非0和末位為0

兩種情況，有遞推式

n-l1

an=2an.l+(3-an.i)=an.,+3"-=.......

n1n1nInlnlnIn

=3-+3-+...+3-+a1=3'+3-+...+3-+2=(3+l)/2.

(b)根據(jù)(a)得到等式右端；考慮0出現(xiàn)0次、2次、4次、….及所有偶數(shù)次的

情形，得等式左端。

47.使用第一臺和第二臺機器的人數(shù)均為k時，分配方案數(shù)為CfC1?3”口，故方

案總數(shù)為之CfC63…。

?=0

48.這相當于求從原點出發(fā)，中途必須行走在直線y=x及以上，最后到達點(n,n)

的全部路徑數(shù)C(n+n,n)-C(n+n,n-l)o

49.C(n-k+l,k)-

50.(a)在00000的間隔中插入1。使得01和10的總次數(shù)為4,只有兩種方法：一

是兩頭有1且中間一間隔插入余下的1；二是兩頭均無1且中間兩處插入全部的1。

兩頭有1共三種情形，中間插入1有四種選擇，此時共有3x4=12種方案。

兩頭無1時有C(4,2)種選擇間隔的方法，選定后每種方法有三種安排1的辦法

(前1后3,前2后2,前3后1),此時共有C(4,2)x3=18種方案。

所以，總方案數(shù)為12+18=30o

(b)在(T的間隔中插入1。

當k為奇數(shù)時，兩頭之一必為1,其余的1插入中間的(k-l)/2個空檔中。先讓

每個空中放入一個1,再將剩余的1任意放入這(k+l)/2個空中。此時符合要求的字

符串的個數(shù)為

k-\R+lk-\￡+1I

------m-------------in--------------_

2c3c2jt+1=2C,J1C?,-1^=2(0)2.

--—)-1

22

當k為偶數(shù)時，兩頭必須同時為1或同時為Oo

兩頭同時為0時，其余的1應插入中間的V2個空檔中，此時符合要求的字符

串的個數(shù)為

兩頭同時為1時.，其余的1應插入中間的(k-2)/2個空檔中，此時符合要求的字

符串的個數(shù)為

'二2時9J&

r1r2一0202

w-lvk+2k+2、,-vvm-\'

——+(m)-1

所以k為偶數(shù)時符合要求的字符串的個數(shù)為

k-k*-2*

Cm-

51.C(20-3+l,3)

52.C(n-k+l,k)

53.C(n+n-l,n)

54.相當于從n+m個位置中選取m個不相鄰的位置：

C(m+n-m+l,m)=C(n+l,m).

55.設m=ak...a2a]aia2...ak,貝ll

m=￡(《JO'e+%JOJ)=+]),

i=l?=1

2212i-2

因為102m+1=+[=￡式中每項均含因子

；=0J=O

11,故m能被11整除。

56.(a)Q"n'.=(n-l)!n!

(b)Q'：,P：

nI

57.C；(r-l)!(n-r-l)!=——

r(n-r)

58.如果交點無重疊，則四個點(的交叉連線)對應一個交點，故共有C：個點。

第二章答案

返回

1.母函數(shù)為

“X)=之"中=x(x(x([匚)')')'=x6x6x

H-----------------,

2

〃=01-X(l-x)(1)3(17)4

因為，；：；

2.7r\r=fcTX”,故此數(shù)列的母函數(shù)為

U-X)n=0

1

f(x)=￡C^+3x

n=0(1-x)4,

3.因為1-3x-54x2=(1+6x)(1-9x),設

3+78xAB

----------------------=+---------,

(1+6x)(1-9x)-----1+6x1-9x

解得A=-4,B=7o故G(x)=￡(7?9"一4.(一6)")x"，從而

an=7x9“-4x(-6)n。

n=0

4.類似上題可得an=8n+2x(?7)，

+

5.Gn-3Gn“+Gn-2=F2n-3F2n々+F21v4=F2n-1F2n-2-3F2n-2+F21M

=F2n-2+F2n-3-2F2n-2+F2n~4=-F2n-2+F2n-3+F2n-4=-F2n-2+F2n-2=0.

設母函數(shù)/*)=￡G”x"，則利用遞推式可得

n=0

r/、1一X

/(X)=~?

\-3x-x2

6.母函數(shù)

〃x)=￡((2“一1)”一+o.1")=￡⑵-i)x2"-'=x(Xx2"-'y

n=ln=ln=l

x(l+X2)

(1—小)2

7.因為爹+…合”=(占』號了所以

81

G(x)=Z(〃+1)A-2"=-----

n=0(I-X)

從而(1一/)G(x)==,(1-X2)2G(X)=1.

1-X

81

2

8.(a)/(x)=x"=-----r

”=o1-X

(b)f(x)=-±x2n+'=-^

i-x

81

(C)f(X)=Z(T)"=l~7

M=01+X

9?因為=￡C：：3x"，故G(x)=￡C3x"=.于是(a)(b)(c)均易證。

(1-x)汽M(1-X)

10.因為，故H(x)=￡c"x"=/下.于是(a)(b)均易證。

(1-X)MM(1-X)

11.由于Z(〃+l)x"=丁?，于是

〃=0(1—x)

G(X)=￡(”+1)2X"(￡(〃+i)x*|1+x

3

M=On=O(1-x)

從而(1-3X+3X2-1)G(X尸1+x是一個多項式。

12.G(x)=%X2"=9Z(〃+D"8E"=1白V白?F11-=盧1_Lv益

〃=o〃=o〃=o(1一%)1-x(1-x)

1

13「(、WnV/.、3nWnl+4x+X~11+4x+A

13.G(x)=￡??x"=￡(n+l)3x"￡x"

”=0n=0”=011-xjL-X

14.記/(x)=j一一r,則有

l-2x-x

(a)po=f(0)=0;pi=f'(0)=1.

(b)遞推關系式為an—2an-|—an.2=0,n=2,3,....

15.仿上題可得

,

(a)a0=f(0)=1;a]=f(0)=1.

(b)遞推關系式為an—an.i+an.2=0,n=2,3,....

16.略

17.因為71co，故G(x)=T1=y.于是(a)(b)(c)均易證。

(1—工)H=0(1—X)

18.(a)A-2n+B-4n

(b)(A+Bn)7n

(c)A-3n+B-(-3)n

(d)A-7n+B-(-l)n

(e)(A+Bn)6n

(f)A-5n+B-(-5)n

20-(a)A(1+V2)H+B(1-V2)n

3)坐(i+&)"一半—

44

(b)(i+V2)n+(i-V2r

nn

21.an=2-5+3-(-4)n特征方程為(r-4)(r+5)=0=遞推關系為an+an.l-an.2=0.

22.設“+xa+i+yan-2=0=>x=-2,y=-3=>遞推關系為an-2an-i-3an-2=0.

23.由an的表達式可推知特征方程為(X+3)2=0,從而遞推關系為an+3an一i+9an一2=0。

==

24.自用an—2an.i+an-20，ao=l,a]=2/導an=1+n,n0,1,2,...?

因為1是特征方程的二重根，故設a「2an」+3n一2=5的一個特解為代入

遞推式可得A=5/2。

2

故解為an=l+n+5/2n0

25.設z—：一4f，則

〃=o(1-x)(l+X-X)

88A_3*

￡b,,K"=E(a?-a,—)**=f(x)-xf(x)=----------

M=0n=01A+X—X)

26.因為G(x)=￡a"x",所以(GO)/=W￡a*a“_*x"=故

M=0n=0k=0?=0

l+(G(x))2x=l+￡a"+i=G(x).

n=0/J=0

nn+I

27.(a)an=A-4+5

nn

(b)an=A-(-6)+5/3-3

nn

(c)an=A-4+n-4

nn

(d)an=A-(-6)+4n-(-6)

nnn

(e)an=A-4+(10-5-3n-4)

nnn

⑴an=A-4+(7n-4+15-5)

nn2

(g)an=A-(-6)+(-6)-n(3/2+5/2-n+n)

nn2

(h)an=A-4+4-n(4/3+n+l/3-n)

3

(i)an=A+n(2+n)

nnnn

(j)an=A-3+B-4+10-2+13n-3

nnnn

(k)an=A-2+B-(-4)+2n-(-4)-18-3

nn2

(1)an=(A+Bn)-3+3-n/2

(m)對應的齊次線性常系數(shù)遞推關系式的特征方程為

X3-7X2+16X-12=0,E|J(X-2)2(X-3)=0,

故x=2(二重根),3(單根)，于是齊次線性常系數(shù)遞推關系式的通解為A-2n+B-3%

設遞推關系a:7az+l6am2T2a?3=2”的一個特解為CdC,代入后比較等式兩

端得C=-lo

設遞推關系2:72?|+16212-12加一3=311的一個特解為Dm311,代入后比較等式兩

端得D=9o

nn2n

故原遞推關系式的通解為an=A-2+B-3-n-2+9n-3%

nnnn

(n)an=A-2+n-2+3-3+2-4o

28.若a2=0,則an=0,*3；若azM,則an與a2同正負,n23。不妨設a/O,g1。

在原遞推式兩邊取對數(shù)，記bn=ln(aj則有

bn=3bn.i+10bn.2,

nnnn

解此遞推關系式,得bn=A-5+B-(-2),故an=exp(A-5+B-(-2))o

29.若ai或a2為0,則an=0,n23；若ai>0,a2<0,則a3k>0,a3k-i<0,a3k-2<0,k=l,2,3..；

若ai<0,a2>0,則a2+3k>0,a3k+i<0,a3k<0,k=0,l,2,3,…"若ai>0,a2>0,則ak>0,

k=l,2,3,...o

因此不妨設ai>0,a2>0(否則考慮bn=a?,,仍有關系b片瓦」也一2,求得也后即可

得到an)。在原遞推式兩邊取對數(shù)，記Cn=ln(an),則有

Cn=Cn-l+品-2,

解此遞推關系式，得

1+V51-娓〃”工(AJ+配5A一配、〃\

c〃=A(---)n+B(---)，從而a〃=exp(A(---)+8(---)).

30.在原遞推式兩邊取對數(shù)，記bn=ln(an),則有

bn=2bn.i+3bn.2,bo=O,bi=ln2.

nn

解此遞推關系式，得bn=3.(ln2)/4-(-l)-(ln2)/4,故

nn

an=exp(3-(ln2)/4-(-l)-(ln2)/4)。

31.在原遞推式兩邊取對數(shù)，記bn=ln(a)則有

bn=7bn-iT2bn_2,bo=O,b(=ln2.

nnnn

解此遞推關系式，得bn=44n2-3-ln2,故an=exp(4-ln2-3-ln2)。

32.(a)an=n!

n

(b)an=6-l/2

n

(c)an=A-l/2-l/3

專((土咨)"一(上:普尸)，而見，-a,i=尸工一

33.因為歹“=F,,2,所以

2222

一aH_i)+(a,1—an_2)+…+(勺-a。)=(戶;十]-Fw)+(FM-Fl^_l)+…+(F2-F,),

故%,=+33=A+1(^y^)n+，+1(^y^)n+1+1(-D".

34.因為(〃；2)=〃(〃+；)；〃+2)=+3〃2+2〃),所以

H(M+1)

%=%+；￡(小+31+2A)=A+、(("(〃+1))2+3.Ln(n+i)(2〃+1)+2-)

6k=\6262

.1431123

=AH—n+—n3'H---n+—n.

4242

35.類似上題，略。

36.(a)

a?=3a+3--1=3(3a?_2+3"-'-1)+3"-1

2n1

=32a“-2+23-(l+3i)=3(3??_,+3"?-1)+2-3-(1+3)

n12

=.......=3a0+n3"-(1+3+3+...+3"-,)

2n-l..1

--------3H---.

22

(b)

*=4a“_1+4"=4(4a?,,+4")+4"

2n,,+1,,+l

=4a?_2+(4+4)=42(4a,-+4")+(4"+4)

WM+,2

=.......=4"an+(4+4+...+4"-')

=1(42B-4").

3

2

37.令an=bn,則有bn=2bn.i+3bn.2,b0=l,bi=2.

nn+1nn+l2

用特征根法求得bn=((-l)+3)/4,故an=((-l)+3)/16o

38.令%=n!bn,則有bn=2bn-i+7,b0=l.

易解得bn=8x2”—7,從而an=(8x2"-7)n!.

39.令narbn,則有bn=bn-i+l,b]=l.

易解得bn=n,從而a()=5,an=1,n=l,2,....

n

40.(a)令an=n!bn,則有bn=4bn.2+5/9x3,bo=l,bi=-1.

nnn1

易解得bn=(2+3x(-2))/4-5x3-,從而

nn

an=(2+3x(-2))/4—5x3*1)n!.

n

(b)令an=n!bn,則有bn=9bn-2+14x2,bo=42,bi=38.

nnn

易解得bn=(82x3+44x(-3))/3-4x2,從而

nnn

an=((82x3+44x(-3))/3-4x2)n!.

41.證：(an+bian.|+b2an.2)—r(an-i+ba.2+b2an.3)=51—rx5r”」=0,

即an+(bi—r)an.|+(b2—rbi)an.2—rb2an.3=0,

這是一個三階齊次線性常系數(shù)遞推關系，其特征多項式為

322

x+(bi-r)x+(b2-rbi)x-rb2=(x-r)(x+bix+b2).

c—c.i—c.2=

42.由題設條件立得nnnbn.i.

記dn=Cn—Cn-l—Cn-2,則由bn的遞推關系有dn—dn-l—dn-2=0，即

=

品—2cn-］一品々+2cn，3+Cn40.

47.(1)由(1+X)n(l+X)n=(l+X)2n,展開后比較兩邊X*1的系數(shù)，得￡。卜丁=4.

*=0

(2)由于

(l+x4+x8)100=Z100.ln,.(x4)"2-(x8)"3,

〃1+〃2+〃3=1001”l"2”3>

故X2°的系數(shù)為

(1001(100)100!100!100!

/=/=--------1---------F-------

100

盯+〃2+〃3=1。。1"1"27W1+/I2+/?3=\1“2”3J95!5!0!96!3!1!97!1!2!

4w2+8/ij=20n2+2n}=5

48.(1+x+x2)4(1+x+x~+x^)^=...+678x1°+…

49.設n位排列中AB至少出現(xiàn)一次的排列個數(shù)為an,則最后兩位為AB的排列有

4n-2個；最后兩位不是AB的排列分為兩種情況：最后一位不是B的情形有3an.,個,

最后一位是B的情形有3an-2個，故

n2

an=3an-i+3an-2+4-,n=3,4,….

ai=0,22=1。

50.這是一個可重復的排列計數(shù)問題，可以使用指數(shù)型母函數(shù)求解。

出現(xiàn)偶數(shù)次2的指數(shù)型母函數(shù)為之上，出現(xiàn)偶數(shù)次3的指數(shù)型母函數(shù)為

￡(2〃)！

￡上，出現(xiàn)0的指數(shù)型母函數(shù)為￡上，出現(xiàn)1的指數(shù)型母函數(shù)為￡上。所以

士(2〃)！占〃！士〃！

總的母函數(shù)為

22

n2,8

8X~y—e+ee"=^(e4x+2e2x+l),

Sw!(“=on\~T

nn1

故ao=l,an=(4+2^)/4,n=l,2,....

51.設n位符號串中符合要求的排列有a。個，則最后一位不是a的排列有2a”“個,

最后一位是a的排列有2ali一2個。于是

an=2an-i+2an.2，n=3,4,….

ai=3,22=8。

52.證:由p.36恒等式,知仁這%這

k=0k=0

54.因為相應的母函數(shù)為

345

^Xk^Xky^Xk=...+14x8+…，

k=0k=0k=0

故共有14種分配方案。

55.用數(shù)學歸納法：n=l時，n可表示為Fi；設n=k時，

k=乙+居.,+...+尸卻,其中2<%<i2V…<i,”，

⑴若ii>2,則左+1=居+F.+幾+...+Fim;

（ii）若ii=2,設p=max{k:ik=k+l,l<k<m}?當p<m時，因為F|+F2+...+Fp=Fp+2—1>

+4j%+…+紇盟+%+”；+.??+￡；

當p=m時k+1=Fm+2o

56.設n個平面將整個空間分為Dn部分。根據(jù)p.158例54的結果，因為其它平面

總與第n平面相交于一條直線，因此第n平面被前n-1個平面分為l+n（n-l）/2個部

分，而每個部分將前n-l個平面分割得到的一個區(qū)域變?yōu)閮蓚€，故有

Dn=Dn.i+l+n（n-l）/2,n=2,3,....

由于Di=2,可推得Do=1.

由遞推式得?！敝?+空二D）+l，可設=A+即+CC：+￡>C，代入

k=\乙

n=0,l,2,3的Dn值，知A=l,B=l,C=l,D=4o

57.設a。為符合要求的n位二進制數(shù)的0的總個數(shù)，0為符合要求的n位二進制數(shù)

的個數(shù)，則an中尾為0的n位二進制數(shù)的0的總個數(shù)為an.2+bn.2.an中尾不為0的

n位二進制數(shù)的0的總個數(shù)為卻」；&中尾為0的n位二進制數(shù)的個數(shù)為％一2,%中

尾不為0的n位二進制數(shù)的個數(shù)為bn」；故

an=（an.2+bn.2）+an.i

+

bn=bn-2bn-i,n=3,4,….

ai=l,a2=2,bi=2,b2=3.

58.設如為n個盤按編號的奇偶性要求移動到目的地的移動總次數(shù)，壯為n個盤移

動到目的地的移動總次數(shù)（不管編號的奇偶性），則

n為奇數(shù)時，先將上面n-l個盤移到B柱（移動b6i次），然后將最后一個盤移至

C柱（移動1次）；再將B柱上面n-3個盤移到A柱（移動bn.3次），而后將B柱最上面

的盤移至C柱（移動1次）。最后根據(jù)假設，A柱中剩下的n-3個盤按編號的奇偶性

要求移動到目的地的移動總次數(shù)為a。一3,故

an=bn.i+l+bn.3+l+an.3?

n為偶數(shù)時，情況完全類似，只需在移動的辦法中將B與C的地位對換即可。

這時仍有an=bn.]+l+bn.3+l+an.3?

n

對于，按照漢諾塔問題有bn=2bn.1+l,b1=l,可以解得bn=2-l.

于是有

nn2

an=an.3+(2-'+2-),n=4,5，….

Hj_1922=2,23=5o

59.設AD=a,貝1」48=匕好《。因為矩形B】BCG中B1C=a,

2

1+y[5V5—1

DD=---------a—a=--------,

1}22

故B(:BIB=F—=匕蟲.

''V5-12

a

2

即新的矩形與原矩形相似。

60.使用數(shù)學歸納法。n=l時等式成立。設n時等式成立，則對于n+1,有

故命題成立。

61.設符合要求的n位符號串的個數(shù)為a。，則其中最后??位不是0的符號串有an.i

個，最后一位是0的符號串有a。一2個。于是

=

an3n-l+3n-2>n=3,4,….

a?=2,a2=3o

62.設圓周上符合要求的n個點的弦將整個圓分為a。部分。

因為圓周上不同的四點對應一個交點(四點構成的四邊形的兩對角線的交點),

故從第n點出發(fā)所作的弦新增的交點個數(shù)為,從第n點出發(fā)所作的弦被交點分

隔后共有(n-l)+C3段(n-1為與其它點相連的段，每增加一個交點即增加一段)，

于是而每段將前n-1個點分割得到的一個區(qū)域變?yōu)閮蓚€，故有

/1(〃—1)("—2)(〃—3)\..

a=a-i+((n-l)+----------------------),n=4,5

nn6

由于a1=l,可推得a()=l.

因為%=i+￡(i+(-2)(y)),可設

*=i6

瑪=A+5〃+C?C：+C.C；+E?C：,代入n=0,1,2,3,4的an值，知A=l,B=0,C=l,

D=0,E=lo

63,設符合要求的n位二進制數(shù)的個數(shù)為a。，則其中最后一位不是1的二進制數(shù)有

an」個，最后一位是1的二進制數(shù)有an一2個。于是

an=an.i+an-2,n=3,4,….

ai=2,a2=3。

64.設符合要求的m位排列的個數(shù)為am，所選的k個文字已定、最后一位所用文字

已定且符合要求的m位排列的個數(shù)為％,則am=C(n,k)kbmo由于最后兩位文字互

異時有(k-1)bm.i種排列，最后兩位文字相同時有(k-1)bm一2種排列,故

bm=(k-l)bra.i+(k-l)bm-2,m=3,4,….

b|=l,b2=ko

65.類似書上例題可得

Sn-6Sn.i+15Sn,2-20Sn-3+15Sn-4-6Sn-5+Sn-6=0,

對應特征方程為(r-l)6=0,故有六重根r=l.于是

Sn=A+B-C(n,1)+C-C(n,2)+D-C(n,3)+E-C(n,4)+F-C(n,5),

將S”S2.........S6的值代入，解線性方程組即可確定全部待定常數(shù)。

66.用數(shù)學歸納法易證

(:2)=(；；其中盤=2%一3",〃=2,3,

解以上后面部分的遞推關系式，得如=203、n=I,2,3,...

67.(1)類似書上例題可得一個齊次線性常系數(shù)遞推關系，其特征方程僅有一個四

重根x=l。故可設S“=A+B〃+C?C；+￡>C^So,Si，S2,S3的值代入，得A=0,

B=0,C=2,D=2.

(2)類似書上例題可得一個齊次線性常系數(shù)遞推關系，其特征方程僅有一個四

重根x=l。故可設S“=A++將So,Si，S2,S3的值代入，得A=0,

B=3,C=5,D=2.

(3)類似書上例題可得一個齊次線性常系數(shù)遞推關系，其特征方程僅有一個五

重根x=l。故可設S,=A+B〃+C-C：+OC+E-C,：MSO,SI，S2,S3,S4的值代

入，得A=0,B=6,C=18,D=18,E=6.

68.根據(jù)題設a「2,a2=4,且有以下遞推關系：

a2n+i=a2n+2,a2n+2=a2n+i+(2n+2),n=l,2,....

故a2n+i=a2n-i+(2n+2),n=l,2,....

于是a2n+i=a21vl+(2n+2)=(2n+2)+2n+…+4+ai=(n+l)(n+2),

從而a2n=a2n-i+2n=n(n+1)+2n=n(n+3)o

所以a2n=n(n+3),a2n+i=(n+l)(n+2),n=l,2,....

70.(a)此題結果有誤，當/為偶數(shù)時三角形的個數(shù)應為/(/+2)/4。

易知三邊(a,b,c),O<aWbWc能構成三角形的充要條件是a+b>c。因此，當邊長為整

數(shù)、最大邊長為/時：

(i)若/=2m+l時，全部三角形為

(k,i,2m+l),1<k<i<2m+l,i+k>2m+2,

當取定k后，i的取值范圍為max{k,2m+2-k)<i<2m+lo所以當14kWm+l時,

2m+2-k<i<2m+l；當k>m+l時，k<i<2m+l()

故三角形的個數(shù)為

c,、Q"+l)(m+2)(3m+3)m

2_^k++2-k)=-----------------+(2m+2)m...........—

k=lk=m+222

(m+l)(/n+2)(m+l)m(m+1)(2zn+2)

---------1------=----------=(?l+l)2

222

(ii)若/=2m時，全部三角形為

(k,i,2m),1<k<i<2m,i+k>2m+1,

當取定k后，i的取值范圍另max{k,