《组合数学》测试题含答案

测 试 题

——组合数学

一、选择题

1. 把101本书分给10名学生，则下列说法正确的是（）

A.有一名学生分得11本书 B.至少有一名学生分得11本书 C.至多有一名学生分得11本书 D.有一名学生分得至少11本书

2. 8人排队上车，其中A，B两人之间恰好有4人，则不同的排列方法是（）

A.3?6! B.4?6! C. 6?6! D. 8?6!

3. 10名嘉宾和4名领导站成一排参加剪彩，其中领导不能相邻，则站位方法总数为（）

!?P?11,4? B. 10!?P?9,4? A.10C. 10!?P?10,4? D. 14!?3!

4. 把10个人分成两组，每组5人，共有多少种方法（） A.???10??10??10?????? B. ??????5??5??5??9??9??9?C.??4?????4?? ?4?? D.???????5. 设x,y均为正整数且x?y?20，则这样的有序数对?x,y?共有（）个 A.190 B.200 C.210 D.220

6. 仅由数字1，2，3组成的七位数中，相邻数字均不相同的七位数的个数是（）

A.128 B.252 C.343 D.192

7. 百位数字不是1且各位数字互异的三位数的个数为（）

A.576 B.504 C.720 D.336 8. 设n为正整数，则

?n????2k??等于（） k?0??nnn?1 C. n?2 D. n?2

A.2 B. 2nn?1?n?k9. 设n为正整数，则???1???k??3的值是（）

k?0??nkA.2 B. ?2 C. ??2? D.0

nnn?k?10. 设n为正整数，则当n?2时，???k?2??=()

k?2??nA.????? B. ?

?n??3??n?1?

?? C. 2??

632?n?1?

??3?? D. ???n???2???2 ??11. ?2x1?3x2?x3?中x1x2x3的系数是（） A.1440 B.-1440 C.0 D.1

12. 在1和106之间只由数字1，2或3构成的整数个数为（）

A.

3?13?33?13?3 B. C. D.

222266

7713. 在1和300之间的整数中能被3或5整除的整数共有（）个

A.100 B.120 C.140 D.160

,f?8??34，则f?10??（） 14. 已知?f?n??n?o是Fibonacci数列且f?7??21 A.89 B.110 C.144 D.288 15. 递推关系an?3an?1?4an?3的特征方程是（） A.x2?3x?4?0 B. x2?3x?4?0 C. x3?3x2?4?0 D. x3?3x2?4?0

16. 已知an?2?3?2n?n?0,1,2,???，则当n?2时，an?（） A.3an?1?2an?2 B. 3an?1?2an?2 C.?3an?1?2an?2 D. ?3an?1?2an?2

?an?2an?1?2n?n?1?17. 递推关系?的解为（）

a?3?0 A.an?n?2n?3

B. an??n?1??2n?2

C. an??n?2??2n?1 D. an??n?3??2n

18. 设an?5?2n?n?0,1,2,???，则数列?an?n?0的常生成函数是（） A.

55 B. 21?2x?1?2x?2C.5?1?2x? D. 5?1?2x?

19. 把15个相同的足球分给4个人，使得每人至少分得3个足球，不同的分法共有（）种 A.45 B.36 C.28 D.20 20. 多重集S??2?a,4?b?的5-排列数为（）

A.5 B.10 C.15 D.20

21. 部分数为3且没有等于1的部分的15-分拆的个数为（） A.10 B.11 C.12 D.13

22. 设n,k都是正整数，以Pk?n?表示部分数为k的n-分拆的个数，则P6?11?的值是（） A.6 B.7 C.8 D.9

23. 设A，B，C是实数且对任意正整数n都有n3?A???3???B???2???C???1??，则B的值

??????是（）

A.9 B.8 C.7 D.6

24. 不定方程x1?2x2?2x3?17的正整数解的个数是（） A.26 B.28 C.30 D.32

25. 已知数列?an?n?0的指数生成函数是E?t??et?1?e5t，则该数列的通项公式是（） A.an?7n?6n?5n B. an?7n?6n?5n C. an?7n?2?6n?5n D. an?7n?2?6n?5n 二、填空题

1. 在1和2000之间能被6整除但不能被15整除的正整数共有_________个

2. 用红、黄、蓝、黑4种颜色去图1?n棋盘，每个方格涂一种颜色，则使得被涂成红色

的方格数是奇数的涂色方法共有_______种 3. 已知递归推关系an?3an?1?4an?2?12an?3?n?3?的一个特征根为2，则其通解为

___________

4. 把n?n?3?个人分到3个不同的房间，每个房间至少1人的分法数为__________

?n??n??n???2?5. 棋盘

??????的车多项式为___________

6. 由5个字母a,b,c,d,e作成的6次齐次式最多可以有_________个不同类的项。

?n?7. ???1?k??k??=_____________________ k?0??n2k8. 求由2个0，3个1和3个2作成的八位数的个数______________

9.含3个变元x, y, z的一个对称多项式包含9个项，其中4项包含x,2项包含xyz,1项是常数项，则包含xy的项数为____________

10．已知f?n?是n的3次多项式且f?0??1,f?1??1,f?2??3,f?3??19,则

f?n??____________

11. 已g?n,k?表示把n元集划分成k个元素个数均不小于2的子集的不同方法数， 则

g?n,2?=___________

12.部分数为3且没有等于k的部分的n-分拆数________________

13. 把24颗糖分成5堆，每堆至少有3颗糖，则有___________种分法

三、计算题

1．在1000至9999之间有多少个数字不同的奇数？

2、以3种不同的长度，8种不同的颜色和4种不同的直径生产粉笔，试问总共有多少种不同种类的粉笔？

3、至多使用4位数字可以写成多少个2进制数！（2进制数只能用符号0或1） 4、由字母表L={a,b,c,d,e}中字母组成的不同字母且长度为4的字符串有多少个？如果允许字母重复出现，则由L中字母组成的长度为3的字符串有多少个？ 5、从{1，2，3??9}中选取不同的数字且使5和6不相邻的7位数有多少？ 6、已知平面上任3点不共线的25个点，它们能确定多少条直线？能确定多少个三角形？

7、计算数字为1，2，3，4，5且满足以下两个性质的4位数的个数： (a)数字全不相同； (b)数为偶数

8、正整数7715785有多少个不同的正因子（1除外）？ 9、50！中有多少个0在结尾处？

10、比5400大并且只有下列性质的数有多少？ (a)数字全不相同； (b)不出现数

字2和7

11. 将m=3761写成阶乘和的形式。

12. 根据序数生成的排列(p)=(3214)，其序号是多少？

13. 如果用序数法对5个文字排列编号，则序号为117的排列是多少？ 14. 设中介数序列为（120），向它所对应的4个文字的全排列是什么？ 15. 按字典序给出所有3个文字的全排列。

16. 按递归生成算法，依次写出所有的4个文字的全排列。 17. 根据邻位互换生成算法，4个文字的排列4231的下一个排列是什不同的方案? 18. 有5件不同的工作任务，由4个人去完成它们，每件工作只能由一个人完成，问有多少种方式完成所有这5件工作？

19. 有纪念章4枚，纪念册6本，分送给十位同学，问有多少种分法？如限制每人得一件物品，则又有多少种分法？

20．写出按次序产生的所有从1，2，3，4，5，6中任取2个的组合。

21．给定一个n边形，能画出多少个三角形使得三角形的顶点为n边形的顶点，

三角形的边为n边形的对角线（不是边）？ 22．试问（x+y+z）的6次方中有多少不同的项？

