组合数学参考答案（卢开澄第四版）- 修改版

1.1 题 从{1，2，……50}中找两个数{a，b}，使其满足 （1）|a-b|=5； （2）|a-b|?5；

解：（1）：由|a-b|=5?a-b=5或者a-b=-5，

由列举法得出，当a-b=5时，两数的序列为（6，1）（7，2）……（50，45），共有45对。 当a-b=-5时，两数的序列为（1，6），（2，7）……（45，50）也有45对。 所以这样的序列有90对。 （2）：由题意知，|a-b|?5?|a-b|=1或|a-b|=2或|a-b|=3或|a-b|=4或|a-b|=5或|a-b|=0； 由上题知当|a-b|=5时 有90对序列。 当|a-b|=1时两数的序列有（1，2），（3，4），（2，1）（1，2）…（49，50），（50，49）这样的序列有49*2=98对。 当此类推当|a-b|=2，序列有48*2=96对，当|a-b|=3时，序列有47*2=94对，当|a-b|=4时，序列有46*2=92对， 当|a-b|=0时有50对

所以总的序列数=90+98+96+94+92+50=520

1.2题 5个女生，7个男生进行排列，(a) 若女生在一起有多少种不同的排列？(b) 女生两两不相邻有多少种不同的排列？(c) 两男生A和B之间正好有3个女生的排列是多少？

解：（a）可将5个女生看作一个单位，共八个单位进行全排列得到排列数为：8！×5！， （b）用x表示男生，y表示空缺，先将男生放置好，共有8个空缺， Y X Y X Y X Y X Y X Y X Y X Y

在其中任取5个得到女生两两不相邻的排列数： C（8，5）×7！×5！ （c）先取两个男生和3个女生做排列，情况如下： 6. 若A，B之间存在0个男生， A，B之间共有3个人，所有的排列应为 P6=C(5,3)*3!*8!*2 1．若A，B之间存在1个男生， A，B之间共有4个人，所有的排列应为 P1= C(5,1)*C(5,3)*4!*7!*2 2．若A，B之间存在2个男生，A，B之间共有5个人，所有的排列应为 P2=C(5,2)*C(5,3)*5!*6!*2 3．若A，B之间存在3个男生，A，B之间共有6个人，所有的排列应为 P3=C(5,3)*C(5,3)*6!*5!*2 4．若A，B之间存在4个男生，A，B之间共有7个人，所有的排列应为 P4=C(5,4)*C(5,3)*7!*4!*2 5．若A，B之间存在5个男生，A，B之间共有8个人，所有的排列应为 P5=C(5,5)*C(5,3)*8!*3!*2

所以总的排列数为上述6种情况之和。

1.3题 m个男生，n个女生，排成一行，其中m,n都是正整数，若

(a)男生不相邻(m?n?1); (b)n个女生形成一个整体； (c)男生A和女生B排在一起； 分别讨论有多少种方案。

解：(a) 可以考虑插空的方法。

n个女生先排成一排，形成n+1个空。因为m?n?1正好m个男生可以插在n+1个空中，形成不相邻的关系。

则男生不相邻的排列个数为

ppnn?n?1m

(b) n个女生形成一个整体有n！种可能，把它看作一个整体和m个男生排在一起，则排列数有(m+1)!种可能。 因此，共有n!?(m?1)!种可能。

(c)男生A和女生B排在一起，因为男生和女生可以交换位置，因此有2！种可能， A、B组合在一起和剩下的学生组成排列有(m+n-1)！

(这里实际上是m+n-2个学生和AB的组合形成的)种可能。共有组合数为2!?(m?n?1)! 1.4题 26个英文字母进行排列，求x和y之间有5个字母的排列数 解：C（24，5）*13！

1.5题 求3000到8000之间的奇整数的数目，而且没有相同的数字。

解：根据题意，千位可以从3，4，5，7，6中选取，个位可以从1，3，5，7，9中选取；因此 2*5*8*7+3*4*8*7=1232 1.6 题 计算，1·1！+2·2！+3·3！+。。。+n·n！ 解：由序数法公式可知 1!+1=2! 2·2!+1·1!+1=3! 3·3！+2·2！+1·1！+1=4！

n·n!+(n-1)(n-1)!+。。。+2·2!+1·1!+1= (n+1)!

所以1·1！+2·2！+3·3！+。。。+n·n！=(n+1)!－１

n

1.7题 试证：(n?1)(n?2)?(2n)被2除尽。

n证明：因(2n)!?2n!(2n?1)!!

(n?1)(n?2)?(2n)n!(n?1)(n?2)?(2n)(2n)!???(2n?1)!! nnn2n!2n!2因为(2n-1)!!是整数所以(n?1)(n?2)?(2n)能被2n除尽。

1

1．8题 求10和20的公因数数目。

404040403010306030402030解：因为10?2*5?2*5*5 20?2*5?2*2*5

4030 它们最大公因子为2*5转化为求 最大公因子 能除尽的整数个数，能除尽它的整数是

ab 2*5,0??a??40,0??b??30

根据乘法法则，能除尽它的数个数为 41*31=1271

21.9题 试证n的正除数的数目是奇数。

22证明：设有0?a?n,n?b?n, 则一定有表达式n?a?b，

则 可知符合范围的a和b必成对出现，所以为偶数。

22n又当a=b=n时，表达式n=a?b仍然成立。 所以的正除数的数目是“偶数?1”为奇数。 1.10题 证任一正整数n可唯一地表成如下形式:

证：对n用归纳法。

先证可表示性：当n=0,1时，命题成立。 假设对小于n的非负整数，命题成立。 对于n,设k!≤n＜(k+1)!,即0≤n-k!＜k·k!

,0≤ai≤i,i＝1,2,…。

4030由假设对n-k!,命题成立，设

，其中ak≤k-1,，命题成立。

再证表示的唯一性：设

, 不妨设aj＞bj,令j=max{i|ai≠bi}

aj·j!+aj-1·(j-1)!+…+a1·1! =bj·j!+bj-1·(j-1)!+…+b1·1!,

(aj?bj)?j!??(bi?ai)?i!?j!??i?i!??bi?ai?i!??(bi?ai)?i! 矛盾，命题成立。

1.11题 证明nC(n-1,r)= (r+1)C(n,r+1),并给予组合解释.

证：nC(n?1,r)?n(n?1)!(r?1)?n!(r?1)?n!???(r?1)C(n,r?1)

r!?(n?r?1)!(r?1)?r!?(n?r?1)!(r?1)!?(n?r?1)!所以左边等于右边

组合意义：等式左边：n个不同的球，先任取出1个，再从余下的n-1个中取r个；

等式右边：n个不同球中任意取出r+1个，并指定其中任意一个为第一个。 所以两种方案数相同。 1.12题 证明等式：

?kC(n,k)?n2k?1nn?1

?n?1?n?n?1?n?1?n?1?n?1?n?n?nC(n?1,0)?C(n?1,1)?L?C(n?1,n?1)?n2?右边 ?? 证明： 等式左边??n????????k?1k?1sk?1??k?1??s?0??n1.13题 有N个不同的整数，从中间取出两组来，要求第1组的最小数大于另一组的最大数。

解题思路：（取法由大到小）

第1步：从N个数由大到小取一个数做为第一组，其它N-1个数为第二组，

组合数为：c（n,1）*{c(n-1,1)+c(n-1,2)-…+c(n-1,n-1)}

第2步：从N个数由大到小取两个数做为第一组，其它N-2个数为第二组，

组合数为：c（n,2）*{c(n-2,1)+c(n-2,2)-…+c(n-2,n-2)} …

第n-2步：从N个数由大到小取n-2个数做为第一组，其它2个数为第二组，组合数为：c（n,n-2）*{c(2,1)} 第n-1步：从N个数由大到小取n-1个数做为第一组，其它1个数为第二组，组合数为：c（n,n-1）*{c(1,1} 总的组合数为：

C(n,1)?{C(n?1,1)?C(n?1,2)??

?C(n?1,n?1)}?C(n,2)?{C(n?2,1)?C(n?2,2)??C(n?2,n?2)}?C(n,n?2)?{C(2,1)?C(n,n?1)?C(1,1)}2

1.14 题 6个引擎分列两排，要求引擎的点火顺序两排交错开来，试求从特定一引擎开始有多少种方案？

解：第1步从特定引擎对面的3个中取1个有C(3,1)种取法，

第2步从特定引擎一边的2个中取1个有C(2,1)种取法，

第3步从特定引擎对面的2个中取1个有C(2,1)中取法，剩下的每边1个取法固定。 所以共有C(3,1)?C(2,1)?C(2,1)=12种方案。

1.15题 求1至1000000中0出现的次数。

解：当第一位为0时，后面6位组成的数可以从1-100000，共100000个0；

当第二位为0时，当第一位取0-9时，后面5位可以取1-9999，此外当第一位取0时，后面5位还可以取为

10000，这样共有9999*10+1=99991个0；

同理第三位为0时，共有99901个0； 第四位为0时，共有99001个0；第五位为0时，共有90001个0；

第六位为0时，只有1个0；

这样总共的0数为：100000+99991+99901+99001+90001+1=488895。

1.16题 n个相同的球放到r个不同的盒子里，且每个盒子里不空的放法。

解：如果用“O”表示球，用“|”表示分界线，就相当于用r-1个“|”把n个“O”分成r份，要求是每份至少有一个球。如下图所示： 00|00000000|00000000|00000|000000……

对于第一个分界线，它有n-1种选择，对于第二个分界线只有n-2个选择，(因为分界线不能相临，如果相临它们之间就没有了球，这不合要求)，依次第r-1个分界线只有n-(r-1)种选择。但是这样的分法中存在重复，重复度为(r-1)!,所以总得放法为：(n-1)*(n-2)*…*(n-r+1)/(r-1)!=C(n-1,r-1)。 1.18题 8个盒子排成一列，5个有标志的球放到盒子中，每盒最多放一个球，要求空盒不相邻，问有多少种排列方案？

5解：要求空盒不相邻，这样球的位置共有8种。而不同标志的球的排列有p5?5!。所以共有8*5！种排列。 8种排列如下两类。因为要求空盒不相邻，途中1代表球

a) 1 1 1 1

b) 1 1 1 1

在a)中 剩下的一个球有四种位置，b)中剩下的一个球也有四种位置，两者合起来一共有8种 1.17题 n和r都是正整数，而且r?n，试证下列等式： (a)p?nprnn?1r?1nr(b)nr?1pprnr?(n?r?1)p?r!?r(pnr?1nr?1(c)n?1r?1pnr?nn?rpn?1r,r?n

(d)pn?1r?p?rp(e)n?1?p?L?prr?1) 解：(a) npn?1r?1?n?n(n?1)!n!??(n?r)!(n?r)!?(n?r?1)?pnr等式成立。

nn!n!??pr?1pr等式成立。

(n?r?1)!(n?r)!n?1nnn(n?1)!n!(c) ????p等式成立。 prrn?rn?r(n?r?1)!(n?r)!(b) (n?r?1)(d)

pnr?rpnr?1?n!n!n!(n?r?1)n!(n?1)!?n!?r?r?n!(n?1)!?r???r????(n?r)!(n?r?1)!(n?r?1)!(n?r?1)!(n?r?1)!(n?1?r)!pn?1r

(e)利用(d)的结论可证明本题。

r!?r(pnr?1?pn?1r?1?L?prr?1)?p?rp?rp?L?rp?p?rp?rp?rp?L?rp?rp?p?rp?rp?L?rp?rp?prr?1r?1r?1rrrr?1r?1r?2r?1n?1r?1nr?1r?1rr?1r?1r?2r?1n?1r?1nr?1rnn?1r

n?1rr?11.19题 n+m位由m个0，n个1组成的符号串，其中n≤m+1,试问不存在两个1相邻的符号串的数目。 解：m个0进行排列，留出m+1个空挡，任选n 个空挡放1，共有C(m+1,n)种方案.

1.21题 一个盒子里有7个无区别的白球，5个无区别的黑球，每次从中随机取走一个球，已知前面取走6个，其中3个是白的，试问取第6个球是白球的概率。

解：C（6,2）*C(5,2)*C(5,3)/C(5,3)C(7,3)C(6,3)=3/14

3

1.20 题 甲单位有10个男同志，4个女同志，乙单位有15个男同志，10个女同志，由他们产生一个7人的代表团，要求其中甲单位占4人，而且7人中男同志占5人，试问有多少中方案？

解：1.甲单位出4个男同志，乙单位出1个男同志，从乙单位出2个女同志 C(10,4)*C(15,1)*C(10,2)=141750 2. .甲单位出3个男同志，乙单位出2个男同志，从甲单位出1个女同志,从乙单位出1个女同志。 C(10,3)*C(15,2)*C(4.1)*C(10,1)=504000

3. .甲单位出2个男同志，乙单位出3个男同志，从甲单位出2个女同志. C(10,2)*C(15,3)*C(4,2)=122850 1+2+3即为所求，总的方案数为768600 1.22题 求图1-22中从O到P的路经数: P (a) 路径必须经过A点; (b) 路径必须过道路AB; (c) 路径必须过A和C (d) 道路AB封锁(但A,B两点开放) C 解: (a)分两步走O(0,0)→A(3,2) A(3,2)→P(8,5)，根据乘法法则: A B ?3?2??3?5?N???2?????3???560

???? 3?2??4?3?(b)分两步走O(0,0)→A(3,2), B(4,2)→P(8,5)，根据乘法法则:N????????350

?2??3?????3?2??3?1??2?2?(c)分三步走: O(0,0)→A(3,2), A(3,2)→C(6,3), C(6,3)→P(8,5), 根据乘法法则: N?? ??2?????1?????2???240?????? （d）AB封锁路径数加必经AB路径数即O(0,0)→P(8,5)的所有路径数有加法法则可得：

?5?8??3?2??4?3? N??

?5?????2?????3???1287?350?937??????1.23题 令s={1,2,…,n+1},n≥2,T={(x,y,z)|x,y,z∈s, x

(1)可先确定z,由题意可得 当z=2时，x可取1，y可取1，根据乘法法则，x,y取值共有1×1=12种可能；

当z=3时，x可取1,2，y可取1,2，根据乘法法则，x,y取值共有2×2=22种可能； 当z=4时，x可取1,2,3，y可取1,2,3,根据乘法法则，x,y取值共有3×3=32种可能； ……

当z=n+1时，x可取1,2,…,n,y可取1,2,…,n,根据乘法法则，x,y取值共有n×n=n2种可能。 根据加法法则，当z取2,3,…,n+1时，x,y取值共有1?2?…?n?222?kk?1n2种可能。故|T|??kk?1n2。

(2)由x

①x=y

?3?n?1?③y

3???n?1?＝?n?1??n?1?。

所以满足题意的x,y,z的组合数为?n?1?+?n?1?+?????2?????3?322????3?????? 4

n?n?1??n?1?由于这两种方法是等价的，故可得|T|??k2????2??。证毕。

k?1?2??3?1.24题 A={(a, b)|a, b∈Z, 0≤a≤9,0≤b≤5} (a) 求x-y平面上以A作顶点的长方形的数目. (b) 求x-y平面上以A作顶点的正方形数目.

解(a)：如图(a)，从图中可以看出，对于x-y平面上满足题意的任一顶点A(a,b),除它本身以外，横坐标取值有9种可能，纵坐标取值有5种可能。顶点A(a,b)与和它不在同一水平线或垂直线上的任一点(x,y)均可构成一个长方形。故满足要求的长方形的数目为9×5=45个。

解(b)：如下图(b)，网格左边是b的取值，下面是a的取值。网格里是x-y平面上对应每个顶点A(a,b)所得的正方形的数目。

1.26题 S={1,2,……，1000}，a,b∈S,使ab≡0 mod 5,求数偶{a,b}的数目

解：根据题意，ab可以整除5，2*C（200，1）*1000=400000 1.25题 平面上有15个点P1,P2。。。Ｐ15，其中P1P2P3P4P5共线，此外不存在3点共线的。 (1)求至少过15个点中两点的直线的数目 (2)求由15个点中3点组成的三角形的数目

解：1)由题意知：P1P2P3P4P5共线，此外不存在3点共线的，所以与这五点分别相连的其他的十点的直线数目为：5*10=50。另外十个点两两相连得直线数目为：C102=45

又因为P1P2P3P4P5共线，所以可算作一条至少2点相连的直线 所以至少过15个点中两点的直线的数目=50+45+1=96

2)有三种情况 a：没有P1P2P3P4P5这五个点的三角个数：C103=120

b：有这五个点的其中一个点：5*C102 225 c：有着五个点的两个点：10*C52=100 由15个点中3点组成的三角形的数目=425 故数目为C(15,2)-C(5,2)+1

(b) C(5,0)C(10,3)+C(5,1)C(10,2)+C(5,2)C(10,1)

1.27 题 6位男宾，5位女宾围一圆桌而坐，（1）女宾不相邻有多少种方案？（2）所有女宾在一起有多少种方案？（3）一女宾A和两位男宾相邻又有多少种方案？

解 ：（1）若5位女宾不相邻，先考虑6位男宾围圆桌而做的方案数，然后女宾插入 Q（6，6）*6*5*4*3*2=86400 （2）把5位女宾看成一个整体，然后插入 Q（6，6）P(6,5)=86400 （3）P（6，2）*Q（9，9）=194000

1.28题 k和n都是正整数，kn位来宾围着k张圆桌而坐，试求其方案数。

p解：若每个圆桌的的人数相等，则每个桌子有n个人。因为圆周排列的个数为

r因此本题的结果为

nr

(kn)!(kn)!?k。

n?n?nn1.29 题 从n个对象中取个r做圆排列，求其方案数目。1<=r<=n

解：c(n,r)*Q（r,r） =c(n,r)*(r-1)!

1.31题 试证任意r个相邻数的连乘：(n?1)(n?2)(n?r) 被r！除尽.

证明：由 P（n ,r）=n*(n-1)…（n-r+1） 可知：（n+1）（n+2）…（n+r）= p（n+r,r）=c（n+r,r）* r! 所以 [（n+1）（n+2）…（n+r）]/r!= p（n+r,r）/ r! = c（n+r,r） 故任意个相邻数连乘可被r！除尽。

5

1．30题 （1）?????=n/r?

?n??r??n?1??n??n??????， 1rn；（2）=（n-r+1）/r, 1?r?n；(3) ????????r?1??r?1??r??n??n?1?

???=n/(n-r) ?r?? , 0?r?n；?r??????n??n?1?

解：（1）：??r???n!/(r!(n-r)!) n/r??r?1??=n/r*((n-1)!/((r-1)!(n-r)!))= n!/(r!(n-r)!)=上式 所以两式相等

????（2）：?????n!/(r!(n-r)!) (n-r+1)/r???n??r??n??=（n-r+1）/r*((n!)/((r-1)!(n-r+1)!))= n!/(r!(n-r)!)=上式 所以两式相等 ??r?1??n??n?1?（3）：??r???n!/(r!(n-r)!) n/（n-r）??r??=（n-1）!/(r!(n-r-1)!))= n!/(r!(n-r)!)=上式 所以两式相等

????1.32题 在a, b, c, d, e, f, x, x, x, y, y的排列中，要求y必须夹在两个x之间，问这样的排列数等于多少？

解：满足y必须加在两个x之间应为 x y x y x 然后再把a ，b ，c ，d ，e ，f插入，a插入时有6种选择， b插入时有7种选择，c插入时有8种选择，d插入时有9种选择，e插入时有10种选择，f插入时有11种选择， 由此可得排列数 N=11*10*9*8*7*6=11!/5!

1.33题 已知r，n，k都是正整数，r?nk，将r个无区别的球放在n个有标志的盒子里，每盒至少k个球，试问有多少种方案？

解：首先从r个球中取出nk个球放入n个盒中，因为球是无区别的。因此只有一种排列方案。剩下的球，每个球

(r-nk)放的时候都有n中可能。因此方案数为n.

1.34 题 在r,s,t,u,v,w,x,y,z的排列中求y居于x和z中间的排列数 解 ： 2*（5+4+3+2+1）*6！=2430

1.35题 凸十边形的任意三条对角线不共点。试求这凸十边形的对角线相交于多少个点？

解：根据题意，1个顶点有7条对角线，与它相邻的顶点有7条对角线，这样的点2个； 与它不相邻的顶点有6条对角线（有1条与它重复的），这样的点8个；

因此 （2* C（7，1）* C（7，1）+8* C（6，1）* C（7，1））*（9+1） =4340

1.36题 试证一整数是另外一整数的平方的必要条件是除尽他的数的数目是整数

证明：设N=P1a1 P2a2。。。Pnan，P1，P2，。。。Pn是n个不同的素数，每个能整除尽数n的正整数都可以选取每个素数Pi从0到ai次，即每个素数都有ai+1种选择，所以能整除n的正整数的数目为(a1+1)(a2+1)。。。(ai+1)个。而设M=N2=P12a1 P22a2。。。Pn2an，能被(2a1+1)(2a2+1)。。。2(ai+1)个整除。所以一整数是另外一整数的平方的必要条件是除尽他的数的数目是整数。 1.37题 .给出???n??r??n?1??r?1??n?2??r?2??n?m??r?m??n?r?1?????????????????+++…+=?的组合意义。 ??????????????????m??0??m?1??1??m?2??2??0??m??m?解： Y B（m,n+r+1-m）

P’ P(k,r)

0 k m X r?k?如上图所示，?表示（0，0）点到P点的路径数； ???k????n?m?m?k??n?k??n?r?1?表示（0，0）点到B点的路径数。P点到P’点只有一步；? ???m?k??表示P’点到B点的路径数;??m?k?=??m???????所以0点到B点的路径由0点到P点再从P点到P’点，最后从P’点到达B点。

?0M?r?k??n?k?M???k?*1*??m?k??=?????0?n??r??n?1??r?1??n?2??r?2??n?m??r?m??n?r?1????????????????+++…+?m??0??m?1??1??m?2??2??0???m??=??m?

??????????????????6

1.41 题 分别写出按照字典序，有给定排列计算其对应序号的算法及有给定序号计算其对应排列的算法。