23. 如果没有两个相邻的数在同一个集合里，由{1，2，?20}中的数可形成3个

数的集合有多少？

24. 试列出重集{2·a,1·b,3·c}的所有3组合和4组合。 25. 设{Fn}为fibonna序列，求出使Fn = n的所有的n。

26. 试求从1到1000中,不能被4,5或6整除的个数? 27. 计算12+22+??+n2

28. 设某地的街道把城市分割成矩形方格，每个方格叫它块，某甲从家里出发上班，向东要走过7块，向北要走过5块，问某甲上班的路经有多少条？ 29.设n=253273114,试求能除尽数n的正整数的数目。 30.求（1+x4+x8）10 中x20项的系数。

31.试给出3个文字的对称群S3中的所有元素，并说出各个元素的格式。 32.有一BIBD，已知b=14,k=3,λ=2,求v和r。 33.将39写成∑ai i!(0≤ai≤i)的形式。

34.8个人围坐一圈，问有多少种不同的坐法？ 35.求C?10,1??2C?10,2??3C?10,3?????10C?10,10?

36.试给出两个正交的7阶拉丁方。

37.在3n+1个球中，有n个相同，求从这3n+1个球中选取n个的方案数。 38.用红、黄两种颜色为一个等边三角形的三个顶点着色，问有多少种实质不同的着色方案？

39.在r,s,t,u,v,w,x,y,z的排列中，求y居x和z中间的排列数。 40.求1040和2030的公因数数目。

41.求1到1000中不被5和7整除，但被3整除的数的数目。 42.求14?24?34????n4的和。

43.用母函数法求递推关系an?6an?1?8an?2?0的解，已知a0=0,a1=1。 44.试求由a,b,c这3个文字组成的n位符号串中不出现aa图像的符号串的数目。 45.26个英文小写字母进行排列，要求x和y之间有5个字母的排列数。

46.8个盒子排成一列，5个有标志的球放到盒子里，每个盒子最多放一个球，要求空盒不相邻，问有多少种排列方案？

47.有红、黄、蓝、白球各两个，绿、紫、黑球各3个，从中取出6个球，试问有多少种不同的取法。

48.用b、r、g这三种颜色的5颗珠子镶成的圆环，共有几种不同的方案？ 49.n个完全一样的球放到r（n≥r）个有标志的盒中，无一空盒，试问有多少种方案？ 50.假设某个凸n边形的任意三条对角线不共点，试求这凸n边形的对角线交于多少个点？ 51.求Sn?1?2?3?2?3?4????n?n?1??n?2?从k个不同文字中取n个文字作允许重复的排列，但不允许一个文字连续出现3次，求这样的排列的数目。 52.求下图中从A点出发到n点的路径数。

1 3 5 7 ??n 2 4 6 8 n-1

53.n条直线将平面分成多少个区域？假设无三线共点，且两两相交。 54.四位十进制数a b c d，试求满足a+b+c+d=31的数的数目。

55.两名教师分别对6名学生面试，每位教师各负责一门课，每名学生面试时间固定，6名学生面试时间定于下周一的第1节至第6节课，两门课的面试分别在901和902两个教室进行。试问共有多少种面试的顺序。

56. 对正六角形的6个顶点用5种颜色进行染色，试问有多少种不同的方案？旋转或翻转使之重合的视为相同的方案。

58. 生成矩阵

?1??0 G??0??0?010000100001111001111??1? 0??1??试求相应的校验矩阵H。

59.由m个0，n个1组成的n+m位符号串，其中n≤m+1,试求不存在两个1相邻的符号串的数目。

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

x1?x2?x3?40,6?x1?15,5?x2?20,10?x3?25的整数解数目。 63.求不超过120的素数的数目。

64.试说明A4群中各置换的不同格式及其个数。 65.已知生矩阵

?1??0 G??0??0?010000100001011110111??1? 0??1?? 求下列信息的码字？

（a） 1110 (b) 1000 (c) 0001 (d) 1101

66.有n个不同的整数，从中取出两组来，要求第1组的最小数大于另一组的最大数，有多少种取法？

67.设某组织有26名成员，要选一名主席，一名会计，一名秘书，且规定一人不得担任一个以上职务，问有多少种选法？ 68.从整数1，2，?，100中选取两个数。（1）使得它们的差等于7；（2）使得它们的差小于或等于7，各有多少种选取方式？ 69.有n个相同的红球和m个相同的白球；那么这m+n个球有多少种不同的排列方式？ 70.一个工厂里已装配了30辆汽车，可供选择的设备是收音机、空调和白圈轮胎。这30辆汽车中，15辆有收音机，8辆有空调，6辆是白圈轮胎，而这三种设备都具有的汽车有3辆，试求这三种设备都不具备的汽车至少有多少辆？ 71.数1，2，?，9的全排列中，求偶数在原来位置上，其余都不在原来位置上的错排数目。

72.在等于300的自然数中：（1）有多少个不能被3，5和7整除的数？（2）有多少个能被3整除，但不能被5和7整除的数？ 73.求下列数值函数的生成函数：

（1）ar?cr(r=0，1，2，?)，其中C为实数。 (2) ar???1?r?（r=0,1,2,?）,其中a为正整数。 ???，74.求下列生成函数的数值函数：其中A?x??x2?5?6x?x2?

nn??2??n. 75.用生成函数求下式之和： 1??12????n?n??q??r?76.一个人上楼梯，可以一步上一个台阶，也可以一步上两个台阶，令an表示有n 个台阶时的上楼方式数，写出an的递推关系，并求解之。 77.利用特征方程法解递推关系： ??an?an?1?9an?2?9an?3,n?3

a?0,a?1,a?2012?n78.求下列递推关系的特解 an?3an?1?2an?2?2

79.1)求小于10000的含1的正整数的个数 2)求小于10000的含0的正整数的个数。

80．在100名选手之间进行淘汰赛(即一场的比赛结果，失败者退出比赛),最后产生一名冠军，问要举行几场比赛？ 81. 计算[1,n]的无重不相邻组合C?n,r?的计数问题

82. 某保密装置须同时使用若干把不同的钥匙才能打开。现有７人，每人持若干

钥匙。须４人到场，所备钥匙才能开锁。问①至少有多少把不同的钥匙？②每人至少持几把钥匙？

83. 凸10边形的任意三个对角线不共点，试求这凸10边形的对角线交于多少

点？又把所有对角线分割成多少段？ 84.在5个0，4个1组成的字符串中，出现01或10的总次数为4的，有多少个? 85. 整数n拆分成1，2，3，?，m的和，并允许重复，求其母函数。

86.某甲参加一种会议，会上有6位朋友，某甲和其中每人在会上各相遇12次， 每二人各相遇6次，每三人各相遇3次，每五人各相遇2次，每六人各相遇1次，1人也没有遇见的有5次，问某甲共参加了几次会议？ 87. 给出下列等式的组合意义：

l?n?m?m?m??n?l????????1?n?k???l????k??,n?k?m?l?0????（a）?

?m?l?1??m?l??m?l??m?l?l?m?l????????????????????1?m?1??m??m?1??m?2??m?l???????????? (b)

88. 将正整数10写成3个非负整数n1,n2,n3的和，要求n1?3,n2?4,n3?6，有多少种不同的写法？ 89. 计算母函数G?x???1?2x??1?3x?x?的头6项。

290. 红、白、黑三色球各8个，现从中取出9个，要求3种颜色的球都有，问有多少种不同取法？ 91. 求序列c?n,0?,?c?n,1?,c?n,2?,??,??1?nc?n,n?的母函数。 92. 解递归关系an?an?2?0,a0?0,a1?2 93. 求下列表达式中求出a50的值

?x?3??x2?3x?2??a0?a1x????a50x50??

94.设ar是掷两个骰子时和为r的方式数，其中第一个骰子的点数为偶数，第二 个骰子的点数为奇数，求序列?a0,a1,a2???的母函数。 95. 有多少棵有n个顶点的二叉数？ 96．求下式之和

1?c?n,1?/2?c?n,2?/3??????1?nc?n,n?/?n?1? 97．展开多项式?x1?x2?x3?

498.六个引擎分列两排，要求引擎的点火的次序两排交错开来，试求从一特定引擎开始点火有多少种方案。

99.试求n个完全一样的骰子掷出多少种不同的方案？ 100. 写出全部部分数最小的19-完备分拆

kn?????fn?2??101. 已知，求f?n?

n102. 求方程x1?2x2?4x3?17的非负整数解的个数。

四、证明题

1.证明：{1,2,?,n}的全排列的最大逆序数是n(n-1)/2。试确定具有n(n-1)/2个逆序的唯一排列。

2.证nc?n?1,r???r?1?c?n,r?1?．并给出组合意义.

3.n个完全一样的球，放到r个有标志的盒子，n≥r，要求无一空盒，试证其方案数为c?n?1,r?1?.

4. 试证一整数是另一个整数的平方的必要条件是除尽它的数目为奇数． 5. 试证明：c?0,m??c?1,m?????c?n,m??c?n?1,m?1? 6. 证明：(C(n,0))2+(C(n,1))2+?+(C(n,n))2 = C(2n,n) 7. 证明：若F1?F2?1, Fn?Fn?1?Fn?2 (n>2)，则

nnFn???1?5/2?1?5/2??/5?? ??n??n/5??????????其中α=（1+√5）/2，β=（1-√5）/2

8. N个代表参加会议，试证其中至少有两个人各自的朋友数相等。 9. 证明：12?22??n2?n?n?1??2n?1?/6 10. 证明：?2n?!/2n是整数。

11. 证明：在边长为1的等边三角形内任取5点，试证至少有两点的距离小于1/2。

?112.证明： ??1?1??Fn?1?????F0??nnFn?? Fn?1?? 其中Fn定义为：F1?F2?1，Fn?Fn?1?Fn?2

13.任取11个整数，求证其中至少有两个数它们的差是10的倍数。

14.在边长为1的正方形内任取5点，试证其中至少有两点，其间距离小于2/2。 15.若H是群G的子群，试证：|xH|=K, 其中K＝|H|，x∈G。

16.二维空间的点（x,y）的坐标x和y都是整数的点称为格点。任意5个格点的

集合A，试证A中至少存在两个点，它们的中点也是格点。 17.证明：在由字母表{0，1，2}生成的长度为n的字符串中，0出现偶数次的字符串有（3n+1）/2个。 18.试证任意r个相邻的正整数的连乘积（n+1）(n+2)?(n+r)必被r!除尽。 19.证明：c?m,0?c?m,n??c?m,1?c?m?1,n?1?????c?m,n?c?m?n,0??2nc?m,n? 20.证明c?n,1??2c?n,2?????nc?n,n??n2n?1

21. 任取5个整数，试求其中必存在3个数，其和能被3整除。

22. 若H是群G的子群，x和y 是G的元素。试证xH∩yH或为空集，或xH=yH. 23. 令S={1，2，?，n+1},n≥2,T???x,y,z??S,x?z,y?z?

试证：T?12?22?......?n2?C?n?1,2??2C?n?1,3?。

24. 证明：任何K个相继的正整数之积，必是r的倍数，其中r=1，2，?，K。

n?22n2n2n25. 求证：?2n?1?=?n?1??2?n???n?1?。

k26. 使用二项式定理证明????2,试推广到任意实数r，求??nk?r。

nnk?0nkknk?027. 证明A?B?C?A?B?C?A?B?A?C?B?C?A?B?C

28. 证明任何k个相继正整数中，有一个必能被k整除。

29. 证明在小于或等于2n的任意n+1个不同的正整数中，必有两个是互等的。 30. 证任一正整数n可唯一地表成如下形式:31. 对于给定的正整数n,证明当

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

时，C?n,k?是最大值。

32. 证明在由字母表{0,1,2}生成的长度为n的字符串中,0出现偶数次的字符串

有

个；

33. 设有三个7位的二进制数：a1a2a3a4a5a6a7，b1b2b3b4b5b6b7，c1c2c3c4c5c6c7。

试证存在整数i和j，1?i?j?7，使得下列之一必定成立，

ai?aj?bi?bj,ai?aj?ci?cj,bi?bj?ci?cj。

34.证明：在n阶幻方中将每个数码a换成n2?1?a，所得的阵列仍是一个n

阶幻方。（注：所谓幻方是指一个n?n方阵，其中的元素分别是1,2??n2，且每列的元素和均相等）

35.证明：把有n个元素的集合s划分为k个有序集合的个数等于kn

A+3B+3C+D=98 D=50 A+4B+6C+4D+E=354 E=60 A+5B+10C+10D+5E+F=979 F=24

所以 Sn=C(n,1)+15C(n,2)+50C(n,3)+60C(n,4)+24C(n,5)

2

=(n(n+1)(2n+1)(3n+3n-1))/30

2

43．解：特征函数为x-6x+8=0,x1=2,x2=4,所以可设

nn

an=A?2+B?4,于是 a0=0=A+B 解得 A=-1/2 a1=1=2A+4B B=1/2 nn

即an=(4-2)/2

44．解：设an为n位符号串中不出现aa图像的符号串的个数，

则an=2an-1+2an-2,即 an－2an-1－2an-2＝０，a1=3,a2=8，由此知 a0=1。

2

特征方程为x-2x-2=0, x1=1+√3 , x2=1-√3 ，可设

nn

an=A(1+√3)+B(1-√3),于是有 a0 = 1 =Ａ＋Ｂ

a1 = 3 = (1+√3)A+ (1-√3)B

解此方程组得 Ａ=(３＋2√3)/6

B=(３-2√3)/6

nn

an=[(３＋2√3)(1+√3)+(３-2√3)(1-√3)]/6 45．解：M=2?20! ?5! ?C(24,5)=40?24!

46. 解：如图_0_0_0_0_0_ ,3个空盒可插在两个球之间,共有C(6,3)=20种方案,5个有标志

的球共有5!种排序,所以总计有M=20?5!=2400种排列方案。

242336

47. 解：母函数为G(x)= (1+x+x)(1+x+x+x),其中x的系数为

M=1?10+4?12+10?12+16?10+19?6+16?3+10?1=510,因为

2345678

G(x)= (1+4x+10x+16x+19x+16x+10x+4x+x)×

48. 解：运动群G={(1)(2)(3)(4)(5),(1 2 3 4 5),(1 3 5 2 4),(1 4 2 5 3), (1 5 4 3 2 ), (1)(25)(34), (2)(13)(45), (3)(24)(15), (4)(35)(12), (5)(14)(23)}={ p1,p2,p3,p4,p5,p6,p7,p8,p9,p10}

c( p1)=5, c(p2)=c(p3)= c(p4)=c(p5)=1, c(p6)=c(p7)= c(p8)= c(p9)= c(p10)=3, m=3,

c(p1)c(p2)c(p3)c(p10)51