解：利用“字典序法”生成下一排列的算法 ，计算该排列的对应序号，生成已知排列序号算法： 设 int M为每一排列的对应序号初始时：P1_P2_...Pi-1_Pi_Pi+1_...Pn_ (其中P1_

满足关系式Pi-1

使Pi-1与 Pj 互换得(p_) = P1_P2_...Pi-1_Pi_Pi+1_...Pn_

IV. (p_) = P1_P2_...Pi-1_Pi_Pi+1_...Pn_ 中的Pi_Pi+1_...Pn_部分的顺序逆转，得下一排列。 V. 判断(p_)排列是否与给定排列相同 ，相同则输出M， ELSE M=M+1 GOTO Ι （2）给定序列号计算排列算法：

设 Int M为每一排列的对应序号，M=N （N为给定序号） 设 Int K为循环次数

FOR （K=1；K++；K <=N ）

{

满足关系式Pj-1

(p_) = P1_P2_...Pi-1_Pi_Pi+1_...Pn_ 中的Pi_Pi+1_...Pn_部分的顺序逆转，得下一排列

}

输出(p_)排列。

?r??r?1??r?2??n??n?1?1.38题 给出????的组合意义。 ?????????r??r??r??r?????r?1????????????解：设A={a1,a2,….,an?r?1 ,……,an?1 },从A中取r+1个元素组合成C，考虑以下n-r+1种情况： (1) a1∈C，则A需要从A\\{a1}中取r个配合，构成C，共????种可能

?n??r?(2)a1?c，a2?c,则需要从A\\{a1,a2} 中取r-1个，加上a2构成C，共??n?1??r??中可能 …… ??(n-r)a1,a2,...,an?r?1?C，an?r?C，则需从A\\{a1,a2,...,an?r}中取r个组合，再加上an?r构成C，共?r?(n?r?1)a1,a2,...,an?r?C,这时只有???=1种可能。

?r????r?1?

?r??种可能。??故??r??+??r??+…+??r??+??r??=??r?1?? ?r??+?????????????（法二）C(n+1,r+1)是指从n+1个元素a1, a2,…,an+1中任取r+1个进行组合的方案数。

左边：若一定要选an+1,则方案数为C(n,r).若不选an+1,一定要选an, 则方案数为C(n-1,r). 若不选an+1,an,…ar+2, 则方案数为C(r,r). 所有这些可能性相加就得到了总方案数。 1.39 题 证明(m,0)C(m,n)+C(m,1)C(m-1,n-1)+…+C(m,n)C(m-n,0)=2nC(m,n)

证明：由公式C(n,l)C(l,r)=C(n,r)C(n-r,l-r) 其中：l>=r 得： C(m,0)C(m,n)=C(m,n)C(n,0)

同理： C(m,1)C(m-1,n-1)=C(m,n)C(n,1) … C(m,n)C(m-n,0)=C(m,n)C(n,n) 由上知：左边=[C(n,0)+C(n,1)+ … +C(n,n)]C(m,n)

nn?1n?22nn由(x?y)=C(n,0)x +C(n,1)xy+C(n,2)xy+…+C(n,n)y

n 令x=y=1 可得 C(n,0) +C(n,1) +C(n,2) +…+C(n,n)=2 左边=2nC(m,n)=右边 命题得证。 1.40题 从n个人中选r个围成一圆圈，问有多少种不同的方案？

解：圆排列:共有P(n,r)/r种不同的方案。

1.48题 在由n个0及n个1构成的字符串中，在任意前k个字符中，0的个数不少于1的个数的字符串有多少？

解：转化为格路问题(弱领先条件),即从(0,0)到(n,n),只能从对角线上方走,可以碰到对角线,故方案数为C(2n,n)-C(2n,n-1。

7

?n??n?1??n?2??r?1??r??n?1?

1.42题 (a) 按照1.41的要求，写出邻位对换法（排列的生成算法之二）的相应算法.

(b) 写出按照邻位对换法由给定排列生成其下一个排列的算法. 解：1：给定排列求相应序号：

设 Int I为每一排列的对应序号 I=1 （初始化）

假定A[1：n]和E[2：n]；D[2：n]；B[1：n]都是整数数组，其中B[1：n]为给定序列

S1： A[1]?1 i从2到n作 始 A[i]?i，D[i]?i，E[i]??1 终；S2： q?0； 判断A[1：n]是否与B[1：n]相等 若相等则输出I值 否则I?I?1；S3： k从n降到2作 始 D[k]?D[k]?E[k]; p?D[k]; 若 p?k 则作E[k]?-1; 否则作 始 若p?0 则作 始 E[k]?1, q?q?1 终 否则作 始 p?p?q; r?A[p]; A[p]?A[p?1]; A[p?1]?r; 转S2 终

终 终2：给定序号求相应排列：

设 Int I为每一排列的对应序号 I=1 （初始化） M为给定序列号 假定A[1：n]和E[2：n]；D[2：n]；都是整数数组

S1： A[1]?1 i从2到n作 始 A[i]?i，D[i]?i，E[i]??1 终；S2： q?0； 判断 I 是否与 M 相等 若相等则 i从1到n输出A[i]； 否则I?I?1；S3： k从n降到2作 始 D[k]?D[k]?E[k]; p?D[k]; 若 p?k 则作E[k]?-1; 否则作 始 若p?0 则作 始 E[k]?1, q?q?1 终 否则作 始 p?p?q; r?A[p]; A[p]?A[p?1]; A[p?1]?r; 转S2 终

终 终(a) 由给定排列生成其下一个排列的算法

从排列 p?p1p2?pn生成下一个排列 S1： 若在 p?p1p2?pn 中无一处于活动状态则停止。S

2： 求处于活动状态各数中的数值最大者， 设为m， m 和它箭头所指一侧数相互邻换位置。S3： 比 m 大的数一律改变箭指头向的 转；S1。

8

M=N ?N?1或N?1若N是奇数221.43题 对于给定的正整数N，证明，当K??时，C(N,K)是最大值。 ?N若N是偶数??2证明：要证明C（N，K）是最大值，只需证明C（N，K）大于C（N，K-1）即可

根据以往证明大小值的经验，可以用相减或是相除的方法来证明，就此题，相减不合适，采用相除可以消除等式中的一些项

C（N，K）/ C（N，K-1）=（N！/K！（N-K）！）*（（K-1）！（N-K+1）！/N！） =（N-K+1）/K 当n为偶数，k=n/2时 （N-K+1）/K=（（n+2）/n）*（2/n）=（n+2）/n >1 当n为奇数,k=(n-1)/2时 （N-K+1）/K=((n+3)/2) * (2/(n-1))=1+4/(n-1) >1 当n为奇数, k=(n+1)/2时 （N-K+1）/K=((n+1)2) * (2/(n+1)) =1 综上所述,当n取以上三种情况, C（N，K）取最大值

3n?11.46题 证明在由字母表{0,1,2}生成的长度为n的字符串中. (a) 0出现偶数次的字符串有个；

2n?n??n??n?(b) ??2n???2n?1?...???2n?q?3?1，其中q?2?n?.

?2?2?0??2??q?证：(a)归纳法：当n=1时,0出现偶数次的字符串有(31+1)/2=2个(即1,2),成立。

假设当n=k时,0出现偶数次的字符串有(3k+1)/2种。总的字符串有3种。0出现奇数次的字符串有(3k-1)/2种。 当n=k+1时，0出现偶数次的字符串包括两部分：

n=k时,0出现偶数次再增加一位不是0的，共有2(3k+1)/2种，0出现奇数次再增加一位0,共有(3k-1)/2种。 所以共有2(3k+1)/2+(3k-1)/2=(3k+1+1)/2种，证毕。

(b) 等式左边第m项是0出现m次的字符串数，总和就是0出现偶数次的字符串数， 右边由(a)得是0出现偶数次的字符串数，两边显然相等。

()!(2n)!(3n)!1.44题 （a）用组合方法证明n和nn都是整数。 （b）证明nn?1是整数。

22?3(n!)(2n)!2n?n!?(2n?1)!!?n!?(2n?1)!! 解：(a) ①方法一：因为：(2n)!?2?n!?(2n?1)!! 所以n?22nn2n!?(2n?1)!!是整数，因此

(2n)!是整数。 n2方法二：设有2n个不同球放入n个不同的盒子里，每盒两个，这个方案数应该是整数。 对2n个球进行排列得到方案数为(2n)!。 而把2个球放入同一个盒子里不计顺序，

应该把全排列数除掉这些重复计算的次数，n个盒子内部的排列共重复计算了2 次。 得到2n个不同球放入n个不同的盒子里，每盒两个的方案数

(2n)! n2②若有3n个不同的球,放入n个不同盒子,每个盒子放三个，这个方案应该是整数。 对这3n个球进行排列得到方案数为(3n)!。

而把3个球放入同一个盒子里不计顺序，应该把全排列数除掉这些重复计算的次数， n个盒子内部的排列共重复计算了3！次。

得到3n个不同的球放入n个不同的盒子里，每盒三个的方案数

2(3n)!(3n)!? (3!)n3n?2n(b) 有n个不同的球，放入n个相同的盒子里，每盒n个，求方案数，方案数应该是一个整数。

按前面(a)的方法，应该得到(n2)!/(n!)n是整数。另外由于n个盒子相同，放入不同的盒子是没有区别的， 应该把n个盒子的排列数n!除去。 因此得到(n2)!/(n!)n+1是整数。

1.49 题 在1到n的自然数中选取不同且互不相邻的k个数,有多少种选取方案？

解: 设从1-n中选取互不相邻的k个数的方案为g(n,k)。若选n，则方案为g(n-2,k-1),若不选n,则方案数位g(n-1,k). 显然g(n,k)=g(n-2,k-1)+g(n-1,k)，且只有当n≥2k-1时,g(n,k)>0,否则g(n,k)=0,可给定初始值g(2k-1,k)=1,g(2k-2,k)=0.

9

1.45题 (a) 在2n个球中，有n个相同. 求从这2n个球中选取n个的方案数.

(b) 在3n+1个球中，有n个相同. 求从这3n+1个球中选取n个的方案数. 解(a）：有n个相同就有n个不相同

取n个不相同和0个相同的为C(n,n), 取n-1个不相同的球和1个相同的球为C(n,n-1)，等等。

n所以总的方案数为 C?n,0??C?n,1????C?n,n??2 解(b）：方法同上，方案数为C?2n?1,0??C?2n?1,1????C?2n?1,n? 由于C(2n+1,0)=C(2n+1,2n+1),… ,C(2n+1,n)=C(2n+1,n+1) C2n?1,0?C2n?1,1???C2n?1,2n?1?22n?1

??????则C?2n?1,0??C?2n?1,1???C?2n?1,n??122n?1?22n

21.47题 5台教学机器m个学生使用，使用第一台和第二台的人数相等，有多少种分配方案？

解：当使用第1台机器的学生为n个时，使用第2台机器的学生也为n,从m个学生中选出2n个使用这两台机器， 剩余的学生可以任意使用剩下的机器的组合数为C(m,2n)C(2n,n)3(m-2n)。

所以总的方案数为

?C(m,2n)C(2n,n)3n?0q(m?2n)?m?q???

?2?1.50题 (1)在有5个0，4个1组成的字符串中，出现01或10的总次数为4的字符串，有多少个？

(2)在有m个0，n个1组成的字符串中，出现01或10的总次数为k的字符串，有多少个？ 解：(1)、先将5个00000排成一排，1若插在两个0中间，即：“010”则出现2个“01”或“10”； 若插在两端，则出现1个“01”或“10”；要使出现“01”，“10”总次数为4，有两种办法： 1、把两个1插入0的空当内，剩下的1插入1的后面（类似010111000）。

2、把1个1插入0的空当，再取两个1分别插入两端，剩下的1插入1的前面。（类似10100011）。

21由1和2得：3*C4?3*C4?30 (2)、m个0产生m-1个空当。

若k为偶数时：要得到出现“01”与“10”总次数为k，可以先按上题中1的情况讨论，则在m-1个空当中分别插入k个1即可，也就是Ck2m?1。剩下的

21如何插入的问题与书P20页的定理1.2类似(在n个不同元素中取r个允许重复的组

合，其组合数为（C（n+r-1,r)），在这里无区别的球的个数也就是剩下的1的个数（即n-k），盒子的个数也就是插入

2到m-1个空当中的1的个数(即k)，则得出剩下的1的插入方法有C2k2n?1n?。即第一种情况的总的插入方法为：Ck?22m?1k?2?22。 n?1n?k2m?1*Ck2n?1n?。

同理可得，按2的情况讨论后的第二种情况的总的插入方法为：C1和2得总的插入方法为：Ck2m?1*C*Ck2n?1n??Ck?22m?1*Ck?2?22。 n?1n?若k为奇数时：则必有且只有一个1插入字符串的头或尾,剩下的1按照1的方法插入,只有这样才能使k为奇数。 所以插入的总方法为：2*Ck?12m?1*Ck?12。 n?1n?1.51 题 从N={1,2,…,20}中选出3个数，使得没有两个数相邻，问有多少种方案？

解：相当于从N={1,2,…,20}个数中取3个作不相邻的组合，故方案数为C(20-3+1,3)=C(18,3)种 1.52题 从s={1,2,n}中连取k个数，使之没有两个数相邻，求不同方案数。

解：在n个数中选k个数，使之没有两个数相邻，相当于在n-k+1位置中插入k个数，k个数中没有俩个数相邻。

有Cn?k?1?k(n?k?1)!种方案。有定理1.4直接可得。

k!1.53题 把n个无区别的球放进有标志1，2，…，n的n个盒子中，每个盒子可放多于一个球，求有多少种方案？

解：把n个无标志的球放进n个有标志的盒子中，每个盒子允许多于一个球是允许重复的组合所以是

?n?n?1??2n?1???n??=??n?? ????

10

1.54题 .m个1，n个0进行排列，求1不相邻的排列数.设n>m.

解：相当于n个0排列后,使m个1做不相邻的插入，共产生n+1个位置.第一个1插入有n+1种情况， 第二个是n种情况…第m个1插入就有n-m+1种情况。 所以是（n+1）（n）（n-1）…（n-m+1），即此题解为pn+1 m。

1.55题 偶数位的对称数，即从左向右读法与从优向左的读法相同，如3223。试证这样的数可被11整除。

证明： 根据所有偶数位置上的数字及所有奇数位置上的数字分别相加，再求出两个和的差， 如果所得的差能被11整除，那么这个整数必能被11整除。

例如12344321，偶数位上是：2，4，3，1。奇数位上是：1，3，4，2

因为对称数是偶数个，所以偶数为相加与奇数为相加的和是相等的，他们的差是零，而零能能被任何数整除， 所以原题成立。证毕。

1.56 题 n个男人与n个女人沿一圆桌坐下，问两个女人之间坐1个男人的方案数。又m个女人n个男人，且m

解：根据题意，两个女人之间坐1个男人的方案数Q (n,n)* P(n,n) 无两个女人并坐的方案数Q (n,n)* P (n,m)

1.57 题 n个人分别沿着两张圆坐下，一张r人，另一张个n-r人，试问有多少种不同的方案数？ 解： C（n,r）*(r-1)!(n-r-1)!

1.58题 一圆周上n个点标以1,2,?,n。每一点与其它n-1个点连以直线，试问这些直线交于圆内有多少点？

解：这些直线交于圆内有C（n,4）个点

每4个点形成矩形，其对角线有一个交点，故圆内交点有：

C(n,4)?n(n?1)(n?2)(n?3)1?n(n?1)(n?2)(n?3)4?3?2?124

因为四个点连在一起构成一个四边形，这个四边形的对角线相交于一个点，

求这些直线交于圆内多少点就是求这些点能构成几个四边形，即转化为从n个点取出四个进行组合

2.1题 求序列{ 0，1，8，27，

n332}的母函数。

33解：由序列可得到G(x)?x?2x?3x?因为

?n3xn?

1?1?x?x2?x3??xn? 1?x1()'?1?2x?3x2?4x3??nxn?1? 1?x1设 p(x)?x()'?x?2x2?3x3??(n?1)xn?1?nxn1?x?'?1x? [p(x)]2

1x2?22x32?222n?2?n?(x1)?nxn2?

设 q(x)?x[p(x)]'?x?2x?3x?3?(n?1)2xn?1?n2xn1?'?1x2? [q(x)]33x32?3n?2?n?(x1)?nxn3?

x[q(x)]'?x?23x2?33x3由以上推理可知x[q(x)]'=

?(n?1)3xn?1?n3xn

,[7*9n?4*(?6)n],所以可通过求得x[q(x)]'得到序列的母函数：G(x)?4x?x?x

321H(x)??F(x)dx?[3x2?4x3?6

?(n?3)xn?2]

11

2.2题 已知序列???,??,解： G(x)???3??4???3??3??n?3??,,?，求母函数 ???3??3*2*14*3*2(n?3)*(n?2)*(n?1)n???x

3*2*13*2*13*2*11n =[3.2.1?4.3.2x??(n?3)(n?2)(n?1)x]

612n?1 F(x)??G(x)dx?[3.2x?4.3x??(n?3)(n?2)x]

612 H(x)??F(x)d? x[23x?34x??(n?n?3)x]61I(x)??H(x)dx?[x3?X4??xn?3]

61因为?1?x?x2?1?x2.3题 已知母函数G(x)??xn?3?1x3112]'''就是所求序列母函数 所以I(x)?(?1?x?x) 所以G(x)?[61?x61?x3?78x，求序列{an}。

1?3x?54x23?78xAB74解：G(x)?= ???1?3x?54x21?9x1?6x1?9x1?6x172由?1?x?x2??xn?3?得 ?7(1?x9?(x9?)?1?x1?9x4?4(1?(?6)x?(?6x)2??(?6x)n) 1?6x所以由两式相加得：对应序列{an}={11，39，

x(n9)

),[7*9n?4*(?6)n],}

2.4题 已知母函数G(x)?3?9x，求序列{an}。 21?x?56x3?9xAB12解：G(x)?= ???21?x?56x1?8x1?7x1?8x1?7x则an=8?2*(?1)*7

nn2.5题 设Gn?F2n，其中Fn是Fibonacci数。证明：Gn?3Gn?1?Gn?2?0，n=2.3.4…..求{G0,G1,G2,解：(1).已知Gn?F2n 则Gn?3Gn?1?Gn?2=F2n?3F2n?2?F2n?4

}的母函数。

F2n?F2n?1?F2n?2 F2n?1?F2n??2Fn2? F2n?2?F2n??3Fn2?

则F2n?3F2n?2?F2n?4 则Gn?3Gn?1?Gn?2?0 (2)．G(x)?G0?G1x???(Gn?2nn?n?1?Gn?2)x =G0?G1x?x?Gn?1xnn?22?n?1?x2?Gn?2?n?2xn?2

=G0?G1x?x?(Gxn?0?G0)?x?Gn?2?2n?2G?Gx?xG(x)?xG?xG(x) x =010n?2 =1?xG(x)?xG(x)?x G(x)?

12

21?x 21?x?x2.6题 求序列{1，0，2，0，3，0，

解：序列an=

}的母函数。

2n?2n?(n?1)xn?0?2n11?1?2n1x112n=?nx??x=?(2n?1)x??x=(= )'?222222(1?x)21?x21?xn?0n?0n?0n?0?2.7题 设G?1?2x?3x?4x???(n?1)x2462n??=1/(1-x^2)^2 求(1?x2)G,(1?x2)2G

2n解：设T?G?1?2x?3x?4x?L?(n?1)x?246?L?1x ?1?1?x1?x1?x?1?x?x G?????22(1?x)(1?x)?1?x?1(1?x2)12222242n(1?x)G?(1?x)?1 所以 1）(1?x)G? 2）??1?x?x???x??22222(1?x)(1?x)1?x2?2.8题 求下列序列的母函数：(1)1,0,1,0,1,0，… (2)0,-1,0,-1,0,-1,… (3)1,-1,1,-1,1,-1,…

解：(1) G?1?x?x???x(2) G??x?x?x???x234242n???1 21?x1x ?1?x2x2?1352n?1?? ??x(1?x2?x4?L?x2n?L)??xn111?x?x2?x?(3)1?x??x?x?x???(?1)x???(1?x?x?L)?x(1?x?x?L)? 1?x21?x1?x2n2424?n?2?n23n2.9题 设G?1?3x?6x?10x?????2??x??证明：(1)(1?x)G?1?2x?3x?4x???(n?1)x??

??23(2)(1?x)G?1?x?x???x?? (3)因为(1?x)G?1，所以有G?22n31

(1?x)3证明（1）G?1?3x?6x2??n?2?n???x?2???11?(1?x)G??1?2x?3x2?32(1?x)(1?x)?(n?1)xn?

（2）展开(1-x2)G= (1+x)/(1-2x+x2) 当x(3)(1?x)G?(1?3x?3x?x)(1?3x?6x?32321时 有

)

1?x1 ?1?x1?x=1?3x?6x2?10x3?15x4?3x2?9x3?18x4?30x5?3x?9x2?18x3?30x4??x3?3x4?6x5?10x6=1

?G?1 3(1?x)23??n?3?n?n?2?n??2.10题 H?1?4x?10x?20x???? 证明(1) x??(1?x)H?G???3??2??x (2) 求H的表达式。

n?0?????n?3?(k?3)(k?2)(k?1)k3?6k2?11k?6证明(1) 设H的第K+1项为hk，则hk=?=， ?3??=63*2*1?? 设G的前K+1项的和为Gk，则Gk=

?2??3??k?2?g?????=++…+?k?2?? ?2??2?k?0??????k 13

而??2??=1+2 + ?2??+??2??+…+??????? =1+

?2??3??k?2?3*24*3(k?2)*(k?1)1+…+ =1+[3*2+4*3+…+(k+2)(k+1)] 2221(1+ 22+ 32+…+k2+3+6+…+3k+2+2+…+2) ①{注释：均为k项，分别为平方数列，等差数列，常数列} 2(2k2?k)(k?1)3k(k?1)113k(1?k)=1+[k(k+1)(2k+1)+ +2k] =1+++k

122624(2k2?k)(k?1)?9k(k?1)?12k?12k3?6k2?11k?6G = = = hk ?H=

6121?x(2) 由H=1+4x+10x2+20 x3+…+(3n?3) x+…=1+

n4*3*25*4*32(n?3)(n?2)(n?1)nx+…+x+x+…

3*2*13*2*13*2*1x3x3对其3次积分得???H=，对此积分式3次求导得H=((( )))’’’。求解完毕。

6(1?x)6(1?x)2.11题 an=(n+1),G=

?2?axnn?0?n=1+4x+…(n+1)x+…,证明(1-3x+3x-x)G是一个多项式,并求母函数G。

?2n22解: G=

?ax=?(n?1)nnn?0n?0?2x=?(n?2n?1)x?G =x?nxn2n2n?0n?1??n?1+2x?nxn?0?n?1+

?xn?0n ①

? G =xG+

2xx?1x?11+ G(1－x)= G= 即为所求 ??(1?x)21?x(1?x)2(1?x)322?(1－3x＋3x2—x2)=(1－x)3 ?(1－3x＋3x—x)G =(1－x)G =(1－x)3

??3x?1=x+1 求解完毕。

(1?x)3①说明：可以由

?nx2n?12n?1=

?(n?1)n?02xn

?x?12n(n?1)x,求序列{ an}的母函数。 2.12题 已知an=?k, =?3(1?x)n?0k?1n?1解：设序列{ an}的母函数为G(x), 则G(x)= a0+a1x+a2x+…+ anx+ an?1x

nn?1

+…

? an=?k2=1+22+32+…+n2+(n+1)2

k?1n?1?G(x)=1+(1+22)x+(1+22+32)x2+…+(1+22+32+…+n2+(n+1)2) xn+…

=1+x+ x+…x+… +2x(1+x+ x+…x+…) +3x(1+x+ x+…x+…)+… +(n+1)x(1+x+ x+…x+…)+…. = (1+x+ x+…x+…)(1+2x+3x+…+nx

2n2222n?1

2n2n2n22n222n1+ (n+1)x+…) =

1?x2n?(n?1)n?0?2xn

?x?1x?1x?112n??(n?1)x= G= G= 即为序列{ an}的母函数。求解完毕。 ??(1?x)3n?0(1?x)41?x(1?x)3 14

?1?4x?x22.13题 已知an??k, ??(n?1)3xn,求序列{an}的母函数。4(1?x)k?1n?0n?13解：B(x)=13+23x+33x2+……

1: a0=13 b0=13 x: a1=13+23 b1=23 2x: a2=13+23+33 b2=33 …… a0= b0 a1= b0+ b1

a2= b0+ b1+ b2 ……

2222A(x)= b0(1+x+ x+……)+ b1x(1+x+ x+……)+ b2x(1+x+ x+……) +……

B(x)1?4x?x2=(1+x+ x+……)( b0+ b1x+ b2x+……) = = 51?x(1?x)222.14题 已知{Pn}的母函数为x ,

1?2x?x2{Pn}的递推关系 (a)求P0和P1; (b) 求序列22解: 特征多项式 K(x)= x-2x-1 x-2x-1=0 解得：r1=1+2 r2=1-2

P(x)=

A1?(1?2)x +

B1?(1?2)x

A+B=0

-A(1-2)-B(1+2)=1 得：A=

22, B=-

442211P(x)= ( -)=

41?(1?2)x1?(1?2)x4Pn=

?[(1?k?0?2)k?(1?2)k]xk

2nn[(1+2)-(1-2)] P0=0, P1=1 42.15 题 已知{an}的母函数为

21,求序列{an}的递推关系a0,a1。 21?x?x解：特征多项式 K(x)= x-x+1

?i331??3i1??x-x+1=0解得：r1=+i=cos+isin=e, r2=-i= cos-isin= e3

22223333??2A(x)=

AB +

1?r1x1?r2xA1+A2=1, A1r2+ A2r1=0 解得：A1=1，A2=

13

an=A1cos

1nnnn?+A2sin?= cos?+sin? a0=1, a1=1 3333315

?m??m?1??m?2??m?n??，??，…，??的母函数为（1-x）?m?1 2.16 题 证明序列??，??m??m??m??m?证明：当m=0时，命题成立。

?m?1?k?k?X=（1-x）?m， 假设对于m-1，命题成立，即??k?0?m?1? 则Gm(X)=

??m?k?k??m?1?k?k??m?1?k?k??X=???X+???X=X ?Gm(X)+ （1-x）?m ?k?0?m?k?0?m?k?0?m?1?m??(1-X) ? G

Gm(X)=

(X)= （1-x）?m，

11

=（1-x）?m?1 m1?X?1?X?2x?...?n?(2.17题 已知G?1?2x?3??x1?)n...证明 aG(?)?x(1??2?4n?0?n?3n)x( 3)(b)G??anx,其中an??(k?1)(n?1?k)2nn?0k?0(c)an?(n?3),n?{0,1,2,...} 3?n?3?n(a) G?(1?x)????x3?n?0? 证明： 由已知 G?1?2x?3x2?2?4??(n?1)xn???(1?x)?2n 所以有 G2?(1?x)?4??n 又根据牛顿二项式展开定理 （1?x）??????xk?kk?0???k?4?1?k?k?3?k 令n?4 则有（1?x）????x???3?x3???k?0k?0??4??

?n?3? G?(1?x)????xn 得证3?n?0?2?4?（b） G ? ?anx , 其中 an??(k?1)(n?1?k)

2nn?0k?0?n 证明： 已知 G?1?2x?3x2???(n?1)xn???(1?x)?2A(x) 由性质 ： 若 bk??ai 则 B(x)?1?xi?0k

1?1?x?x2?1?xii1A(x)G? ? 即 gi??an??12(1?x)1?xn?0n?0A?iini1G(x)C? ? 即 ci??gn???ah???n?1?(1?x)31?xn?0n?0h?0n?0iin1C(x)D?G? ? 即 di??cn???(h?1)4(1?x)1?xn?0n?0h?02

16

可将di表示成如下形式： c0： a0 (a0?1) c1： a0?a1 (a1?2) c2： a0?a1?a2 (a2?3) cn： a0?a1?a2??an (an?n?1) dn??ci?(i?1)(n?1?i) i?0n

其中（i?1）表示每列上的数值，（n?1?i）表示（k?1）这个数的个数。所以 an??(k?1)(n?1?k)成立k?0n

?n?3?(c) 证 an ??? n??0,1,2,?3?n??

?n?3? 证明： 题目即证 ??k?1??n?1?k???? n??0,1,2,?3?k?0n?n?3? (1) 当 n?0 时 ??k?1??n?1?k??1 ?? ?1 等式成立 ?3?k?0 (2) 假设，当 n?m -1 时等式成立 ，即 ??k?1??n?1?k? ? ??k?1??m?k??1?m?2?(m-1) ?3?(m-2)k?0k?0nm?1m?1

(m?2)(m?1)m?m?1?3??m?2? ?? ?? ? ?3? 33！????(3) 当 n?m 时有??k?1??n?1?k? ? ??k?1??m?1?k? k?0k?0nm ?1?（m?1）?2?m?3?(m?1)? ?1?m?1?1?2?(m?1)?2?1? ? ??k?1??m?k??1?2?k?0m?1?(m?1)?1?m?1?(m?1)?1

?(m?1) ? ??k?1??m?k??k?0m?1(m?2)(m?1)2?m?3?(m?3)(m?2)(m?1)?m?2?3(m?2)(m?1)?m?2?(m?2)(m?1)? ????????3??33！3！2?????3? ?m?2?当 n?m -1 时等式成立即 ??k?1??m?k? ? ???3?k?0m?1(m?2)(m?1)?m?2?(m?2)(m?1)所以 ??k?1??m?k??????22?3?k?0?m?3?即 ??k?1??m?1?k? ? ?? 等式成立?3?k?0?n?3?综合（），（12），（3） an ??? 得证?3?

17

mm?1

2.18题 用母函数法求下列递推函数关系的解.

(a)an?6an?1?8an?2?0(c)an?9an?2?0(e)an?12an?1?36an?2?0(b)an?14an?1?49an?2?0(d)an?6an?1?7an?2?0 (f)an?25an?2?0解(a)：x2:a2?6a1?8a0?0x3:a3?6a2?8a1?0x4:a4?6a3?8a2?0 ?)......0?(A(x)?a0?a1x)?6x(A(x)?a0)?8x2A(x)(1?6x?8x2)A(x)?a0?a1x?6a0x?a0?(a1?6a0)xan?(a1?6a0)xABA(1?4x)?B(1?2x)(A?B)?(4A?2B)????1?6x?8x21?2x1?4x(1?2x)(1?4x)(1?2x)(1?4x)a01A?B?a06a?a22a0?(6a0?a1)a1?4a01?所以有?解之得:A=01???(4a0?a1)11?(4A?2B)?a?6a2?4?2210?42a0146a0?a1(6a0?a1)?4a02a0?a11B????(a1?2a0)112?4?22421?A?(4a0?a1)??2因此??B?1(a?2a)10??2??111111n故此A(x)?(4a0?a1)?(a1?2a0)??(4a0?a1)??(2x)?(a1?2a0)??(4x)n21?2x21?4x22n?0n?0?11??[(4a0?a1)?2n?(a1?2a0)?4n(n?2)

22n?0所以A(x)?解(b)：x2:a2?14a1?49a0?0x3:a3?14a2?49a1?0 x4:a4?14a3?49a2?0?):......(A(x)?a0?a1x)?14x(A(x)?a0)?49x2A(x)?0

(1?(4x?49x2)A(x)?a0?a1x?14a0x?a0?(a1?14a0)xa?(a1?14a0)xABA(1?7x)?B(A?B)?7Ax所以A(x)?0????1?14x?49x2(1?7x)(1?7x)2(1?7x)2(1?7x) ?A?B?a0所以有??7A?a1?14a0111故此A?(a1?14a0)B?a0?A?a0?(a1?14a0)??(a1?7a0)777故此A(x)?1111(a1?14a0)?(a1?7a0)71?7x7(1?7x)2??n?111nn?(a1?14a0)?(?7)x?(a1?7a0)?()(?7)(参见题2.16) 177n?0n?0?11??[(a1?14a0)?(a1?7a0)(n?1)](?1)n7nxn7n?071所以an?[a0?(a0?a1)n](?1)n7n718

解(c)：x2:a2?9a0?0x3:a3?9a1?0 x4:a4?9a2?0?):......(A(x)?a0?a1x)?9x2A(x)?0 所以有(1?9x)A(x)?0a?axABA(1?3x)?B(1?3x)(A?B)?(3A?3B)x于是A(x)?012????1?9x1?3x1?3x(1?3x)(1?3x)(1?3x)(1?3x)①?A?B?a0故此有?②?3A?3B?a1②?3x①有6A?3a0?a111于是有A?a0?a1③261111将③代入①有B?a0?A?a0?a0?a1?a0?a1④262611?A?a?a10? ?26即??B?1a?1a01?26???1111111111nn故此A(x)?(a0?a1)?(a0?a1)?(a0?a1)?3x?(a0?a1)?(?1)n3nxn261?3x261?3x26n?026n?0?1111??[(a0?a1)?(a0?a1)(?1)n]?3nxn2626n?01111所以an?[(a0?a1)?(?1)n(a0?a1)]?3n(n?2)2626解(d)：x2:a2?6a1?7a0?0x3:a3?6a2?7a1?0 x4:a4?6a3?7a2?0?):......(A(x)?a0?a1x)?6x(A(x)?a0)?7x2A(x)?0所以(1?6x?7x2)A(x)?a0?a1x?6a0xa?(a1?6a0)xABA(1?x)?B(1?7x)(A?B)?(A?7B)x因而A(x)?0????1?6x?7x2(1?7x)1?x(1?7x)(1?x)(1?7x)(1?x)①?A?B?a0

故此有?②?A?7B?a1?6a0②?7?①得8A?a1?a01于是有A?(a0?a1)③8将③代入①有B?a0?A?a0?1(a0?a1)?1(7a0?a1)④88?A?1(a0?a1)?8从而?B?1(7a0?a1)?8???111nn111故此A(x)?(a0?a1)?(7a0?a1)?(a0?a1)?7x?(7a0?a1)?(?1)nxn

881?7x81?x8n?0n?0???[1(a0?a1)?7n?1(7a0?a1)(?1)n]xn88n?0所以an?1(a0?a1)?7n?1(7a0?a1)(?1)n(n?2)88

19

解(e)：x2:a2?12a1?36a0?0x3:a3?12a2?36a1?0x:a4?12a3?36a2?0?):......24

(A(x)?a0?a1x)?12x(A(x)?a0)?36x2A(x)?0于是(1?12x?36x)A(x)?a0?a1?12a0x

从而A(x)?a0?(a1?12a0)xABA(1?6x)?B(A?B)?6Ax????222(1?12x?36x)(1?6x)(1?6x)(1?6x)(1?6x)2①②③④

?A?B?a0故有???6A?a1?12a01由②有A?2a0?a16

11代入③就有B?a0?A?a0?(2a0?a1)??a0?a1661?A?2a?a10??6即??B??a?1a01?6??n?111111?nn1从而A(x)?(2a0?a1)??(?a0?a1)??(2a0?)?6x?(?a0?a1)?()6nxn261?6x6(1?6x)6n?06n?01?111nn??[(2a0?a1)?(?a0?a1)(n?1)]?6x??[a0?(?a0?a1)n]6nxn666n?0n?01所以an?[a0?(?a0?a1)n]?6n(n?2)6?

解(f)：x2:a2?25a0?0x3:a3?25a1?0x:a4?25a2?0?):......24

(A(x)?a0?a1x)?25x2A(x)?0故此（1?25x)A(x)?a0?a1x从而A(x)?

a0?a1xABA(1?5x)?B(1?5x)(A?B)?(5A?5B)x????221?25x1?5x1?5x1?25x1?25x2?1a?1aA??20101?A?B?a0?故此?于是有?5A?5B?a?1?B?1a?1a 012?10???1111111111nn从而A(x)?(a0?a1)?(a0?a1)?(a0?a1)?5x?(a0?a1)?(?1)n5nxn2101?5x2101?5x210n?0210n?0?1111??[(a0?a1)5n?(a0?a1)(?1)n5nxn]xn(n?2)210210n?0

20

2.19 题 用特征值法求习题2.18的解。

???2特征值为?1??2?41???a0?A?B?A?2(4a0?a1)从而有?解之得??B?1(a1?2a0)?a1?2A?4B??2n11于是an?(4a0?a1)?2?(a1?2a0)?4n(n?2)22(a)特征方程为?2?6??8?0通解为：an?A?2n?B?4n

(b)特征方程为:?2?14??49?0特征根为:?1??2??7?A?a0?a0?A?从而有?解之得?1a??7(A?B)B??(a?a1)?10?7?1故an?[a0?(a0?a1)n](?1)n7n(n?2)7通解为an?(A?Bn)(?1)n7n

特征根为:?1?3,?2??3通解为an?A?3n?B?(?1)n3n11?A?a?a10??a0?A?B?26 从而有?解之得??a1?3A?3B?B?1a?1a01?26?111111故an?[(a0?a1)?(?1)n(a0?a1)]?3n?[a0(1?(?1)n)?a1(1?(?1)n]?3n(n?2)262626(d)特征方程为:?2?6??7?0特征根为:?1??1,?2?7通解为an?A?(?1)n?B?7n1?A?(7a0?a1)??a0?A?B11?8从而有?解之得?故an?(7a0?a1)(?1)n?(a0?a1)?7n(n?2)88?a1??A?7B?B?1(a?a)01?8?(e)特征方程为:?2?12??36?0特征根为:?1?6,?2?6通解为an?(A?Bn)?6n?A?a0

?a0?A1?n从而有?解之得?故an?[a0?(a1?a0)n]?6(n?2)16B?a1?a0?a1?6(A?B)?6?2(f)特征方程为:??25?0特征根为:?1?5,?2??5通解为an?A?5n?B?(?1)n5n?A?1a0?1a1?a0?A?B?210从而有?解之得?故an?[(1a0?1a1)?(?1)n(1a0?1a1)?5n]210210B?1a0?1a1?a1?5A?5B?210?2.20 题 已知an?2an?1?a?n2?0,(c)特征方程为:?2?9?0(a求一般解；)(求满足b)0a?，0?1 1a的特解；(c)求满足的a0=a1=2的特解；

解(a)：特征方程为:?2?2??1?0特征根为:?1?1?2,?2?1?2n通解为an?A(1?2)?B(1?2)n1?A????A?B?0?22解(b)：由an?0,a1?1得?解之有???(1?2)A?(1?2)B?1?B??1 ?22?1因此，特解an?[(1?2)n?(1?2)n]22??A?1?A?B?2解(c)：由a0?a1?2可得?解之有?A?(1?2)B?2??B?1?(1?2)nn因此，特解an?(1?2)?(1?2)

21

2.21 题

2.21 已知an?5n?d?(?4)n,c和d为常数,n?N,求a0?5,a1??2时的c和d及序列的递推关系

?c?d?0?c?2解:由an?5,a1??2得?解之有??5c?4d?1?d?3因此，特解an?2?5n?3?(?4)n由于特征根为:?1?5,?2??4 故特征方程为:(??5)(??4)?0即?2???20?0因此对应的递推关系为:an?an?1?2an?2?0或者 an?an?1?20an?22.22 题 已知

a3(?1)，c和d为常数，n?N,求{a=cnn+d

nn}满足的递推关系。

2解：由题意可知，

a的特征方程为，（x-3）（x+1）=0,即nx-2x-3=0,所以递推关系为

a-2ann?1-3

an?2=0

nn)?(3)k和,1k是常数n?,N求,an的递推关系{}2.23 题 an?(k1?k2 2解：特征根为:?1??2??3,故特征方程为:(??3)2?0,即:?2?6??9?0,

于是递推关系为:an?6an?1?9an?2?0?求解这个递推关系2,2.24 题 设an?2an?1?a? n2?5,a0?1,a1解： 首先解得a2=8

an-2an?1+an?2=5 （1） an?1-2an?2+an?3=5 （2）

（1）-（2） an-3an?1+3an?2-an?3=0

32建立特征方程为： x-3x?3x-1?0

解这个方程得：x1? 1 x2?-1 x3?1/3

nnn设 an=A(1)+B(-1)+C(1/3)

a0=A+B+C a1=A-B+(1/3)C a2=A+B+(1/9)C 解得A= 2 B= 7 C= -9 an=2(1)n+7(-1)n-9(1/3)n

2.25题 设{an}序列的母函数为

解：

4?3x, 但b0=a,b1=a1-a0, …,bn=an-an-1, …, 求序列{bn}的母函数 3(1?x)(1?x?x)设B的母函数是B(n)?b0?b1x?b2x2?....bnxnb0?a0x:b1?a1?a0x2:b2?a2?a1x3:b3?a3?a2???

?)B(x)?b0?b1x?b2x2?....bnxn?a0?(a1?a0)x?(a2?a1)x2?.....即 B(x)?b0?b1x?b2x2?....bnxn?(1?x)a0?(1?x)a1x?...... ?(1-x)(a0?a1x?a2x2?....)?（1?x）A(x) ?

22

4?3x1?x?x32.26题 设G=a0+a1x+a2x2+…,且a0=1,an=a0an-1+a1an-2+…+an-1a0,试证1+xG2=G.

证明：因为G=a0+a1x+a2x2+…. x2:a2=a0a1+ a1a0

x3:a3=a0a2+ a1a1+ a2a0

4x:a4=a0a3+ a1a2+ a2a1+ a3a0 +) …

2G-1-X= a0+a1x-1-X+(a0a1+ a1a0) x+ (a0a2+ a1a1+ a2a0) x3+… 因为a0=1，得a1=1

2所以G-1-x= (a0a1+ a1a0) x+ (a0a2+ a1a1+ a2a0) x3+…

22 =a0a1x+a1a0x+ a0a2x3+ a1a1x3+ a2a0x3+…

222 = a0(a1x+ a2x3+…)+ a1x(a0x+a1x…)+ a2x( a0x +…)+…

222 = a0a1x+a0a2x3+…+ a1x(a0x+a1x+…)+ a2xa0x +…

222=a0a0x+a0a1x+a0a2x3+…+a1x(a0x+a1x…)+ a2xa0x +…-x

2=-x+(a0x+a1x+…)(a0+a1x +…)=-X+X(a0+a1x +…) (a0+a1x +…)

22所以：G-1-X=-X+(a0+a1x +…)x G-1=Gx 2.27 题 求下列递推关系的一般解：

(a)an?4an?1?5n(b)an?6an?1?5?3n(d)an?6an?1?4?(?6)n(f)an?4an?1?7?4n?6?5n(h)an?4an?1?(n?n2)?4n(i)an?an?1?4n3?6n2?4n?1(k)an?2an?1?8an?2?3?(?4)n?14?3n(l)an?6an?1?9an?2?3n(n)an?2an?1?2n?3n?4n解(a)：特征方程:??4?0，特征根:??4，齐次通解:an?A?4n 非齐次特解:an?B?4n，代入齐次方程可得:B?5nnnn?1非齐次的通解:an?A?4?5?5?A?4?5(c)an?4an?1?4n(g)an?6an?1?(?6)n(2n?3n2)(j)an?7an?1?12an?2?5?2n?4?3n (m)an?7an?1?9an?2?3n解(b)：特征方程:??6?0，特征根:???6，齐次通解:an?A?(?6)n，5非齐次特解:an?B?3n代入齐次方程可得:B?，

35非齐次的通解:an?A?(?6)n??3n?A?(?6)n?5?3n?13解(c)：特征方程:??4?0,特征根:??4,齐次通解:an?A?4n非齐次特解:an?(B?Cn)?4n(因为f(n)?4n,4是一重特征根) 代入齐次方程可得:C?1,非齐次的通解:an?A?4n?(B?n)4n?(A?B?n)4n设新的A为A?B,故有an?(A?n)?4n解(d)：特征方程:??6?0，特征根:???6，齐次通解:an?A?(?6)n非齐次特解:an?(B?Cn)?(?6)n(因为f(n)?(?6)n,?6是一重特征根) 代入齐次方程可得:C?4，非齐次的通解:an?A?(?6)n?(B?4n)(?6)n?(A?B?4n)(?6)n设新的A为A?B,故有an?(A?4n)?(?6)n解(e)：特征方程:??4?0，特征根:??4，齐次通解:an?A?4n非齐次特解:an?(B?Cn)?4n?D?5n(因为f(n)?2?5n?3?4n,4是一重特征根)?C??3代入非齐次方程可得:?即特解为an?(B?3n)?4n?10?5n

?D?10非齐次的通解:an?A?4n?(B?3n)4n?10?5n?(A?B?3n)4n?2?5n?1设新的A为A?B,故有an?(A?3n)?4n?2?5n?1解(f)：特征方程:??4?0，特征根:??4，齐次次通解:an?A?4n，非齐次特解:an?(B?Cn)?4n?D?5n(因为f(n)?7?4n?6?5n,4是一重特征根)?C?7代入非齐次方程可得:?即特解为an?(B?7n)?4n?30?5n

?D??30非齐次的通解:an?A?4n?(B?7n)4n?30?5n?(A?B?7n)4n?30?5n设新的A为A?B,故有an?(A?7n)?4n?30?5n

23

解(g)：特征方程:??6?0，特征根:???6，齐次次通解:an?A?(?6)n非齐次特解:an?(B?Cn?Dn2?En3)?(?6)n，代入非齐次方程可得:(B?Cn?Dn2?En3)?(?6)n?6[B?C(n?1)?D(n?1)2?E(n?1)3](?6)n?1?(?6)n[C?D(2n?1)?E(3n2?3n?1)]?(?6)n[3En2?(2D?3E)n?(C?D?E)]?(?6)n(2n?3n2)?C?32?3E?3?

??故有?2D?3E?2，解之得?D?5，即非齐次特解为an?(B?3n?5n2?n3)(?6)n222?C?D?E?0???E?1?n非齐次的通解:an?A?(?6)?(B?3n?5n2?n3)(?6)n?(A?B?3n?5n2?n3)(?6)n222223n35设新的A为A?B,故有an?(A?n?n?n)?(?6)22解(h)：特征方程:??4?0，特征根:??4，齐次通解:an?A?4n，非齐次特解:an?(B?Cn?Dn2?En3)?4n，代入非齐次方程可得:(B?Cn?Dn2?En3)?4n?6[B?C(n?1)?D(n?1)2?E(n?1)3]4n?1?4n[C?D(2n?1)?E(3n2?3n?1)]?4n[3En2?(2D?3E)n?(C?D?E)]?4n(n?n2)?C?1?3E??13???故有?2D?3E?1解之得?D?0

?C?D?E?0?E??1??3?即非齐次特解为an?(B?1n?1n3)4n33n非齐次的通解:an?A?4?(B?1n?1n3)4n?(A?B?1n?1n3)4n33333n11设新的A为A?B,故有an?(A?n?n)433解(i)：特征方程:??1?0，特征根:??1，齐次通解:an?A?1n非齐次特解:an?(B?Cn?Dn2?En3?Fn4)?1n?B?Cn?Dn2?En3?Fn4 代入非齐次方程可得:(B?Cn?Dn2?En3?Fn4)?[B?C(n?1)?D(n?1)2?E(n?1)3?F(n?1)4]?[C?D(2n?1)?E(3n2?3n?1)?F(4n3?6n2?4n?1]?4Fn3?(3E?6F)n2?(2D?3E?4F)n?(C?D?E?F)?4n3?6n2?4n?1?4F?4?C?0?3E?6F??6?D?0 ??故有?解之得?2D?3E?4F?4??E?0???C?D?E?F??1?F?14即非齐次特解为an?B?n非齐次的通解:an?A?B?n4设新的A为A?B,故有an?A?n4解(j)：特征方程:?2?7??12?0，特征根:?1?3,?2?4，齐次通解:an?A?3n?B?4n非齐次特解:an?C?2n?(D?En)?3n(因为f(n)?5?2n?4?3n,且3是一重特征根)代入非齐次方程可得:(C?2n?(D?En)?3n]?7[C?2n?1?(D?E(n?1)?3n?1]?12[C?2n?2?(D?E(n?2))?3n?2] ?C?2n?2(4?14?12)?3n?2[(9D?21D?12D)?(9En?21E(n?1)?12E(n?2))]?C?2n?1?3n?1?5?2n?4?3n?C?10于是,可得?即非齐次特解为an?10?2n?(D?12n)?3n?E?12非齐次的通解:an?A?3n?B?4n?10?2n?(D?12n)?3n?10?2n?(A?D?12n)?3n?B?4n设新的A为A?D,故有an?10?2n?(A?12n)?3n?B?4n

24

解(k)：特征方程:?2?2??8?0特征根:?1??4,?2?2齐次通解:an?A?(?4)n?B?2n非齐次特解:an?(C?Dn)?(?4)n?E?3n(因为f(n)?3?(?4)n?14?3n,且-4是一重特征根)代入非齐次方程可得:[(C?Dn)(?4)n?E?3n]?2[(C?D(n?1)(?4)n?1?E?3n?1]?8[(C?D(n?2)(?4)n?2?E?3n?2] CCDDD?[(C??)?(Dn?(n?1)?(n?2))](?4)n?E3n?2(9?6?8)?(?D)(?4)n?7E?3n?22222237?D(?4)n?E?3n?3?(?4)n?14?3n29?3D?10??D?2?2于是,可得?解之得?即非齐次特解为an?(C?2n)(?4)n?18?3n?E??18?7E??14??9非齐次的通解:an?A?(?4)n?B?2n?(C?2n)?(?4)n?18?3n?(A?C?2n)(?4)n?B?2n?18?3n设新的A为A?C,故有an?(A?2n)(?4)n?B?2n?18?3n解(l)：特征方程:?2?6??9?0特征根:?1??2?3齐次通解:an?(A?Bn)?3n非齐次特解:an?(C?Dn?En2)?3n(因为f(n)?3n,且3是二重特征根)代入非齐次方程可得:(C?Dn?En2)?3n?6(C?D(n?1)?E(n?1)2]?3n?1?9(C?D(n?2)?E(n?2)2]?3n?2?[(C?2C?C)?(D?2D?D)n?(E?2E?E)?(2D?2D)?2E(2n?1)?E(?4n?4)]3n ?E?(4n?2?4n?4)?3nn?E?2?3?3n故有E?1即非齐次特解为an?(C?Dn?1n2)?3n22n非齐次的通解:an?(A?Bn)?3?(C?Dn?1n2)?3n?((A?C)?(B?D)n?1n2)?3n222n1设新的A为A?C,新的B为B?D,故有an?(A?Bn?n)?322解（m）：特征方程：??7??9?0 特征根：?1?7?137?13,?2? 22齐次通解：an?A?(7?137?13)?B?() 非齐次通解：an?C?3n 22nn?1代入非齐次方程：C?3?7C?3?9C?3n?2?3n7C?3n(1??1)?3n31C?(?)?13C??3

n故此非齐次方程的特解为：an?(?3)?3

于是非齐次方程的通解为：an?A?(7?137?13)?B?()?3?3n 22n解（n）：特征方程：??2?0 特征根：??2 齐次通解：an?A?2

nnnnnn非齐次通解：an?(B?Cn)2?D?3?E?4（因为f(n)?2?3?4，是现齐次的一重特征根）

代入非齐次方程：

(B?Cn)2n?D?3n?E?4n?2(B?C(n?1))2n?1?2D?3n?1?2E?4n?12111?2n?C?D?3n(1?)?E?4n(1?)?2n?C?D?3n?E?4n3232故有C＝1，D＝3，E＝2

nnn故此非齐次方程的特解为：an?(B?n)2?3?3?2?4

?2?3?4nnn

nnnnnnn于是非齐次方程的通解为：an?A?2?(B?n)2?3?3?2?4?(A?B?n)2?3?3?2?4

nnn令新的A为A＋B，有： an?(A?n)2?3?3?2?4

25

3102.28 an?an?1an?2，利用置换bn?log2(an)求解。

310【解】：由an?an?1an?2，两边取对数：log2an?3log2an?1?10log2an?2

令：bn?log2an，则有 bn?3bn?1?10bn?2 从而 bn?3bn?1?10bn?2?0

nn2特征方程：??3??10?0 特征根：?1??2,?2?5 齐次通解：bn?A?(?2)?B?5

将bn?log2an代入上式，有 log2an?A?(?2)n?B?5nan?2A?(?2)n?B?5n

2.29 题 an=an-1an-2 求这个递推关系的解

解：设 bn= log2an 由an=an-1an-2 得 bn－bn-1－bn-2=0 k(x)=x2－x－1=0

解得：r1=

11(1?5)，r2=(1?5) bn=A(r1)n+B(r2)n 22由??b0?A?Bb?rb2b?(1?5)b0rb?b(1?5)b0?2b1得 A?120?1 ,B?101?b?Ar?Brr1?r2r1?r2252512?1n

bn=

2b1?(1?5)b01?5n(1?5)b0?2b11?5()＋()222525 an=2

bn

2.30 题 解递推式an=an-12an-23

解： 令： bn=log2an

bn=log2(an-12an-23) =2log2an-1+3log2an-2=2bn-1+3bn-2

2

k(x)=x-2x-3=0

r1=3 r2=-1 bn=A3n+B(-1)n a0=1 b0=0 a1=2 b1=1

A+B=0 (1) 3A-B=1 (2) 由(1) (2)得： A=1/4 B=-1/4

bn=(1/4)3n+(-1/4)(-1)n

log2an=(1/4)3n+(-1/4)(-1)n

n(1/4)3n?(-1/4)(-1)an=2 2.31题 an?7an?1a12n?2，a0?1，a1?2，解个递推关系。

【解】：由an?7an?1a12n?2，两边取对数：log2an?7log2an?1?12log2an?2

令：bn?log2an，则有 b0?log21?0，b1?log22?0 bn?7bn?1?12bn?2

从而 bn?7bn?1?12bn?2?0

nn2特征方程：??7??12?0 特征根：?1?3,?2?4 齐次通解：bn?A?3?B?4

由初值，由??A?B?0?A??1nn，解之? 于是有bn??3?4

?3A?4B?1?B??1nn将bn?log2an代入上式，有 log2an??3?4an?2?3?4

nn 26

2.32 解下列递推关系 （a）an?nan?1，a0?1，an?? （b）an?an?1?【解】：（a）由an?nan?1，a0?1，得：an?n! （b）an?an?111a?7， （c） a?a?0nn?1nn231?1??n??? 特征方程：??1?0 特征根：??1 齐次通解：an?A?1n?A 2?2??1??2?1111 代入非齐次方程： B??B??nn?1n2n222n非齐次特解：an?B????B? B?2B?1 ?B?1 B?1 从而非齐次特解：an?A?1?7（c）an?an?111 于是非齐次特解： a?A?n2n2n1a?7?1?6 所以 an?6?n

2n1?1??n??? 3?3??1??3?1 n3n特征方程：??1?0 特征根：??1 齐次通解：an?A?1?A 非齐次特解：an?B????B?1111 ?B??B??B?3B?1?2B?1nn?1n23331111从而非齐次特解：an?(?)?n 于是非齐次特解：an?A?(?)?n

2323代入非齐次方程：B?222.37 利用置换an?bn解 an?(2an?1?3an?2)，a0?1，a1?4。

2【解】：（置换法）将an?bn代入，有

22(1) 若bn>0, bn?(2bn?1?3bn?2) bn?2bn?1?3bn?2

特征方程：?2?2??3?0 特征根：?1?3,?2??1 通解：bn?A?3?B(?1)n

?A???A?B?1?初值：b0?1，b1?2 ? 解得?3A?B?2??B???故此，bn?34 1431112?3?(?1)n?[3?3n?(?1)n] 于是，an?bn?[3?3n?(?1)n]2 4441622（2）若bn<0,则有：bn?(?2bn?1?3bn?2) bn??(?2bn?1?3bn?2) bn?2bn?1?3bn?2

?A??3A?B??1??4n从而 bn?A?3?B(?1) 初值：b0??1，b1??2 ? 解得?

13A?B??2B?????4故此，bn??[3?3?(?1)] 于是，an?bn?

27

14nn21[3?3n?(?1)n]2 16Fn?2Fn?1?(Fn?1?Fn)(Fn?1?Fn)?Fn2?1?Fn2）F1，F2是Fibonacci序列，2.33 F0，求解an?an?1?Fn?2Fn?1。（提示：

n【解】：特征方程：??1?0 特征根：??1 齐次通解：an?A?1?A

222由于Fn?2Fn?1?(Fn?1?Fn)(Fn?1?Fn)?Fn?1?Fn 故此非齐次得一个特解：an?Fn?1 2因此，非齐次得通解为：an?A?Fn?1

2.34 an?an?1???3??n?2???，a0?0，求an。 ?n【解】：特征方程：??1?0 特征根：??1 齐次通解：an?A?1?A

非齐次特解：an?B0?B1?????B2?????B3?????B4????

?n??1??n??2??n??3??n??4??n??n??n??n??n?1??n?1??n?1??n?1?于是an?an?1?B0?B1???B2???B3???B4???B0?B1???B2???B3???B4??

12341234????????????????11?B1?B2(n?1)?B3?(n?2)(n?2)?B4?(n?1)(n?2)(n?3)26

?n?2?n(n?1)(n?2)????6?3?3?2?14?3?2?1； 令n?2，有B1?B2??4，于是B2?4?B1?3； 665?4?3令n?3，有B1?2B2?B3??10， 于是B3?10?B1?2B2?10?1?2?3?3；

66?5?4令n?4，有B1?3B2?B3?B4??20，

6令n?1，有B1?于是B4?10?B1?3B2?3B3?20?1?3?3?3?3?1； 则非齐次特解：an?B0???1???3??2???3??3?????4??

?n????n????n??n??????n???从而，非齐次的通解：an?A?B0???1???3??2???3??3?????4??

?n????n??n?????将a0?0代入，有A?B0?0，于是非齐次的解为：an???1???3??2???3??3?????4??

?n????n????n??n?????

28

2.35 an?an?1???4??n?3???，a0?0，求an。 ?n【解】：特征方程：??1?0 特征根：??1 齐次通解：an?A?1?A

非齐次特解：an?B0?B1?????B2?????B3?????B4?????B5????

?n??1??n??2??n??2??n??3??n??4??n??5?于是an?an?1?B0?B1???B2???B3???B4???B5???B0?B1??n??1??n??3??n??4??n??5??n?1??n?1??n?1??n?1??n?1??B?B?B?B?2??3??4??5?? 12345??????????111?B1?B2(n?1)?B3?(n?2)(n?2)?B4?(n?1)(n?2)(n?3)?B5?(n?1)(n?2)(n?3)(n?4)23!4!

?n?3?n(n?1)(n?2)(n?3)????4!?4?4?3?2?15?4?3?2?1； 令n?2，有B1?B2??5，于是B2?5?B1?4；

4!4!6?5?4?3令n?3，有B1?2B2?B3??15， 于是B3?15?B1?2B2?15?1?2?4?6；

4!7?6?5?4令n?4，有B1?3B2?3B3?B4??35，

4!令n?1，有B1?于是B4?35?B1?3B2?3B3?35?1?3?4?3?6?4； 令n?5，有B1?4B2?5B3?4B4?B5?8?7?6?5?70，

4!于是B5?70?B1?4B2?6B3?4B4?35?1?4?4?6?6?4?4?1； 则非齐次特解：an?B0???1???4??2???6??3???4??4?????5??

?n????n????n????n??n??????n???从而，非齐次的通解：an?A?B0???1???4??2???6??3???4??4?????5??

?n????n????n??n??????n???将a0?0代入，有A?B0?0，于是非齐次的解为：an???1???4??2???6??3???4??4?????5??

?n????n????n??n?????nn2.36 利用迭代法解：（a）an?3an?1?3?1，a0?0；（b）an?4an?1?4，a0?0。

12222【解】：（a）(迭代法) a1?3a0?3?1?3?1 a2?3a1?3?1?3?3?3?1?2?3?(3?1)

a3?3a2?33?1?2?33?3?(3?1)?33?1?3?33?(32?3?1)a4?3a3?34?1?3?[3?33?(32?3?1)]?34?1?4?34?(33?32?3?1)

nn?1n?2n?32设an?1?(n?1)?3?(3?3?????3?3?1) 于是，an?3an?1?3?1

29

?3[(n?1)?3n?1?(3n?2?3n?3?????32?3?1)]?3n?13n?1 ?n?3?(3?3?????3?3?1)?n?3?3?1111?n?3n?(3n?1)?(n?)?3n?222nn?1n?22nn1222（b）(迭代法) an?4an?1?4 a1?4a0?4?3 a2?4a1?4?4?4?4?2?4

a3?4a2?43?4?2?42?43?3?43a4?4a3?44?4?3?43?44?4?44

n?1nn?1nn设an?1?(n?1)?4 于是，an?4an?1?4?4(n?1)?4?4?n?4

2.38 利用置换an?n!bn解 an?2nan?1?7n!，a0?1。

【解】：（置换法）将置换an?n!bn代入递推方程，有 n!bn?2n?(n?1)!bn?1?7n! 整理，得：bn?2bn?1?7 特征方程：??2?0 特征根：??2

nn齐次通解：bn?A?2 非齐次特解：bn?B?1?B

代入非齐次方程，有： bn?2bn?1?B?2B?7 即B??7

n从而非齐次得特解为：bn?7 故非齐次的通解为：bn?A?2?7

由初值a0?1得，a0?0!b0?1?b0，故b0?1

1?A?20?7，从而1?A?1?7，即A?8

nn于是有bn?8?2?7，从而an?n!(8?2?7)

2.39 利用置换an?bnn解 an?n?11an?1?，a1?5。 nn【解】：（置换法）将置换an?bnn代入递推方程，有

bnn?1bn?11?? nnn?1nn整理，得：bn?bn?1?1 特征方程：??1?0 特征根：??1 齐次通解：bn?A?1 n非齐次特解：bn?(B?Cn)?1?B?Cn（因为f(n)?1，1是一重特征根）

代入非齐次方程，有： bn?bn?1?B?Cn?(B?C(n?1))?C?1 从而非齐次特解为：bn?B?n 故非齐次的通解为：bn?A?B?n 于是将an?bnn代回，有 nan?A?B?n

由初值a1?5得 1?5?A?B?1，从而A?B?4 因此，有an?

30

4?n4?1? nn

2.40解下列递推关系：（a）an?4n(n?1)an?2?5n!?3n,a0?1,a1??1； 9nn（b）an?9n(n?1)an?2?14n!?2，a0?42,a1?28； （c）an?3an?1?5?3,a0?0；

【解】：（a）（置换法）令an?bnn!代入递推方程，有n!bn?4n(n?1)bn?2(n?2)!?整理，得：bn?4bn?1?5n!?3n 95n?3 特征方程：?2?4?0 特征根：?1??2，?2?2 9nnn齐次通解：bn?A?(?2)?B?2 非齐次特解：bn?C?3

代入非齐次方程，有： C?3?4C?3nn?2?5?3n， 9n整理，有C(1?4)?5，故C?1 从而非齐次的特解为：bn?3

99nnn故非齐次的通解为：bn?A?(?2)?B?2?3

由初值a0?1得，a0?0!b0?1?b0，故b0?1 a1??1得，a1?1!b1?1?b1，故b1??1 代入有??A?B?1?1?A?B?0?A?2，故?，即?

??2A?2B?3??1?A?B?4?B??2nnnnnn因此，bn?2?(?2)?2?2?3 于是，an?n!?[2?(?2)?2?2?3] n（b）（置换法）令an?bnn!代入递推方程，有n!bn?9n(n?1)bn?2(n?2)!?14n!?2

n2整理，得：bn?9bn?1?14?2 特征方程：??9?0 特征根：?1??3，?2?3

nnn齐次通解：bn?A?(?3)?B?3 非齐次特解：bn?C?2

代入非齐次方程，有： C?2?9C?2整理，有C(1?)?14，故C??nn?2?14?2n，

14?45656?? 从而非齐次的特解为：bn???2n 55556nnn故非齐次的通解为：bn?A?(?3)?B?3??2

5由初值a0?1得，a0?0!b0?1?b0，故b0?42 a1??1得，a1?1!b1?1?b1，故b1?28

4956266??91A?B?A?B??42???A????55代入有?，故?，即?5

8456?2???A?B???3A?3B??28?B?35??55??91569156?(?3)n?35?3n??2n 于是，an?n!?[?(?3)n?35?3n??2n] 5555nn（c） 特征方程：??3?0 特征根： ??3 齐次通解：an?A?3 非齐次特解：aa?(B?Cn)?3

nn?1nn代入非齐次方程，有： aa?an?1?(B?Cn)?3?3(B?C(n?1))?3?3?C?5?3

n故C?5, 从而，从而非齐次的特解为：an?(B?5n)?3

nnn故非齐次的通解为：an?A?3?(B?5n)?3?(A?B?5n)?3

n令A为A＋B后，有an?(A?5n)?3

nn利用a0?0，有A?3?0，知A?0，从而an?5n?3

因此，bn?

31

n2.41设an满足：an?b1an?1?b2an?2?5?，其中：b1，b2和?都是常数，试证该序列满足三阶奇次线性常系数奇次

递推关系，且有特征多项式(x??)(x?b1x?b2)。

【解】：满足特征多项式为(x??)(x?b1x?b2)?x?(b1??)x?(b2??b1)x??b2?0的递推关系为

2322an?(b1??)an?1?(b2??b1)an?2??b2an?3?0 ①

整理为(an?b1an?1?b2an?2)??(an?1?b1an?2?b2an?3)?0 ②

将关于序列{an}的递推关系： an?b1an?1?ban?2?5?n ③

n?1nn??5???5???5??? 0?2这说明序列{an}满足三阶奇次线性常系数奇次递推关系①，且有特征多项式(x??)(x?b1x?b2)。

2.42设{an}满足an?an?1?an?2?0，{bn}满足bn?2bn?1?bn?2?0，cn?an?bn，n?0,1,2,3,???，试证序列{cn}?(aa2?代入②，有 (an?b1an?1?b2an?)2?n?1?b1n?b)3?5?n?2n?a满足四阶奇次线性常系数奇次递推关系。

【解】：方法一（特征系数法）

由于序列{an}满足递推关系： an?an?1?an?2?0 ①

故显然也满足递推关系：(an?an?1?an?2)?A1(an?1?an?2?an?3)?A2(an?2?an?3?an?4)?0 这里A1，A2为任意常数

整理为：an?(A1?1)an?1?(A2?A1?1)an?2?(A1?A2)an?3?A2an?4?0 ② 由于序列{bn}满足递推关系：bn?2bn?1?bn?2?0 ③

故显然也满足递推关系 (bn?2bn?1?bn?2)?B1(bn?1?2bn?2?bn?3)?B2(bn?2?2bn?3?bn?4)?0 这里A1，A2为任意常数

整理为：bn?(B1?2)bn?1?(B2?2B1?1)bn?2?(B1?2B2)bn?3?B2bn?4?0 ④

?A1?1?B2?2?A?A?1?B?2B?1?A1??2?B1??1?2121令?，解之得?，?

?A2??1?B2??1?A1?A2?B1?2B2??A2?B2将此代入②，④有 an?3an?1?3an?3?an?4?0 ⑤

bn?3bn?1?3bn?3?bn?4?0 ⑥

将⑤＋⑥，并注意到cn?an?bn，我们有cn?3cn?1?3cn?3?cn?4?0 ⑦ 这就是序列{cn}满足的四阶线性常系数奇次递推关系。

?1??2???1?0特征根：方法二（特征根法）递推关系an?an?1?an?2?0 特征方程：

1?5n1?5n)?B() 递推关系bn?2bn?1?bn?2?0 221?51?5,?2? 22故其通解：an?A(特征方程：?2?2??1?0 特征根：?1?1?2,?2?1?2

故其通解：bn?C(1?2)n?D(1?2)n 于是cn?an?bn?A(1?5n1?5n)?B()?C(1?2)n?D(1?2)n 22因此序列{cn}满足的四阶线性常系数奇次递推关系。 其特征多项式为(??21?51?5)(??)(??(1?2))(??(1?2))?0 2243整理为(????1)(??2??1)?0 再整理为??3??3??1?0 因此，对应的四阶线性常系数奇次递推关系为 cn?3cn?1?3cn?3?cn?4?0

32

22.43题 已知an=an-1+an-2;bn=2bn-1+bn-2;cn=anbn;n=0,1,2,…,求cn的递推关系。

解：cn=anbn=(an-1+an-2)(2bn-1+bn-2)=2cn-1+cn-2+an-1bn-2+2an-2bn-1 (1)

=2cn-1+cn-2+(an-2+an-3)bn-2+2an-2(2bn-2+bn-3) =2cn-1+6cn-2+an-3bn-2+2an-2bn-3

=2cn-1+6cn+an-3(2bn-3+bn-4)+2(an-3+an-4)bn-3

=2cn-1+6cn-2+4cn-3+an-3bn-4+2an-4bn-3 (2) 由(1)式得： an-1bn-2+2an-2bn-1=cn-2cn-1+cn-2 所以有an-3bn-4+2an-4bn-3=cn-2-2cn-3-cn-4 代入(2)式得cn=2cn-1+7cn-2+2cn-3-cn-4 2-44题 设{an}和{bn}均满足递推关系xn?b1xn?1?b2xn?2?0，试证：

(a){anbn}满足一个三阶奇次线性常系数奇次递推关系；(b) a0,a2,a4???二阶线性常系数奇次递推关系。

【证】：(a)（特征根法）二阶奇次线性常系数奇次递推关系xn?b1xn?1?b2xn?2?0的特征方程为

x2?b1x?b2?0 ①

nnnn甲. 设其特征根为?1，?2，?1??2，则有：an?A??1?B??2 bn?C??1?D??2

nnnn于是cn?anbn?(A??1?B??2)(C??1?D??2)

?AC?(?1)?(AD?BC)?(?1?2)?BD(?2) 这说明{cn}满足一个三阶奇次线性常系数奇次递推关系， 其特征方程为： (x??1)(x??1?2)(x??2)?0

或者x?(?1??1?2??2)x?(?1?2??1?2??1?2)x?(?1?1)?0 由于?1??2??b1，?1?2?b2，故?1??1?2??2?b1?b2 因此有x?(b1?b2)x?b2(b1?b2)x?b2?0

223故此{cn}满足如下三阶奇次线性常系数奇次递推关系cn?(b1?b2)cn?1?b2(b1?b2)cn?2?b2cn?3?0

2nn2n2232223223322232223乙.

设其特征根为?是一个二重根，则：an?(A?Bn)??n bn?(C?Dn)??n 于是cn?anbn?(A?Bn)(C?Dn)?(?)

?(AC?(AD?BC)n?BDn)(?) 这说明{cn}满足一个三阶奇次线性常系数奇次递推关系， 其特征方程为： (x??)?x?3?x?3?x??3222n22n2332246?0

32由于2???b1，??b2，因此有x?3b2x?3b2x?b2?0

23故此{cn}满足如下的三阶奇次线性常系数奇次递推关系 cn?3b2cn?1?3b2cn?2?b2cn?3?0 nn2n2n(b)甲. an?A??1?B??2 a2n?A?(?1)?B?(?2)

因此，这说明{a2n}满足一个二阶奇次线性常系数奇次递推关系

其特征方程为(x??1)(x??2)?0 整理为：x?(?1??1)x?(?1?2)?0 由于?1??2??b1，?1?2?b2，有?1??2?b1?2b2 于是x?(b1?2b2)x?b2?0

22故此序列{a2n}满足一个二阶奇次线性常系数奇次递推关系为：cn?(b1?2b2)cn?1?b2cn?2?0

222222222222乙. an?(A?Bn)?? a2n?(A?Bn)?(?)

因此，这说明{a2n}满足一个二阶奇次线性常系数奇次递推关系 其特征方程为(x??)?0 整理为：x?2?)x??

33

22422n2n?0 由于2???b1，?2?b2，于是x2?2b2x?b22?0

2故此序列{a2n}满足一个二阶奇次线性常系数奇次递推关系为：cn?2b2cn?1?b2cn?2?0

2.45题 已知F0,F1,F2……是Fibonaci序列，试找出常数a,b,c,d使：

F3n?aFnFn?1Fn?2?bFn?1Fn?2Fn?3?cFn?2Fn?3Fn?4?dFn?3Fn?4Fn?5

解：当n=0时 F0?aF0F1F2?bF1F2F3?cF2F3F4?dF3F4F5

当n=1时 F3?aF1F2F3?bF2F3F4?cF3F4F5?dF4F5F6 当n=2时 F6?aF2F3F4?bF3F4F5?cF4F5F6?dF5F6F7 当n=3时 F9?aF3F4F5?bF4F5F6?cF5F6F7?dF6F7F8

注意到F0?0，F1?F2?1，F3?2，F4?3，F5?5，F6?8，F7?13，F8?21，F9?34，得到

?0?2b?6c?30d?0?a??17?2a?6b?30c?120d?2?b?21?? ????6a?30b?120c?520d?8?c?13???30A?120B?520C?2184D?34?d??4经验证当n=4时亦成立。

2.46题 对所有的正整数a,b,c,恒有Fa?b?c?3?Fa?2(Fb?1Fc?1?Fb?1Fc)?Fa?1(Fb?1Fc?1?FbFc)

证明：固定n ，利用第二归纳法可证

当m=1时 Fn+1=F1Fn+1+F0Fn，F0=F1=1 Fn+1=Fn +Fn+1成立 假定当m<=k时成立 Fk+n=(FkFn+1)+(Fk-1Fn) 则要证m=k+1时Fk+1+n=(Fk+1Fn+1)+(FkFn)

Fk+1+n=(Fk+n)+(Fk+n-1)=(FkFn+1)+(Fk-1Fn)+(Fk-1Fn+1)+(Fk-2Fn)

=(Fk+Fk-1)(Fn+1)+((Fk-1)+Fk-2)Fn=(Fk+1Fn+1)+FkFn 即证 所以Fb?2?c代入右边

?Fb?2Fc?1?Fb?1Fc Fb?1?c?Fb??FbF c1Fc?1Fa?2?b?c?1?Fa?2Fb?2?c?Fa?1Fb?1?c 即证

2222?n??n??n??n??2n?4810020

????????????..?.?2.47题 证明等式? 求(1+x+ x)中x项的系数. ?0??1??2??n??n???????????解法一：利用第一章的第8节的公式7：令m = n, r = n即可。

?n??n?n?n??2n?n???????(1?x)(1?x)?(1?x)x??????解法二：利用恒等式，比较两边的系数x:???? ???。kn?kknk?0????k?0????nn2nnn2或是观察母函数(1?x)(1?n1n)的常数项，都可以得到结论。 x964x+8y=20并且x+2y=5解得x=5,y=0;x=1,y=2；x=3,y=1。

1x95???x?4580:100!95!5!

1?x43??x81?:100!96!3!1!

197x4???x?182:100!97!1!2!

共91457520.

2.48题 有红、黄、蓝、白球各两个，绿、紫、 黑的球各3个，问从中取出10个球，试问 有多少种不同的取法？

解： (用指数型母函数，可得母函数 ,x10系数即为所求。)

同色球看做是相同的。求(1+x+x2)4(1+x+x2+x3)3中x10的系数。(1-x3)4(1-x4)3/(1-x)7

x3 : 0 0 0 1 1 2 2 3 x4 : 0 1 2 0 1 0 1 0 x : 10 6 2 7 3 4 0 1

?6?10??3??6?6??3??6?2??4??6?7??4??3??6?3??4??3??4??6?4??4??6?1???10?????1????6?????2????2?????1????7?????1????1????3?????2????1?????2????4?????3????1??=678 ????????????????????????????????

34

2.49题 求由A,B,C,D组成的允许重复的排列中 AB至少出现一次的排列数目。

解 设an为所求个数，bn为不出现AB的串的个数

an+bn=4n, bn=4bn-1-bn-2, an=4an-1+bn-2,

b1=4,b2=15,b0=1,b3=56.

x2-4x+1=0 解得 x=2?bn=S(2+3)n+t(2-3)n

3。

S?t?1? ?2?3S?2?3t?4??????S=22?33,t=?2?323

bn?12?2?33??1?n?1an?4?2n?2?3??????

??3???2?3??2?3n?1n?12n?1?a?4n?1?2?323???n?22??n?1?2?3??n?1?

??2.50.题 求n位四进制数中2和3必须出现偶次的数目。

x?x???x2x4??x22x?e?e2x?2x12x?...??1???...??e?解：Ge?x???1?x???4e?e?2?e??2!2!4!?????2?14?e4x?2e2x?1?

xn:n!14?4n?2?2n?4n?1?2n?1

?2.51题 试求由a,b,c三个文字组成的n位符号串 中不出现aa图像的符号串的数目。

解 设不出现aa的字符串的排列数为an

在所有符合要求的n位串中，最后一位是a,则n-1位是b或c，最后一位不是a，则是b或c.故有 an=2an-1+2an-2，a1=3，a2=8，a0=1.

x2-2x-2=0,解得 x=1?3。 an=A(1+3)n+B(1-3)n

A?B?1? ?1?3A?1?3B?3??????22??1?3?1?3?A=43,B=?43

an??413?1?3???n?2?1?3??n?2?

??2.52题 证明C(n,n)+C(n+1,n)+ … + C(n+m,n)=C(n+m+1,m).

证法一 对m做归纳，m=0时，等式成立。 假设对m-1,等式成立。

C(n,n)+C(n+1,n)+ … + C(n+m-1,n)+C(n+m,n)=C(n+m,n+1)+C(n+m,n) =C(n+m,m-1)+C(n+m,m)=C(n+m+1,n+1) =C(n+m+1,m). 证毕。

证法二： 等式的右端相当于从n+m+1个球中取n+1个球的组合。 把这n+m+1个球编号:

如果取出的n+1个球中最小编号是1，则得到 C(n+m,n); 如果最小编号是2则得到C(n+m-1,n)；…… 如果最小编号是m则得到C(n,n)。

于是就有C(n,n)+C(n+1,n)+…+C(n+m,n) = C(n+m+1,n+1) =C(n+m+1,m)

35

2.53 题 利用

11+2122+

132+。。。=?，改善pn估计式

26xx1xn(1?x) 解：由于lnG(x)< ?·，知道lnPn< ?·+n·ln

x61?xx61?x61?x222?x?(0,1),所以lnPn?2?2xn(1?x)2n··??。所以Pn?e61?xx32n?3。

2.54题 8台计算机分给3个单位，第一个单位的分配量不超过3台，第二个单位的分配量不超过4台，第三个单位的分配量不超过5台，问共有几种分配方案？

解：利用母函数(1+ x1+x2+x3)(1+ x1+x2+x3+x4)(1+x1+x2+x3+x4+x5)，x8的系数就是该题的答案。

x8的系数为14，所以该题答案：14。

2.55 题 证明任一个正整数n都可以写成不同的Fibonacci数的和。 解：该题的意思就是证明n=

?aF，aa

iii?2ii+1=0，ai=0，1。其中F1= F2=1是相同的Fibonacci数。对n用归纳法

1） 当n=1时，命题成立

2）设对小于n的正整数命题成立，对于n+1，如果存在i使得n+1=Fi，显然成立。否则存在i，满足Fi

2.56题 空间有ｎ个平面，任意３个平面交于一点，无四平面共点。问这样的ｎ个平面将空间分 割成多少个不重叠的域？

解：设n个满足条件的平面把空间分成an个域，第n条直线与前n-1个直线有n-1个交点，第n条直线被分成了n

段，而原来的区域被分成了2n

an=an-1+n，an= A0+ A1n+ A2?? a0=1, a1=2, a2=4, A0= A1= A2=1。所以an=1+n+??

?????n??2??n??2?bn= bn-1+ an-1，bn= B0+ B1n+ B2??+?? b0=1，b1=2，b2=4，b3=8，B0=B1=B2=B3=1。所以bn=1+n+??+??

?2??3??2??3?????????2.58题 在Hanoi塔问题中，在柱A上从上到下套着n个圆盘，其编号依次从1到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(1)=1,k(2)=2,k(3)=5 h(k)为Hanota数列。

?n??n??n??n?

可得特征方程： 代入初值可解得 K(n)?

解得

5n212322??cosn??sinn? 732137336

2.57题 相邻位不同为0的n位二进制数，总共有多少个0？

解 设相邻位不同为0的n位2进制数的个数为hn 个，这些数中一共有an个0， 当n位二进制数最高位为1时,符合条件的n位二进制数的个数为hn-1

最高位为0时，次高位必为1符合条件的n位二进制数的个数为hn-2 hn?hn?1?hn?2，h1=2,h2=3,h0=1. 即hn是F数列

特征方程为：

解得a、b为2重根。 设

分析上式结构可得：

把n=2代入可解得：

代入an

可得方程组 解得

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

1(1?5)，作C1B1使AB1C1D是一正方形，试证B1C1CB和ABCD相似，2试证继续这一过程可得一个与原矩形相似的矩形序列

解：... 把AD看成1 则AB为

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

37

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

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

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

2 特征方程为 x?x?1?0,?x1?1?51?5, x2? 222???11?5??A???A?B?1???5?2??nn? 1?5代入得 ?an?Ax1?Bx2 ?1?52A?B?2??11?5??2?2?B??????5?2???所以an?1?1?5n?21?5n?2???()?()?

225??

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

a1?n，a2?n2，a3?n3?n 答案：设所求为ak则ak?(n?1)ak?1?(n?1)ak?2

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

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

38

nn可设 an?Aa?B?把初值代入即可求得A，B=>an

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

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

∴Sn?1满足递推关系 Sn?6Sn?1?15Sn?2?20Sn?3?15Sn?4?6Sn?5?Sn?6?0

?A1?1?A?152??n??n??n??n??n??????????代入可解得 ?A3?50 Sn?1??15?50?60?24?1??2??3??4??5?? ???????????A?60?4??A5?24?3?1?2.66.题 求矩阵??02????n100。

?3?1??3n解：设??02??=?????0?3n?1an??3?1??3?1??3n?1?????=????n?1??2??02??02???0n?1an?1?? n?1?2?100?2an?1?3an?1?2,an?1?3?1?n?1n?1nnn?2?3,a?2?3 所以??02?????3100=??0?2100?3100?? 100?2?)n?2.67题 (1S?kk?0n(k?1),(S2)??kk?(nk?0n2),nS(?3)?k?0nkk?(K? 1)(2)解：（1）因为 sn?sn?1?n(n?1)①

同理sn?1?sn?2?(n?1)(n?2)⑵ ①-②：sn?2sn?1?sn?2?2(n?1)③ 同理：

sn?1?2sn?2?sn?3?2(n?2)④

③-④：sn?3sn?1?3sn?2?sn?3?2⑤ 同理：sn?1?3sn?2?3sn?3?sn?4?2⑥ ⑤-⑥ sn?4sn?1?6sn?2?4sn?3?sn?4?0

所以特征方程为：x?4x?6x?4x?1?0 X=1是4重根

432sn?(A?Bn?Cn2?Dn3)1n

A=0 B+C+D=0 2B+4C+8D=2 3B+9C+27D=8 解方程得 A=0 B??13(2)和第一题同理

（3）sn?sn?1?n(n?1)(n?2) 有二项式定理可设 sn?An?B?????C?????D???? S1=A=6 S2=2A+B=30 S3=3A+3B+C=90 S4=4A+6B+4C+D=210 联立解 A=6 B=18 C=18 D=6 所以sn?6n?18?????18?????6????

2.68题 在一个平面上画一个圆，然后一条一条地画n条与圆相交的直线。当r是大于1的奇数时，第r条直线只与前r-1条直线之一在圆内相交。当r是偶数时，第r条直线与前r-1条直线在圆内部相交。如果无3条直线在圆内共点，这n条直线把圆分割成多少个不重叠的部分？

39

1C=0 D?13 所以 sn?3n(n?1)(n?1)

?n??2??n??3??n??4??n??2??n??3??n??4?解 当r是奇数（>1）时 ar?ar?1?2?ar?2?r?1 当r是偶数时 ar?ar?1?(r?1)?1?ar?2?r?2

?(n?1)(n?3)n为奇数?4 ?an??

n(n?6)?n为偶数4?当n是偶数，?an?3,?n?12.69题 用an记具有整数边长、周长为n的三角形的个数。 （1）证明 ：an?? n???1?2an?3?，当n是奇数?4?（2）求序列{an}的普通形母函数。

解：(1) ①.当n是偶数时 对所有符合条件的ar-3来说，每边增加1各单位，则可构成符合条件的ar。 ?ar?ar?3

设短边为a、b，长边为c，则(a+b)-c>=2即a+b-2>c-1，对所有符合条件的ar来说，每边减少1各单位， 则可构成符合条件的ar-3

?ar?ar?3?ar?ar?3

②当n为奇数时 由I的讨论知，ar比ar-3多了a+b-c=1的三角形。 而这种三角形可知

. 当

能被2整除时，这种三角形有

n?1个 4当 不能被2整除时，这种三角形有

n?1个 4

(2)

下面求它的普通母函数：a2k?a2k?3，a2k?1?a2k?2记f(x)?2k?1?(?1)k?1 ?4?ak?0??2kx2k，g(x)??ak?0??2k?1x2k?1

??那么

??f(x)??a2kxk?02k?1??2k?a0?a2x?x??23?ak?22k?3x2k?3?x3g(x)

?2k?1?(?1)k?1?2k?1g(x)??a2k?1x?a1x???a2k?2??x4k?0k?1???????????kxxxx?1???

?x3?a2k?2x2k?2???2k?1?x2k????x2??x3f(x)???x2k?1?x????1?24k?14k?14?k?0?k?1?4?1?x4x?x3f(x)??1?x2??1?x4?x7x4所以：f(x)??1?x2??1?x4??1?x6? g(x)??1?x2??1?x4??1?x6?

x4?an?的普通母函数就是 f(x)?g(x)? 234?1?x??1?x??1?x?21??4(L?1)2.70 （a）证明边长为整数、最大边长为L的三角形的个数是 ?1(L?2)L??4当L是奇数时当L是偶数时

40

（b）设fn记边长不超过2n的三角形的个数，而gn记边长不超过2n+1的三角形的个数，求fn和gn 的表达式。

解：(a) l=1时，只有一种可能（即3边都是 长度为1）。 1(l?1)?1

42 l=2时，有两种可能（即“1，2，2”、 “2，2，2”）。 12(2?2)?2

4设三角形的3边边长为x、y、z， 且 x≤y≤z=l,x+y≥z。

l=2k+1时 x+y=2k+2时，有k+1种方案，即“1，2k+1”、“2，2k”、...…、“k+1，k+1”。 x+y=2k+3时，有k种方案，即“2，2k+1”、“3，2k”、...…、“k+1，k+2”。 x+y=2k+4时，有k种方案，即“3，2k+1”、“4，2k”、...…、“k+2，k+2”。 … … … …

x+y=4k+1时，有1种方案，即“2k，2k+1”。

x+y=4k+2时，有1种方案，即“2k+1，2k+1”。

总和?2?(i?k?1)?2*1k(k?1)?k?1?(k?1)2?1(l?1)2

24l?1l=2k时 x+y=2k+1时，有k种方案，即“1，2k”、“2，2k-1”、...…、“k，k+1”。

x+y=2k+2时，有k种方案，即“2，2k”、“3，2k-1”、...…、“k+1，k+1”。 x+y=2k+3时，有k种方案，即“3，2k”、“4，2k”、...…、“k+2，k+2”。 … … … …

x+y=4k-1时，有1种方案，即“2k-1，2k”。 x+y=4k时，有1种方案，即“2k，2k”。 总和＝2k?(i)?k(k?l)?i?1kll?21???l(l?2) 22421??4(k?1)，当k是奇数（b） ak??1k(k?1)，当k是偶数

??4 fn??ak?12nk,gn??ak

k?12n?11(2n)(2n?2)?n(n?1)4gn?gn?1?a2n?1?a2n?(n?1)2?n(n?1)fn?gn?1?a2n?a1=1,a2=2,a3=4,a4=6, f1=a1+a2=3,f2=13,f0=0, f3=34,

g1=a1+a2+a3=7,g2=22,g0=1, g3=50,

gn?fn?a2n?1?1(2n?2)2?(n?1)24

fn?fn?1?n(n?1)?n2?n??n??fn?A0?A1n?A2??A?2?3??3?? ????A0=0,A2=0,

f2=13=6+A2=>A2=7

f3=34=9+21+A3=>A3=7

?n??n??gn?B0?B1?B2??B3??2??3??, ????B0=1,

g1=7=1+B1=>B1=6,

41

g2=22=B0+2B1+B2=>B2=9

g3=50=B0+3B1+3B2+B3=>B3=4,

∴fn?3n?7?????4???? gn?1?6n?9?????4????

n?n??2??n??3??n??2??n??3?2.71 第一类stirling数[x]?x(x?1)…(x+n-1),nn[x+y]??c(n,r)[x]n?r[y]r.

nr?0证明：左边＝[x+y]?(x?y)(x?y?1)...(x?y?n?1)

n右边＝?c(n,r)[x]n-r[y]r??0?[x]n[y]0＋?1n?[x]n?1[y]1?…?nn?[x]0[y]nr=0n

s(n?1,k)?s(n,k?1)?ns(n,k)?左边＝右边。2.72 试证：x1?x2?????xm?n，有?m?/n?c(n?m?1,m?1)个非负整数解，其中m和n都是正整数。

n解：该题为第一类斯特林数，略。

2.73 已知非负整数S1,S2,???,Sm，求满足x1?x2?????xm?n,xi?Si,i?1,2,???,m的整数解的数目。

解：由题已知：xi?Si,i?1,2,???,m 故： xi?Si?0,i?1,2,???,m

因为： x1?x2?????xm?n 所以有： (x1?S1)?(x2?S2)?????(xm?Sm)?n?m?Si?1i

m??m?(n?S)?1?i??mi?1? 设： yi?xi?Si 则： y1?y2?????ym?n??Si ，yi?0其方案数为：?m??i?1n?S?i??i?1??m??m?(n?S)?1?i??i?1? 所以，满足x1?x2?????xm?n,xi?Si,i?1,2,???,m的整数解的数目为：?m??n?S?i??i?1??2.75设 F1=F2=1, Fn=Fn-1+Fn-2 （a）证明 Fn?FkFn?k?1?Fk?1Fn?k,n?k?1。 （b）证明Fm|Fn的充要条件是m|n。 [m被n整除] （c）证明 FmFn?Fn?m?2?Fm?n?6?Fm?n?10?...???Fm?n?1，当n是奇数,m?n?2。

?Fm?n?2，当n是偶数（d）证明(Fm,Fn)=F(m,n), (m,n)为m,n的最大公约数。

解：(a)证 （对k用归纳法）k=2时，Fn = F2Fn-2+1 + F1Fn-2 ，等式成立。假设对于k，等式成立。 下证对于k+1等式成立。

由归纳假设，Fn = FkFn-k+1 + Fk-1Fn-k = Fk (Fn-k + Fn-k-1)+ Fk-1Fn-k = (Fk + Fk-1) Fn-k + FkFn-k-1

= Fk+1Fn-k + FkFn-k-1 。 证毕。

(b)证 对m用数学归纳法。m=0时，命题成立。假设对小于m的正整数，命题成立，设m≥n,

Fm?FnFm?n?1?Fn?1Fm?n，FnFm?FnFn?1Fm?n，因（Fn,Fn-1）=1,故FnFn?1Fm?n?FnFm?n,有归纳假设

FnFm?n?nm?n?nm

(c)证

对n用归纳法.n=2时，等式成立。

42

n=3时，Fm F3= Fm+3-2 + Fm-3+1 = Fm+1 + Fm-2 = Fm + Fm-1 + Fm - Fm-1 =2 Fm ,等式成立。 假设对小于n的正整数，等式成立。Fm?2Fn?2?Fm?2?n?2?2?Fm?2?n?2?6??Fm?2?(n?2)?1，当n是奇数,????

F，当n是偶数。??m?2?(n?2)?2利用 Fm Fn= Fm+n-1 - Fm-1 F n -1 = Fm+n-1 –(Fm-1+n-1-1 –Fm-2 Fn-2)= Fm+n-2 + Fm-2Fn-2 故有FmFn?Fm?n?2?Fm?n?6?????Fm?n?1，当n是奇数,?Fm?n?2，当n是偶数。

（d）证 对max{m,n}用归纳法，当m=n时，等式成立。设m>n，假设对小于max{m,n}的正整数，等式成立。 因

Fm?FnFm?n?1?Fn?1Fm?n，?Fm,Fn???Fn?1Fm?n,Fn???Fm?n,Fn??F?m?n,n??F?m,n?

2．76. 从1到n的自然数中选取k个不同且不相邻的数，设此选取的方案为f(n,k)。

（a）求f(n,k)的递推关系。 （b）用归纳法求f(n,k)。 （c）若设1与n算是相邻的数，并设在此假定下从1到n的自然数中选取k个不同且不相邻的k个数的方案数为g(n,k)，利用f(n,k)求g(n,k)。

解（a） （b）

n?k?1n?4?k?2?1g(n,k)?f(n,k)?f(n?4,k?2)?()?()kk?2（c） n?k?1n?k?1?()?()?f(n,k)?f(n,k?2)kk?22.77题 设S(n,k)是第二类stirling数，证明：S(n+1,m)=∑nk=m-1(n k)S(k,m-1)

证明: 当n=2,m=2 左边=s(3,2)=2s(1,1)+s(2,1)=3 右边=c(2,1)s(1,1)+c(2,2)s(2,1)=2+1=3 左边=右边 等式成立 假设当n=nk时等式成立 即 s(nk+1,m) =∑c (nk,m)s(k,m-1)

当n=nk+1时 s(nk+2,m)=ms(nk+1,m)+s(nk+1,m-1)=∑mc(nk,,k)s(k,m-1)+s(nk+1,m-1)=∑c(nk+1)s(k,m-1) 即等式成立 s(nk+1,m)=∑c(n,k)s(k,m-1) 2.78题 求下图中从A点出发到n点的路径数.

1 3 5 n-2 n ……… A 2 4 n-1

解: 设从A点到n点的路径数为an,则得到递推公式为an=an-1+an-2 其中a1=1,a2=2

特征方程为x2-x-1=0 解得特征根为x1,2=

1?51? 故an=A???22?5????n

n

1?5?, + B??????2?将初始值a1=1,a2=2代入上式,解得A=

5?55?55?5,B= 所以,an=101010?1?5?n+

???2???5?5?1?5?n

??

?10??2?

3.1题 某甲参加一种会议，会上有6位朋友，某甲和其中每人在会上各相遇12次，每二人各相遇6次，每三人各相遇3次，每五人各相遇2次，每六人各相遇一次，1人也没有遇见的有5次，问某甲共参加了几次会议

解: 设Ai为甲与第i个朋友相遇的会议 集，i＝1，…，6．则

43

故甲参加的会议数为:28+5=33.

3.2题 求从1到500的整数中被3和5整除但不被7整除的数的个数.

解: 设A3：被3整除的数的集合 A5：被5整除的数的集合 A7：被7整除的数的集合 所以

3.3.题 n个代表参加会议，试证其中至少有2人各自的朋友数相等。

解:每个人的朋友数只能取0，1，…，n－1．但若有人的朋友数为0，即此人和其 他人都不认识，

则其他人的最大取数不超过n－2．故这n个人的朋友数的实际取数只 有n－1种可能．?n??2，

?n?1?所以至少有２人的朋友数相等． 3.4题 试给出下列等式的组合意义.

解: (a)从n个元素中取k个元素的组合，总含有指定的m个元素的组合数为(设这m个元素为a1,a2,…,am,Ai为不含ai的组合（子集），i=1,…,m.

n?mn?m)?()。 k?mn?k?n?l?Ai1???k??mm?n?m??n?l?A??(?1)??i????n?kk(i1,...,il)??(m,l)??i?1??l?1Ai1Ai21?m??n?l?Aij????1?????l?0j?1?k??k?lml

44

3.5题 设有三个7位的二进制数：a1a2a3a4a5a6a7，b1b2b3b4b5b6b7， c1c2c3c4c5c6c7．试证存在 整数i和j，1≤i≤j≤7，使得下列之一必定成立：ai=aj=bi=bj， ai=aj=ci=cj，bi=bj=ci=cj．

证： 显然，每列中必有两数字相同，共有??种模式， 有０或１两种选择．故共有??·2种选择．??·2=6． 现有7列， ?7??2．即必有２列在相同的两行选择相同的数字，即有一矩形，四角的数字相等．

?3??2??3??2??3??2??6?3.6题 在边长为1的正方形内任取5个点试证其中至少有两点，其间距离小于122

证：把１×１正方形分成四个(1/2)×(1/2)的正方形． 如上图.则这５点中必有两点落在同一个小正方形内． 而小正方形内的任两点的距离都小于122．

3.7题 在边长为1的等边三角形内任取5个点试证其中至少有两点，期间距离小于1/2． 证： 把边长为１的三角形分成四个边长为1/2的三角形，如上图：

则这５点中必有两点落在 同一个小三角形中．小三角形中任意两点间的距离都小于1/2． 3.8题 任取11个整数，求证其中至少有两个数它们的差是10的倍数。

证：整数的个位数的可能取值为０，１，…，９．共１０种可能．11个整数中必有 ２个数的个位数相同， 即这两个数之差能被１０整除．

3.9题 把从1到326的326个整数任意分为5个部分，试证其中有一部分至少有一个数是某两个数之和， 或是另一个数的两倍。

证：用反证法。设存在划分 P1∪P2∪P3∪P4∪P5＝[1，326]， Pi中没有数是两数之差． ，则有一Pi中至少有66个数， A＝{ a1 ,…,a66} ，a1＜a2＜???＜a66 ， 以下按书上174页的例题证明可得．

3.10题 A、B、C三种材料用作产品I、II、III的原料，但要求I禁止用B、C作原料，II不能用B作原料， III不允许用A作原料，问有多少种安排方案？（假定每种材料只做一种产品的原料）

解：按题意可得如下的带禁区的棋盘,其中有阴影的表示禁区．

棋盘多项式为：R( )=R( )R( )=(1+x)(1+3x+x2 )=1+4x+4x2 + x 3 故方案数＝3!－4?2!+4 ?1!－1 ?0!＝1 3.11题 n个球放到m个盒子中去，n＜(m/2)(m－1)，试证其中必有两个盒子有相同的球数。

解：设m个盒子的球的个数是a1,…,am， 各不相等，且有0≤a1＜a2＜???＜am．则有 a2≥1、am≥m－1，故

≥1+2+…+m－1＝(m/2)(m－1) ， 与n＜(m/2)(m－1)相矛盾！ 所以必有两个盒子的球数相等．

3.12题 一年级有100名学生参加中文、英语和数学的考试，其中92人通过中文考试，75人通过英语考试，65人通过数学考试；其中65人通过中、英文考试，54人通过中文和数学考试，45人通过英语和数学考试，求通过3门学科考试的学生数。

解：设： 通过中文考试的92人为集合A，通过英语考试的75人为集合B，通过数学考试的65人为集合C

则∣A∩B∣=65，∣A∩C∣=54，∣B∩C∣=45

由∣A∪B∪C∣=∣A∣+∣B∣+∣C∣-∣A∩B∣-∣A∩C∣-∣B∩C∣+∣A∩B∩C∣ 故∣A∩B∩C∣=∣A∪B∪C∣-∣A∣-∣B∣-∣C∣+∣A∩B∣+ ∣A∩C∣+∣B∩C∣

=100-92-75-65+65+54+45 =32 通过3门学科考试的学生数为32。 3.13题 试证(1)|A?B|?|B|?|A?B| (2)|A?B?C|?|C|?|A?B|?|A?B?C|

证明：(1) AB?? AB?B?AB=B AB?? AB?B?AB

B?B?AB=? 所以AB?B?AB成立

A=B A(2)ABC?ABC AB?AB AB?A?B?AB=C?AC?BC?ABC

又因为 由（a）得 原式=C?(A

B)C?C?(AC)(BC)

45

3.14题 N?{1,2,?,1000}，求其中不被5和7除尽，但被3除尽的数的数目。

解：设

A3为被3除尽的集合

A35为被5除尽的集合

A-

7为被7除尽的集合

所以由题意得：

AAA357?A?AA35?AAA357

=??1000??1000??1000??1000??????? =333-66-47+9=229 ?????3??3?5??3?7??3?5?7?3.15题 N?{1,2,?,12}0,求其中被2，3，5，7中m个数除尽的数的数目，m=0，1，2，3，4。求不超过120的素数的数目。

解：(1) m=0时 不被2，3，5，7除尽的数为

AAAA2357=120-+ -

A52?A33?A35?A77?AA2573?AA2235?5AA27

AA2?AA7?AA-AAA57?AAA2377AAA5?AAA3+

AAAA235

=120-（60+40+24+17）+（20+12+8+8+8）-（4+2+1+1）=27

m=0 时

AA2373?120????20 ?2?3??

AA25?120????12 ?2?5??

AA27?120????8 ?2?7??

AA2?120????5 ?3?7??AA57?120????3 ?5?7??M=3 时

AAA3575?120????4 A2??2?3?5?AA3577?120????2 ??2?3?7?

AAA223?120????1 ?2?5?7??AAA3?120????1 ?3?5?7??M=4 时

AAAA57?120????0 ??2?3?5?7?(2) 因为

11?121 ，故不超过120的合数必然是 2，3，5，7的倍数

2而且不超过120的合数的因子不可能超过11 设

A为不超过120的数的倍数集合，i=2，3，5，7

i排除 2，3，5，7这四个数又包含1这个非素数

2，3，5，7本身是素数，故所求不超过120的素数个数应该为 27+4-1=30

3.16题 求正整数n的数目，n除尽

解：N为正整数 设

1040，

402030中的至少一个数。

A1040为被

10除尽

A2030为被

204030除尽

?n? 40?A1040=???10???n?

30?A2030=?

??20??

46

A10??n 4030?A2030????10?20??

3.19 题 {1000，1001，。。。，3000}，求其中是4的倍数但不是100的倍数的数目。

解：设A，B分是4，100的倍数。

?3000?1000??3000?1000?A???500?A?B??20??A?B??500?20?480?????4100????

3．20题 在由a,a,a,b,b,b,c,c,c,组成的排列中，求满足下列条件的排列数，（1）不存在相邻3元素相同； 解：A，B，C分别表示 aaa,bbb,ccc 则：

A?B?C????7!?3!?2A?B?A?C?B?C?5!3!A?B?C?1S?9!9!?3!?35!A?B?C?S??A?B?C???A?B?A?C?B?C??A?B?C??3*?3*?1323!?3!??3!?7!

（2）相邻两元素不相同。

3．21题 求从O（0，0）点到（8，4）点的路径数。已知（2，1）到（4，1）的线段，（3，1）到（3，2）的线段被封锁

解： 设A点坐标（2，1），B点坐标（4，1），C点坐标（3，1），D点坐标（3，2） 令a为从O点到M点经过AC b为从O点到M点经过CB c为从O点到M点经过CD

s?c(12,4)?a?c(3,1)*c(8,3)?168a?b?105 a?c?63

b?c(4,1)*c(7,3)?140c?c(4,1)*c(7,2)?84b?c?0a?b?c?0a?b?c?s?(a?b?c)?(a?b?a?c?b?c)?a?b?c?2713．22题 求满足下列条件 x1+x2+x3=20, 3?x1?9,0?x2?8,7?x3?17的整数解数目.

解：令y1=x1-3,y2=x2,y3=x3-7

???0?z1?6?y1,0?z2?8?y?14 z1?z2?z32,?0z?31?y0

则所求整数解的数目：c(14+3-1,14)=c(16,2)=120

3.24题 求满足下列条件的整数解数目：x1+ x2+ x3+ x4=20 1≤x1≤5,0 ≤x2≤7,4 ≤x3≤8,2≤x4≤6

解：设y1= x1 -1, y2= x2, y3= x3 -4, y4= x4 -2, y1+y2+y3+y4=13 0 ≤y 1≤4, 0 ≤y 2≤7, 0 ≤y 3≤4, 0 ≤y 4≤4,

若不附加上界条件的解根据公式应为 ??13?4?1??16??16?????????560

?13??13??3?对于有上界的问题要作变换 ε1=4-y1, ε2=7-y2, ε3=4-y3, ε4=4-y4, ε1≥0 , ε2≥0 , ε3≥0 , ε4≥0 ,

于是问题变为 ε1+ε2+ε3+ε4=6 整数解的数目 ?

47

?6?4?1??9??9?????????84

?6??6??3?3.25题 证明满足下列条件：x1+ x2+……+ xn=r 0≤xi≤k , i=1,2,……，n 的整数解数目为

?1)?i?n?1i?n??r?(k(?1)?????

ir?1i?0????n 解：S, |S|=???n?r?1??令S中具有x1≥k+1的子集A1，……，xi≥k+1的子集Ai , 问题转化为求| A1∩A2∩…∩An | ??r??n??r?(k?1)i?n?1?(?1)????? i?0?i??r?1?nini?r?n?2k?4??r?n?k?2?????? … | A1∩A2∩…∩An | =? |A1∩A2 |=?r?1 |A1|=?r?1?n??r?ki?1?3.26题 证明满足下列条件：x1+ x2+……+ xn=r 1≤xi≤k , i=1,2,……，n 的整数解数目为?(?1)????

ir?1i?0????证明：令yi= xi-1 则y1+ y2+……+ yn=r-n 0≤yi≤k , i=1,2,……，n

n?n??r?(k?1)i?n?1?i?n??r?ki?1?由上题知?(?1)???代入得整数解数目为(?1)????? ?ir?1ir?1i?0i?0????????ni3.27题 求n对夫妻排成一行，夫妻不相邻的排列数。

解：(1)n个人排成一行方案数为n! N对夫妻排成一行方案数为n!2n 令Ai 第i对夫妻相邻而坐的集合，i=1,2,……，n (2)2n个人排成一行方案数为(2n)!

|Ai|相当于将第i对夫妻作为一个对象排列一行然后换位，故 |A1|=2(2n-1)!

|A1∩A2 |=22(2n-2)! … … |A1∩A2∩…∩An|=2n n!

nn?n?h?n?2??nn

故夫妻不相邻排列数为 N=(2n)!-2??(2n-1)!+ 2?? (2n-2)!- ……+(-1)2 n! =?2??(2n-h)!

h?0?1??2??h?3.28题 设p,q∈N，p是奇数，现在有pq个珠子，着q种颜色，每种颜色有p个珠子。假定相同颜色的珠子无区别。

试分别求满足以下条件的珠子的排列数。（1）同颜色的珠子在一起；（2）同颜色的珠子处于不同的块；（3）同颜色的珠子最多在两个块。

解：同颜色的珠子在一起的排列数 p! 同颜色的珠子处于不同的块的排列数 p!qp

同颜色的珠子最多在两个块的排列数Ai 相当于第i个某色球处于不同块

| A1 |=q(pq)! |A1∩A2 |=q2(pq-1)! … … |A1∩A2∩…∩Ap|=qp(pq-p)!

p?p??p?pp

N= q(pq)!- q?? (pq-1)! +……+(-1)q(qp-p)!=?qp??(pq?i)

i?0?1??i?2

3.29题 将r个相同的球放进n个有标志的盒子里，无一空盒，求方案数。

解：先拿出n个球在每个盒子里放一个球，再将剩下的r-n个球无限制地放入n个盒子中。

根据定理1.3，r-n个球无限制地放到n个盒子中共有C(n+r-n-1,r-n)=C(r-1,r-n)=C(r-1,n-1)种放法。 3.30题 试证

i?n??n?r?i?1??r?1?(?1)???=?，r，n∈N，r>n ????i?????ri?0?????n?1?n?1解：设共有r-1个不同的红球和n个不同的白球，从中取出n-1个球.

等式左边每个累加项（不考虑符号）可化为：C(n,i)C(n+r-1-i,n-1-i)表示从这些球中取i个白球和n-1-i个红球， 表示至少取i个白球的组合数，即β(i)。

等式右边表示只从r-1个红球中取出n-1个球的组合数，表示恰好取0个白球的组合数，即α(0)。 根据广义容斥定理α(0)= β(0)-β(1)+β(2)-…+(-1)n-1β(n-1)。原式证毕。

48

?n?m?mi(?1)?3.32题 m,r,,n∈N,满足m≤r≤n,试证?=??n?r???i?0?m???i?????n?i???r?? ??

?n?m??n?m?证明：从n个元素中取k个的组合，总含有制定的m个元素的组合数为??k?m??=??n?k??，

????设这m个元素为a1,a2,.....am,Ak为不含ak的组合（子集），i=1，…,m.

?n?i?

AK1?AK2?...?AKi=??r??

??

3.33 题 求证a)D(n,r,k)?rkim?n?m?m?n?mii?(?1)?AKj??n?r??=?Ai=??r??+?(?1)·

(k1,k2,..ki)??(m,i)j?1??i?1??i?1?r???k?? ????D(n?k,r?k,0)

r?ki?0ir?ki证明：右边=

?(?1)??(n?k?i)!(n?k?r?k)!?(?1)?(n?r)!ii?0??rk??r?k0r?k?0r?k?0i?(n?0?i)!

=

?rk1r?k(?1)i?*(n?r)!?i?0??(n?k?i)!=左边

r?kic) D(n,n,k)?n*D(n?1,n?1,k)?(?1)n?k??

nk证明：

n?kn!(n?k)!i(?1)(n?k?i)!?(n?k)!k!i?0(n?k?i)!i!n?k?1n!(n?k?1)!n!in?k?(?1)(n?k?i?1)!?(?1)?(n?k?1)!k!i?0(n?k?i?1)!i!(n?k)!k!

n!n?kn!n?k?1n!i1i1n?k (?1)?(?1)?(?1)??k!i?0i!k!i?0i!(n?k)!k!n!n?kn!n?k?11n!i1 得证。 (?1)?(?1)i?(?1)n?k??k!i?0i!k!i?0i!(n?k)!k!d)

??D(n,r,k)???D(n?t,r?t,k?t)

ktrt????证明：

ktrk?(?1)??(n?r)!ir?kii?0r?k????(n?k?i)!?rtr?tk?t?(?1)??(n?k?i)!

(n?r)!ir?kii?0r?kk!r!(k?t)!t!(r?k)!k!r?k(?1)i?(n?r)!i?0r!(k?t)!t!(r?k)!r?k(?1)i?(n?r)!i?0

r!(r?t)!(r?t)!t!(r?k)!(k?t)!r?kr?k(?1)i?i?(n?k?i)!??(n?r)!i?0??(n?k?i)!

r?kir!t!(r?k)!(k?t)!r?kr?k?i?(n?k?i)!?(n?r)!?(?1)ii?0??(n?k?i)! 反过程可证。

r?ki49

e) D(n,r,k)?r*D(n?1,r?1,k)?D(n?1,r,k)

证明：

?(?1)??(n?k?i)!(n?r)!ir?kii?0??rkr?k?r*??(?1)?(n?r)!ii?0r?1k?r?k?1r?k?1i?(n?k?i?1)!?(n?r?1)!?(?1)??(n?k?i?1)!ir?kii?0??rk

r?kr!(r?k)!k!r?k(?1)i?ir?k?(n?k?i)!??(n?r)!i?0(r?1)!r!r*(r?1?k)!k!r?k?1(r?k)!k!r?kir?k?1(?1)?i(n?k?i?1)!?(?1)i???(n?r)!(n?r?1)!i?0i?0r?ki

??(n?k?i?1)!r?kir?k(n?k?i)!r?k?1i(n?k?i?1)!i(n?k?i?1)!(?1)?(?1)?(n?r)(?1) ???(r?k?i)!i!(r?k?i?1)!i!(r?k?i)!i!i?0i?0i?0当i=0时，各项左右相等，对应当n=r-k-1时候，左右也相等。剩余左右当i=r-k时候也相等，得证。

3.35题 令Dn(k)=D(n,n,k), 试证 (a) Dn(k)=????Dn-k

?n??k?

?n??ii?k??n?k?n?k??n?n?k?n?k???i ????????????证明：Dn?k??D?n,n,k??(?1)n?k?i!??1n?k?i!???i??k??i?(n?n)!i?0????i?0??Dn?k?n?k?n?k????0??(?1)??i?0iin?k?n?k??n?k?????????n?k?i!??1??i??i??n?k?i?!

i?0?????n??Dn?k????k??Dn?k

??(b) ??1??D1???2??D2?????n??Dn?n!

??????证明：上面等式可变换为：???n??n??n??n??n??n?????D?D????1?n?2?2?0??Dn?n! n?1??????nn考虑n元素的集合S={1,2,…,n}，设T为S的排列全体，则|T|=n!。 设Ai是S中恰有i个在其自然位置的n-排列全体，则Ai?Aj??n?n??n?而，|Ai|???i??Dn?i 因此，n!????i??Dn?i

i?0????T??Ai 所以，|T|??|Ai|

i?0i?0

50

本文来源：https://www.bwwdw.com/article/cgyo.html