|G|=10,据P?lya定理,M=(1/|G|)?(m+ m+ m+。。。+ m)=(1/10)（3+4?3+53

?3）

=(1/10)（243+12+45）=30。 49．Ｃ（ｎ－１，ｒ－１）

将ｎ个球排成一行，两球之间有一间隔，共有ｎ－１个间隔。在此ｎ－１个间隔中任取ｒ－１个，将ｎ个球分成ｒ段，将第ｉ段的球（其中至少有１球）放入第ｉ个盒子，所以共有Ｃ（ｎ－１，ｒ－１）种方案。 50. Ｃ（ｎ，４）

凸ｎ边形有ｎ个顶点，任取其中４个顶点可以组成一个凸４边形，该４边形的两条对角线有一个交点，所以凸ｎ边形的对角线交于Ｃ（ｎ，４）个交点（根据假设，没有３条对角线相交于一点）。 51. Ｓｎ＝ｎ（ｎ＋１）（ｎ＋２）（ｎ＋３）／４

Ｓｎ＝１·２·３＋２·３·４＋．．．＋ｎ（ｎ＋１）（ｎ＋２） ＝３！（１·２·３／３！＋２·３·４／３！＋．．．＋ｎ（ｎ＋１）（ｎ＋２）／３！） ＝３！（Ｃ（３，３）＋Ｃ（４，３）＋．．．＋Ｃ（ｎ＋２，３）） ＝３！（Ｃ（３，０）＋Ｃ（４，１）＋．．．＋Ｃ（ｎ＋２，ｎ－１）） ＝３！Ｃ（ｎ＋３，ｎ－１） ＝３！Ｃ（ｎ＋３，４）

＝ｎ（ｎ＋１）（ｎ＋２）（ｎ＋３）／４ 52. ａｎ＝（ｋ／（２（ｋ－１））＋ｋ／（２·ｓｑｒｔ（（ｋ－１）（ｋ＋３）））·

ｎ

（（ｋ－１＋ｓｑｒｔ（（ｋ－１）（ｋ＋３）））／２） ＋（ｋ／（２（ｋ－１））－ｋ／（２·ｓｑｒｔ（（ｋ－１）（ｋ＋３）））·

ｎ

（（ｋ－１－ｓｑｒｔ（（ｋ－１）（ｋ＋３）））／２）

假设从ｋ（ｋ＞１）个不同文字取出ｎ个（可以重复）作排列，但不允许一个文字连续出现３次的排列所组成的集合为Ａｎ，则所求排列数ａｎ＝｜Ａｎ｜。将Ａｎ中的字符串按最后一个文字可以分成两类：一类是最后一个文字同其前一个文字不相同的那些字符串，共有（ｋ－１）ａｎ－１个（最后一位有ｋ－１种选择，而前ｎ－１位是没有一个文字连续出现３次的字符串），另一类是最后两个文字相同，但与倒数第３个文字不相同的字符串，共有（ｋ－１）ａｎ－２个，所以有递推关系

ａｎ＝（ｋ－１）ａｎ－１＋（ｋ－１）ａｎ－２（

２３

而ａ１＝ｋ，ａ２＝ｋ，ａ３＝ｋ－ｋ＝ｋ（ｋ－１）（ｋ＋１ 递推关系的特征方程为

２

ｘ－（ｋ－１）ｘ－（ｋ－１）＝０ 其根为：

α１＝（ｋ－１＋ｓｑｒｔ（（ｋ－１）（ｋ＋３）））／２ α２＝（ｋ－１－ｓｑｒｔ（（ｋ－１）（ｋ＋３）））／２

ｎｎ

于是知 ａｎ＝Ａ１α１＋Ａ２α２

２

由于ａ１＝ｋ，ａ２＝ｋ，由递推关系知ａ０＝ｋ／（ｋ－１），所以

００

ａ０＝ｋ／（ｋ－１）＝Ａ１α１＋Ａ２α２Ａ＝Ａ１＋Ａ２

１１

ａ１＝ｋ＝Ａ１α１＋Ａ２α２＝Ａ１（ｋ－１＋ｓｑｒｔ（（ｋ－１）（ｋ＋３）））／２ ＋Ａ２（ｋ－１－ｓｑｒｔ（（ｋ－１）（ｋ＋３）））／２ 解得

Ａ１＝（ｋ／（２（ｋ－１））＋ｋ／（２·ｓｑｒｔ（（ｋ－１）（ｋ＋３））） Ａ２＝（ｋ／（２（ｋ－１））－ｋ／（２·ｓｑｒｔ（（ｋ－１）（ｋ＋３））） 所以

ａｎ＝（ｋ／（２（ｋ－１））＋ｋ／（２·ｓｑｒｔ（（ｋ－１）（ｋ＋３）））·

ｎ

（（ｋ－１＋ｓｑｒｔ（（ｋ－１）（ｋ＋３）））／２） ＋（ｋ／（２（ｋ－１））－ｋ／（２·ｓｑｒｔ（（ｋ－１）（ｋ＋３）））·

ｎ

（（ｋ－１－ｓｑｒｔ（（ｋ－１）（ｋ＋３）））／２）

n＋1n＋1

53. f（n）＝（（（１＋√５）／２）－（（１－√５）／２））／√５

假设从A（编号为０）到编号为i的顶点有f（i）条路径，则f（１）＝１，f（２）＝２，当i＞2时，f（i）＝f（i-1）＋f（i－2），由此知f（０）＝f（A）＝１。当i＝n时，f（n）＝f（n-1）＋f（n－2）,即f（n）－f（n-1）－f（n－2）＝０。其特征方程为： 2

x－x－1=0，它的两个根分别为：α１＝（１＋√５）／２，α２＝（１－√５）／２。

ｎｎ

于是知f（n）＝Ａ１α１＋Ａ２α２，根据 f（０）＝１＝A1＋A2

f（１）＝１＝A1（１＋√５）／２＋A2（１－√５）／２， 解得

A1＝（１＋√５）／（２√５），A2＝（１－√５）／（２√５）

所以，

n＋1n＋1

f（n）＝（（（１＋√５）／２）－（（１－√５）／２））／√５＝F（n＋1） 其中F（n）为第n个Fibonacci数。

54. an＝（n＋n＋２）／２

设n条符合条件的直线将平面分成an个区域，那么n－１条直线可将平面分成an－１个区域，而第n条直线与前n-1条直线均相交，有n－１个交点，因此第n条直线被分成n段，而每一段对应一个新增的区域，所以有an＝an－１＋n，即an－an－１＝n。于是

an－１－an－２＝n－１，由此得an－２an－１＋an－２＝１，同样有an－１－２an－２＋an－３＝１，

32

故得an－３an－１＋３an－２－an－３＝０，其特征方程为x－３x＋３x－1＝０，解此方程

2n2

得α＝α１＝α２＝α３＝１，所以an＝（A0＋A1n＋A2n）α＝A0＋A1n＋A2n ，而

a0＝１＝A0 a1＝２＝A0＋A1＋A2

a２＝４＝A0＋２A1＋４A2

解得 A0=1 A1=1/2 A2=1/2

由此知

2

an＝（n＋n＋２）／２

55、56

因为x1＋x2＋x3＋x４＝31,xi≥0（i＝１，２，３，４）的整数解共有C（4+31-1，31）＝C（34，３）＝34·33·32/6＝5984（个）。

再考虑x1＋x2＋x3＋x４＝31,xi≥１0（i＝１，２，３，４）的整数解的个数。令N为全体非负整数解，则｜N｜＝5984。

令Ai(i＝１，２，３，４)为其中xi≥１0的解集合。则｜A1｜即为（x1＋10）＋x2＋x3＋x４＝31，也就是x1＋x2＋x3＋x４＝21的非负整数解的个数。所以，

｜A1｜＝C（４＋21－１，21）＝C（24，3）＝24·23·22/6＝2024。同理可知 ｜A２｜＝｜A３｜＝｜A４｜＝｜A1｜＝2024。类似地，

｜Ai∩Aj｜＝C（4＋11－１,11）＝C（14，3）＝14·13·12/6＝364（１≤i

根据容斥原理，a＋b＋c＋d＝31，０≤a，b，c，d≤９的整数解个数等于 ｜?１∩?２∩?３∩?４｜＝

｜N｜－４｜A１｜＋C（4，2）｜A１∩A２｜－C（4，3）｜A１∩A２∩A３｜＋ ｜A１∩A２∩A３∩A４｜

＝5984－4·2024＋6·364—4·4＋0＝56 56. 190800

假设６个学生参加第１位教师的面试的顺序为１、２、３、４、５、６（即对第１个面试的学生编号１，．．．，对第６个面试的学生编号６），那么，这６个学生参加第２位教师的面试的顺序必定是１、２、３、４、５、６的一个错排。不然，就有至少一个学生要同时参加两为教师的面试。于是面试方案总数为

6!D6＝6!6!（1－1＋1/2!－1/3!＋1/4!－1/5!＋1/6!）＝6!256＝190800 57. 1505

对应于旋转与翻转的运动群的置换为：

６

p1（不动） （1）（2）（3）（4）（5）（6） 格式为（１）

１

p2（逆时针旋转60o） （123456） 格式为（６）

2

p3（逆时针旋转120o） （135）(246） 格式为（3）

2

p4（逆时针旋转180o） （14）（25）（36） 格式为（2）

2

p5（逆时针旋转240o） （153）（264） 格式为（3）

１

p6（逆时针旋转300o） （654321） 格式为（６）

22

p7（沿14轴翻转） （1）（4）（26）（35） 格式为（1）（２） 22

p8（沿25轴翻转） （2）（5）（13）（46） 格式为（1）（２）

22

p9（沿36轴翻转） （3）（6）（15）（24） 格式为（1）（２）

３

p10（沿12边54边中线翻转）（12）（36）（45） 格式为（２）

３

p11（沿23边56边中线翻转）（14）（23）（56） 格式为（２）

３

p12（沿16边34边中线翻转）（16）（25）（34） 格式为（２） 所以，总方案数为

61234

l＝（5＋2·5＋2·5＋4·5＋3·5）/12＝18060/12＝1505 58．

3

?1110100???H??0111010?

?1101001???3?7因为

?1??0G??0??0?而

010000100001111001111??1???I3|A4?3? 0??1??4?7?1110???AT??0111?

?1101???3?4H??AT|I3?3?7

59. Ｃ（m＋１，ｎ）

将ｍ个０排成一行，两个０之间有一间隔，共有ｍ＋１（≥ｎ）个间隔（包括头尾处的间隔）。在此ｍ＋１个间隔中任取ｎ个插入１，则所得符号串满足要求，所以共有 Ｃ（ｍ＋１，ｎ）个这样的符号串。 60. （ｎ－１）！ｎ！，（ｎ－１）！ｎ！／（ｎ－ｍ）！

先让ｎ个男人围坐一圈，共有（ｎ－１）！种坐法。对应于每一种坐法，有n个间隔，将n个女人排成一行插入这n个间隔中，有n!种方案，所以共有（n—1）!n!种不同的坐法。

若只有m（m

ｎn+1n+1

61．ａｎ＝4-√3（2+√3）/6+√3（2-√3）/6

设长度为n的由A、B、C、D组成的允许重复的排列中AB至少出现一次的排列所组成的集合为Sn,又设ａｎ＝｜Sｎ｜。而AB一次也不出现的排列所组成的集合为Bn,又设bｎ＝ ｜Bｎ｜。可将Sｎ中的所有排列按AB出现的位置分为两类：一类是在前n-1位中均未出现AB，它仅出现在最末两位，则这种排列共有bn-2个。另一类是在前n-1位中已出

现AB,而最后一位可以是A、B、C、D中的任一个，所以这类排列共有4an-1个，于是知

nn-2n-2

ａｎ＝4an-1 +bn-2，而ａｎ+bn=4，即aｎ-2+bn-2=4，也就是bn-2=4 -aｎ-2，

n-2n-2n-2

由此知ａｎ＝4an-1 +4 -aｎ-2，即ａｎ-4an-1 +aｎ-2=4，可推知4(ａｎ-1-4an-2 +aｎ-3)=4

32

于是得ａｎ-8an-1 +17aｎ-2-4an-3=0，其特征方程为x-8x+17x-4=0,解此方程得

nnn

α１＝4，α２＝2+√3，α３＝2-√3，所以可设ａｎ＝A1α１+A2α２+A3α３，已知ａ1＝0，a2 =1，由此推知a0=0，所以有 a0=0= A1+A2+A3

a1=0= 4A1+（2+√3）A2+（2-√3）A3 a2=1= 16A1+（7+4√3）A2+（7-4√3）A3 化简得 A1+A2+A3=0

2A1+√3A2-√3A3=0 9A1+4√3A2-4√3A3=0 解得 A1=1

A2=-（3+2√3）/6 A3=-（3-2√3）/6 所以

ｎnn

ａｎ=4-（3+2√3）（2+√3）/6-（3-2√3）（2-√3）/6

ｎn+1n+1

=4-√3（2+√3）/6+√3（2-√3）/6

62．135

令y1+6=x1，y2+5=x2，y3+10=x3，则0≤y1≤9，0≤y2≤15，0≤y3≤15，于是有 y1+6+y2+5+y3+10=40，即y1+y2+y3=19，0≤y1≤9，0≤y2≤15，0≤y3≤15，因为

y1+y2+y3=19的非负整数解的个数为C（3+19-1，19）=C（21，2）=21·20/2=210。 令A1是y1+y2+y3=19当y1≥10时的非负整数解集合，则| A1|=C（3+9-1，9）=C（11，2） =11·10/2=55，

令A2是y1+y2+y3=19当y2≥16时的非负整数解集合，则| A2|=C（3+3-1，3）=C（5，2） =5·4/2=10，

令A3是y1+y2+y3=19当y3≥16时的非负整数解集合，则| A3|=C（3+3-1，9）=C（5，2） =5·4/2=10，

而且| A1 ∩A2|=| A2 ∩A3|=| A1 ∩A3|=0，| A1 ∩A2 ∩A3|=0，根据容斥原理可知，符合条件的解的个数为

｜?１∩?２∩?３｜=210-（55+10+10）=210-75=135 63．30

设S={1，2，3，?，120}，若n∈S且n为合数，即n=n1·n2，则因为11·11=121>120，所以n1或n2中必有一数∈{2，3，5，7}。

设A1表示S中能被2整除的数，则| A1|=int（120/2）=60（int（x）表示不超过x的最大整数），

设A2表示S中能被3整除的数，则| A2|=int（120/3）=40， 设A3表示S中能被5整除的数，则| A3|=int（120/5）=24， 设A4表示S中能被7整除的数，则| A4|=int（120/7）=17， 而且，

| A1 ∩A2|=20，| A1 ∩A3|=12，| A1 ∩A4|=8， | A2 ∩A3|=8，| A2 ∩A4|=5，| A3 ∩A4|=3，

| A1 ∩A2 ∩A3|=4，| A1 ∩A2 ∩A4|=2，| A1 ∩A3 ∩A4|=1，| A2 ∩A3 ∩A4|=1，

| A1 ∩A2 ∩A3 ∩A4|=0，

所以，根据容斥原理知，S中既不是2、3、5的倍数，也不是7的倍数的个数共有 120-（60+40+24+17）+（20+12+8+8+5+3）-（4+2+1+1）+0=176-149=27

但是，这27个数中包含了1，它不是素数，却没有包含2、3、5、7，所以，1至120之间的素数共有27-1+4=30个。 64．因为A4={（1）（2）（3）（4），（123），（124），（132），（134），（142），（143），（234）， （243），（12）（34），（13）（24），（14）（23）}，它共有12个置换，其中

4

格式为（1）的有1个：（1）（2）（3）（4），

11

格式为（1）（3）的有8个：（123），（124），（132），（134），（142），（143），（234），（243），

2

格式为（2）的有3个：（12）（34），（13）（24），（14）（23） 65． (a) w1=(1111)G=(1111111) (b) w2=(1000)G=(1000011)

(c) w3=(0001)G=(0001111) (d) w4=(1101)G=(1101001)

n-1

66．（n-2）2+1

从n个不相同的数a1，a2，. . . ，an中取出r（r=2，3，. . . ，n）个,将这r个数从小到大排序：ai1≤ai2≤. . . ≤air。将这r个数分成前后两部分，使每一部分非空，共有r-1种分法。前面部分形成第2组，后面部分形成第1组，则第1组中的最小数大于第2组中的最大数。所以满足条件的取法共有

nnn

（r-1）= r=2∑rC（n，r）- r=2∑C（n，r） r=2∑C（n，r）nn

=（ r=1∑rC（n，r）-C（n，1））-（r=0∑C（n，r）- C（n，1）- C（n，0））

n-1nn-1

=（n2-n）-（2-n-1）=（n-2）2+1

67. 解 根据题设，无论选哪一名，有26种可能结果；余下选一名只有25种可能结果；最后选一名就只有24种可能结果。由于同时选出三名，所以由积的法则知，共有26×25×24=15600种选法。

68. 解 （1）这100个数的前7个数，任选取两个数的差不可能等于7，只有100－7=93种

选取方式，才能使这100个数两数之差等于7。

（2）同理，选取两数之差等于6的有100－6=94种选取方式；等于5的有100－5=95；?，等于1的有100－1=99种。以上两数之差均小于7。故两数的差小于或等于7的选取方式，根据和的法则，共有（94+95+96+97+98+99）+93=672种选取方式。 69. 解 这是一个多重集S=｛n·红球；m·白球｝的重复排列问题。S的一个排列就是它的

m+n个元素的一个全排列，因为S中有n个红球，在排列时要占据n个位置，这些位置

m的选法是Cnm?n种，接下去，在剩下的（n+m）－n=m个位置选择m个位置的选法是 Cm,

由积运算法则，S的排列数为N=CnCmm?n·m=n!?m!n!?m!?m?n?! ·1=?m?n?!,以下化为较简单形式：

n!m!m!n!?m?n?!=?m?n??m?n?1???n?m??n?1??!

= = 这即为所求排列方式数。

?n?m??n?m?1???m?1?!

n!?m!n!?n?m??n?m?1???m?1?

70. 解 设分别具备这三种设备的汽车依次为A1，A2，A3，由题设A1?15，A2?8，A3?6， A1?A2?A3?3?A1A2?A1A3?A2A3?3,于是这三种设备都不具备的汽车，由容斥原理

2知为A1?A2?A3?A1?A2?A3?30?A1?A2?A3

=30???A1?A2?A3???A1?A2?A1?A3?A2?A3??A1?A2?A3? =30???15?8?6???3?3?3??3??7

71. 解 实际上是求奇数1，3，5，7，9这5个数的移位排列数目D（n），由于n=5,所以：

D（5）=5!??1???11111?????? 1!2!3!4!5!??1111?? =120??1?1?????

2624120?? =120??60?20?5?1?120?44

?300?72. 解 设A1，A2，A3分别为能被3，5，7整除的集合，则A1????100， 3???300??300??300??300? A2??，；，?60A??42A?A??20A?A?31213??7??3?5??3?7??14， 5?????????300??300? A2?A3??；?8A?A?A?123??3?5?7??2。 ?5?7??? （1）由容斥原理2知，不能被3，5，7整除的数的个数为：

N1?A1?A2?A3?A1?A2?A3

=300???A1?A2?A3???A1?A2?A1?A3?A2?A3??A1?A2?A3? =300???100?60?42???20?14?8??2??138 （2）能被3整除但不能被5和7整除的数的个数为： N2?A1?A1?A2?A1?A3?A1?A2?A3 =100?20?14?2?68

73. 解 (1) ?a0?c0?1，a1?c，c2?c2，?，ar?cr，?。 ?F?x??a0?a1x?a2x2???arxr?? =1?cx?c2x2???crxr??

1 = ，其中cx＜1

1?cx(2)

?a0???,aa01????,a???,?,aa12a2r?a????1?r??r??,???

?F?x??a0?a1x?a2x2???arxr?? =

?????x???xa0a1a22?a?r?????1?r??r??x??

?? =?74.

?r?0??xart??1?x?a

解A?x??1??6x?5??x?5??x?1??1??1?5?411?x5?11?41?x25111???45?x41?x23?15?x?1??1??1???1???x???x??????1?x?x2?x3??

4??5???5?5??4??1?2?11?1????x????44?5??44?521?4?3?1x???x???3?44?5????1?5?1252?1353?14??x?2x?3x???4?555?数值函数的通项为ar?5r?24?5r?2ni?0,r?3,而当r?2时ar?0

i75. 解 生成函数F?x???F,?x???n1nnii?1??xni??1?x?n

n?1???ix?n?1?x?.即 1????2???x?3???x???n???xi?0n2n32nnn?1?n?1?x?n?1

当令x?1时又为1?n1n2???2??????n????n?2nnn?176. 解 令上到第n个台阶的方式数为an，可心分成两类：一类是从第n－１阶台阶迈一步

上去的，共有an?1种方式；另一类是从第n－２阶台阶迈两个台阶上去的，有an?2种方式，由于最后一步的上法有一步和二步之分，所以这两类上楼梯方式不同，且an?1与an?2的各自上法都不同，故an＝an?1＋an?2，为得到初始条件，当n=1时，a1=1种显然；

当n=2时，有两种可能方式（一步或二步），故a2=2,这样，可得递推关系： ??an?an?1?an?2,n?2

a?1,a?212? 利用特征方程法：由于为２阶常系数齐次递推关系，所以特征方程x2?x?1?0之特征

根x1?1?51?5不同，于是通解an?A1x1n?A2x2n，代入初始条件得方程组 ,x2?22?A1?A2?a0?1x?22?x15?35?3可求出A1?2?,A2???x2?x1x2?x1 ?A1x1?A2x2?a1?22525

将x1,x2,A1,A2代入an即得77. 解 an?an?1?9an?2?9an?3?0

特征方程x3?x2?9x?9?0特征根x1?1,x2?3,x3??3.

通解为an?A1?1n?A2?3n?A3???3?n

A1?A2?A3?0?? 代入初始条件得方程组?A1?3A2?3A3?1

?A?32A???3?2A?223?11A1??,A2?1,A3??1.3124 利用消元法 得 11n1n故an????3????3?431278. 解 先求对应齐次递推关系特征方程的根。

特征方程x2?3x?2?0有两相异特征根x1?1,x2?2.由于??n??2n中2是特征方程的m?1重根所以设特解为?pi?ni?2n?p0?2n?p1?n?2n代入原递推关系得p0?2n?p1?n?2n?3?m?pi?0??0?2n?1?p1??n?1??2n?1?2?p0?2n?2?p1??n?2??2n?2?2n?比较2n两端系数得p1?2,???

故特解为?p0?2n??2n,?p0为任意数?79. 解

1)小于10000的不含1的正整数可看做4位数, 但0000除外. 故有9×9×9×9－1

＝6560个.含1的有：9999－6560=3439个

2)不含0的1位数有9个，2位数有9个，3位数有9个，4位数有9个 不含0小于10000的正整数有9+9+9+9=(9－9)/(9－1)=7380个 含0小于10000的正整数有9999－7380=2619个

80．是淘汰的选手与比赛(按场计)集一一对应。99场比赛

81. 解法1: 0?010?010?010?010?0 共有n位，其中含有r个1且不可含11。 ①以1结尾：r-1个10与n-1-2(r-1)个0的排列 r-1+[n-1-2(r-1)]=n-r

2

3

4

52

3

4

这样的排列有

②以0结尾：r个10与n-2r个0的排列

r+n-2r=n-r这样的排列有 f(a1a2?ar) = b1b2?br

个,

解法2:任给a1a2?ar∈C'(n,r),a1＜a2＜?＜ar 令f：a1a2?ar→b1b2?br

bi=ai-i+1,i=1,2,?,r.

1≤b1＜b2＜?＜br≤n-r+1,b1b2?br∈C(n-r+1,r) C'(n,r)=C(n-r+1,r)

82. 解:①每３人至少缺１把钥匙，且每３人所缺钥匙不同。故至少共有钥匙。

=35把不同的

②任一人对于其他６人中的每３人，都至少有１把钥匙与之相配才能开锁。故每人至少持

＝20把不同的钥匙。

83. 解：根据题意,每4个点可得到两条对角线,1个对角线交点,从10个顶点任取4个的方案有C(10,4)中,即交于210个点。 根据图论知识，每个对角线交点有4个度，每个顶点去掉与相邻两个顶点的连线还有7个度，可以得到

条边

84. 解：先将5个0排成一列：00000，1若插在两个0中间，“010”，则出现2个“01”或“10”;若插在两端，则出现1个“01”或“10”;要使出现“01”,“10”总次数为4，有两种办法：

(1)把两个1插入0得空当内，剩下的1插入1的前面。

(2)把1个1插入0得空当内，再取两个1分别插入两端，剩下的1插入1的前面。 故总方案数为C(4,2)×2+C(4,1)×3=36.

85. 若整数n拆分成1，2，3，?，m的和，并允许重复，其母函数为：

86.

??6??6??6??6??6??6?Ai?12??1???6??2???4??3???3??4???2??5?????6?????????????? ?28 故甲参加的会议次数为：28+5=33 87. 解：

(a) 从n个元素中取k个元的组合，总含有指定的m个元的组合数为。设这m个元为

a1,a2,??，am，Ai为不含ai的组合（子集），I=1,??,m。

格点(x1, y1)和(x２, y２)的中点M的坐标为（Mx ，My)，其中Mx＝ (x２－x1)/2，My＝(y２－y1)/2，因为x１和x２均为偶数，y1和y2均为奇数，所以Mx和My均为整数，也就是说点M是格点。

17. 证明：假设符合条件的字符串集合为A，其中的字符串个数为an。设由0、1、2组

成的长度为n的字符串中０出现奇数次的字符串个数为bn，那么，根据字符串最后一位为０或１或２将A中字符串分类，若最后一位是１或２，则共有２an－1个，若最后一位是０，则前n－1位中必有奇数个０，故有bn－1个，于是

n－1n－1

an＝２an－1＋bn－1，但an－1＋bn－１＝３，所以，bn－１＝３－an－1，于是

n－1n－1n－２

an＝an－1＋３，即an－an－1＝３，由此知an－１－an－２＝３，也就是3an－１－3an－２

n－1２

＝３，于是有an－4an－1＋3an－２＝0，其特征方程为x－4x＋3＝０，解此方程得：

nn

α１＝１，α２＝３，所以an＝A11＋A23，而a１＝２，a２＝５，于是有 A1＋３A2＝２ A1＋９A2＝５ 解得 A1＝1/2 A2＝1/2

n

所以an＝（３＋１）／２

18. 证明：因为从n＋r个不同的物品中任取r个的方案数是

C（n＋r，r）＝（n＋r）（n＋r—1）．．．（n＋r－r＋1）／r! ＝（n＋１）（n＋２）．．．（n＋r）／r! 它是一个整数，所以（n＋１）（n＋２）．．．（n＋r）必能被r!整除。 19. 证明： 因为已知C（n，l）C（l，r）=C（n，r）C（n-r，l-r）即

C（m，n）C（n，r）=C（m，r）C（m-r，n-r）,所以 左端

=C（m，0）C（m，n）＋C（m，1）C（m-1，n-1）＋．．．＋C（m，n）C（m-n，0） ＝C（m，m）C（m，m-n）＋C（m，m-1）C（m-1，m-n）＋．．． ＋C（m，m-n）C（m-n，m-n） ＝C（m，m-n）C（m-（m-n），m-（m-n））＋C（m，m-n）C（m-（m-n），m-1-（m-n）） ＋．．．＋C（m，m-n）C（m-（m-n），m-n-（m-n）） ＝C（m，n）C（n，0）＋C（m，n）C（n，1）＋．．．＋C（m，n）C（n，n）

n

＝C（m，n）（C（n，0）＋C（n，1）＋．．．＋C（n，n））=C（m，n）2=右端 故命题得证。

20. 证明：将３n个人排成n行，每行３人，不分左中右，则排列方案数为

C（3n，3）·C（3n-3，3）·．．．·C（3，3），其中C（3n，3）为第１行的可能方案数，C（3n-3，3）为在剩余3n-3个人中任取３人站在第２行的方案数，．．．，C（3，3）为最后３个人站在第n行的方案数，因为必须为每一行确定人选，故用乘法法则，由于 C（3n，3）·C（3n-3，3）·．．．·C（3，3） ＝［（3n）（3n-1）（3n-2）／３！］［（3n-3）（3n-4）（3n-5）／３！］．．．［３·２·１/３!］

nnn

＝（3n）!／（3!）是方案数，它必为整数，所以（３n）!／（２３）必是整数。 21. 证明：设任给的５个数为a1，a２，a３，a４，a５，将它们除以３得到的余数分别是

r1，r２，r３，r４，r５，即ai＝３Mi＋ri（i＝１，２，３，４，５），因为除以３的余数只可能是０或１或２，所以如果r1，r２，r３，r４，r５是相同的，则任取其中３个，比如r1，r２，r３，则a1＋a２＋a３＝３（M１＋M２＋M３）＋３r1，必能被３整除。如果r1，r２，r３，r４，r５中有３种余数，比如r1＝０，r２＝１，r３＝２，则a1＋a２＋a３＝３（M１＋M

＋M３）＋（０＋１＋２）＝３（M１＋M２＋M３＋１），必能被３整除。还有一种情况是r1，r２，r３，r４，r５，既不是全都相同（只有一种余数），也不是３种余数都出现，而是只有２种余数，那么，根据鸽巢原理，这５个余数中至少有３个是相同的，比如r1＝r２＝r３＝r，于是a1＋a２＋a３＝３（M１＋M２＋M３）＋３r，它也必能被３整除。综上所述，知任取５个整数中必有３个之和是３的倍数。

22. 证明：设H＝｛h1, h2, ?, hk｝是群G的子群，x，y∈G，若xH∩yH=Ф，则命题已证。

-1-1

现设xH∩yH≠Ф，则必存在g∈G，使g∈xH且g∈yH。设g=xhi=yhj,由此知x=ghi,y=ghj，

-1-1

于是对任意的f∈xH，即f＝xhk＝ghihk，由于H是子群，hi，hk∈H，所以hihk∈H，可

-1

令hihk＝hp∈H。于是f＝g hp＝yhj hp＝yhq∈yH，因而知xH是yH的子集。反过来，对

-1-1-1

任意的u∈yH，即u＝yhl＝ghjhl，由于H是子群，hj，hl∈H，所以hjhl∈H，可令hjhl＝hs∈H。于是u＝g hs＝xhi hs＝xht∈xH，因而知yH是xH的子集。从而xH=yH。 23. 证明：T中元素（x，y，z）满足条件x，y，z∈{1，2，?，n+1}，x

所以z的取值只能是2，3，?，n+1。当z取值i+1时，x，y的取值范围均为1，2，?，

2222222

i。于是共有i个（x，y，i+1），所以|T|=1+2+?+n。令|T|=Sn，则Sn＝1+2+?+n，

2

Sn－Sn－１＝n，于是可设Sn＝A0C（n，0）＋A１C（n，1）＋A２C（n，2）＋A３C（n，3），已知S０＝０，S１＝１，S２＝５，S３＝１４，所以有 S０＝０＝A0 S1＝1＝A0＋A1

S2＝5＝A0＋2A1＋A2

S3＝14＝A0＋3A1＋3A2＋A3 解得

A0＝０，A1＝１，A2＝３，A3＝２，

所以 |T|=Sn= C（n，1）＋３C（n，2）＋２C（n，3）

2

＝n+3n（n-1）/2+2n（n-1）（n-2）/3＝n（2n+3n+1）/6＝n（n+1）（2n+1）/6 而C（n+1，2）＋2C（n+1，3）＝n（n＋1）/2+2（n+1）n（n-1）/3! ＝n（n+1）（3+2n-2）/6＝n（n+1）（2n+1）/6

222

所以|T|=1+2+?+n＝C（n+1，2）＋2C（n+1，3），命题得证。

24. 证：设K个相继的正整数为n＋1，n＋2,?,n＋K,从这n＋K个不同的正整数中选取r

２

个正整数的方法数是

??,即

n?krN=

?n?k?!??n?k??n?k?1???n?k??r?1??为正整r!?n?k?r?!r!数，即分子有r 个相继正整数之积为r！的倍数，当然亦为r的倍数，证毕。 25. 证：利用组合数二分性质得： ???2n?2???n?1???n?1???2n?1??2n?1???????????n?????n?1?? n?1n?1??????????n?1??n???n?1??n??????n?1?? n????2nn2nn?12nn =?? =

???????????????

2nn?1 =

???2?????。

2nn?12nn2nn?126. 证：由二项式定理知，?1?x?n??nk?0??xnkk

当x=2时：3??2nk?0???2

nkknnk?0 当x=r时亦成立：?1?r??????rnkk

（二项式定理中x与y均为实数）。

27. 证明：A?B?C??A?B??C?A?B?C??A?B??C =A?B?A?B?C??A?C???B?C?

=A?B?C?A?B??A?C?B?C?A?C?B?C? =A?B?C?A?B?A?C?B?C?A?B?C 证毕。

28. 证：设k个相继正整数为n+1,n+2,?,n+k.

若不然这k个相继正整数都不能被k整除，于是 n?i?pi?k?ri，（i=1，2，?k）

其中pi为正整数，ri为余数，且1?ri?k?1，（i=1，2，?k）显然k个余数ri只能取k－1个值，由抽屉原理知，必存在m,?,且n?1?m＜?＜n+k使rm?r?，从而?n?????n?m???p??pm??k，即正整数??m??p??pm??k，显然n+1≤??m?n?k,且p??pm亦为整数，于是证毕。

29. 证明：把1～2n分成以下n组，即｛1，2｝，｛3，4｝，?｛2n－1,2n｝。由题设这n 组

有n+1个数，由抽屉原理必有一组至少有两个数，显然是相邻的两个正整数，以下证明这两个相邻正整数互素，不妨设这两个正整数为n与n+1，若不然，不是互等的，那末必有公因子q(q≥2)使n=p1·q，n+1=p2·q。其中p1，p2为整数，于是n+1= p1·q+1= p2·q?（p2－p1）q=1,这与q≥2且p2－p1为整数矛盾，证毕。 30. 证：对n用归纳法。

先证可表示性：当n=0,1时，命题成立。 假设对小于n的非负整数，命题成立。

对于n,设k!≤n＜(k+1)!,即0≤n-k!＜k·k!

由假设对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!,

另一种证法：令j=max{i|ai≠bi}

, 两边被(j+1)!除,得余数aj·j!=bj·j!,矛盾.

31. 证：取C(n,k)和C(n,k-1)进行比较。C(n,k)/C(n,k-1)=(n-k+1)/k。 当k>n/2时,(n-k+1)/k<1,即C(n,k)

当k>n/2时,(n-k+1)/k>1,即C(n,k)>C(n,k-1)得到当k为最接近n/2的数时，C(n,k)取到最大值。

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

k

假设当n=k时,0出现偶数次的字符串有(3+1)/2种。总的字符串有3种。0出现奇数次的字

k

符串有(3-1)/2种。

当n=k+1时，0出现偶数次的字符串包括两部分：

k

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

k

共有(3-1)/2种。

kkk+1

所以共有2(3+1)/2+(3-1)/2=(3+1)/2种，证毕。

1

?3??3?33. 证明：显然，每列中必有两数字相同，共有?有0或1种选择，故共有??2???2?2??种模式，

????种选择，??2???2?6。现有7列，?6??2。即必有2列在相同的两行选择相同的数字，

????即有一巨形，四角的数字相等。

34.一个n阶幻方每行每列的数字之和为：

?3??7??1?2?3????n?/n?n?n2222?1/2n?nn2?1/2。如果将幻方中的每个数a换

?????222成n?1?a，则新幻方的每行每列的数字之和为nn?1?nn?1/2?nn?1/2，

??????所以仍为幻方。

35.假设将S划分为个有序集合S1,S2,??,Sk，所谓有序集合是指S1,S2,??,Sk，是有序的，于是S中的个n元素每个都有k种选择，所以共有k种划分方法。 36.证明：因为c??n,k????1?c?n?k?1,k?

kn所以1/?1?x???1?x?n?n??c??n,k?x????1?c?n?k?1,k?xk，所以命题得证

kk?0k?0??k 37. 证明：以A表示所取10个点所成之集，则A?10。把边长为1的等边三角形分成9个边长为1/3的小等边三角形，并将其编号，以Ai表示A中属于第i个三角形的点所成之集，则

?Ai?19i?A.由鸽笼原理的简单形式，必有正整数k?1?k?9?，使得Ak?2，这表

明所取10个点中必有2个点落在同一个小等边三角形内，它们的距离不大于小等边三角形

的边长1/3

更多课程资料请到大学课程网www.0206.cc学习

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