发布时间 : 星期四 文章《组合数学》测试题含答案更新完毕开始阅读
它们分别是{0，1，10，11，100，101，111，1000，1001，1010，1011，1100，1101，1110，1111}
4、 从5个字母中选取4个组成的字符串共有p(5,4)=5×4×3×2=120种。如果允许字母重
复出现，则长度为3的字符串共有5×5×5=125种。
5、 可以这样考虑：在9个数字中不重复地选取7个作排列共有P?9,7?种，其中出现5和6相邻的排列数共有2?6?P?7,5?种，因为出现5和6相邻的排列可看成是从1，2，3，4，7，8，9七个数中选5个排列后，将56或65插入到这5个数的6个间隔位置上（数前、数后及两个数字之间的间隔共6个位置），所以包含相邻的5和6的7位数共有
。 2?6?P?7,5?，于是所求数的个数为P?9,7??2?6?P?7,5??1512006、 因为任3点均不共线，所以25个点中每两个点组成一条直线，每3个点了构成一个三
角形，所以共有C?25,2??300条直线和C?25,3??2300个三角形。
7、 因为所求的数为偶数，所以个位只有2种选择：2或4。因为4位数字全不相同，所以
乘余3位数只能是1，2，3，4，5中去掉用于个位数的数字之后的4个数字的3排列，可是共有2×P(4,3)=24个这样的数。
?3?5?7?11，所以共有?4?1??2?1??3?1??1?1??1?119个不同8、 因为7715785的正因子
4239、因为在1到50中共有10个数含有因子5而这10个数中又有2个包含有因子25。因此50！中含有10+2=12个5因子，显然50！中至少含有12个因子2，因为在1到50这50个数中有25个是偶数所以50！中含有12个因子10，即50！在结尾处有12个0。 10、符合条件的数可分成以下几类： （1）8位数：共有7×P（7，7）=35280个 （2）7位数：共有7×P（7，6）=35280个 （3）6位数：共有7×P（7，5）=17640个 （4）5位数：共有7×P（7，4）=5880个 （5）4位数：8位数>5的有3×P（7，3）=630个 8位数=5，百位数>4的有4×P（6，2）=120个 8位数=5，百位数=4的有P（6，2）=30个 所以符合条件的数共有94860个 11. 3761 =5·6!+5!+4!+2·3!+2!+1
12. 因为和(p)=(3214)对应的中介数是（021），所以（p）的序号为m=0·3!+2·2!+1=5,即(p)是第5个排列
13. 因为117=4·4!+3·3!+2!+1，则中介数为（4311），所以序号为117的5个文字的全排列为54231。
14. 因为a1=0,所以2在1的右边，a2=2，所以3在1和2的左边,a3=1，所以4在2的前面且在3和1的后面，因此所对应的排列为3142。 15. 123，132，213，231，312，321
16. 1234 1243 1423 4123 1324 1342 1432 4132 3124 3142 3412 4312 2134 2143 2413 4213 2314 2341 2431 4231 3214 3241 3421 4321
17. 排列4231的下一个排列是4213。
18. 因为5件工作中的每一件工作都可由4个人中的任一人完成，因此每件工作有4种分配方法，所以总共有4×4×4×4×4=1024种完成任务的方案。 19. 因为没有限制一个同学可得纪念章和纪念册的个数，所以将4枚纪念章分给十个同学的方法有C（10+4-1,4）=C(13,4),将6本纪念册分给十个同学的方法有C（10+6-1，6）=C（15，6），所以若有C（13，4）、C（15，6）种方案。
20. 如果限制每人得1件物品，则共有10！/（4！6！）12，13，14，15，16，23，24，25， 26，34，35，36，45，46，56
21. 因为n边形的每个顶点有n-3条对角线，要使另一边也是对角线，则选中的两条对角线不能相邻，于是相当于在n-4条对角线中选2条对角线作三角形的两边，另一条边即为此二对角线顶点的连线。所以共有C(n-4,2)个这样的三角形，有n个顶点，共有n·c(n-4,2)个三角形。但这里有重复，因为每一个满足条件的三角形在三个顶点处重复了3次，所以真正不同的三角形只有n·c(n-4,2)/3.例如，6边形中可以找出6·c(2,2)/3=2个这样的三角形。
22. 共有C（3+6-1,6）=C(8,6)=C(8,2)=28项。
23. 因为可以在{1,2,?,18}中任取3个的组合同在{1,2,?,20}中任取3个没有相邻的数组成的集合之间建立起一一对应关系,所以答案是C(18,3)=816
24. {c,c,c},{b,c,c},{a,c,c},{a,b,c},{a,a,c},{a,a,b}，共6个3组合， {a,c ,c,c},{b,c,c,c},{a,b,c,c},{a,a,c,c},{a,a,b,c}共5个4组合。 25. F1 = 1, F 5 = 5
26. 因为能被4整除的有10000/4=2500，能被5整除的有1000/5=2000，能被6整除的有10000/6=1666，能同时被4，5整除的有10000/20=500，能同时被4，6整除的有10000/24=416，能同时被5，6整除的有10000/30=333，能同时被4，5，6整除的有10000/120=83，所以符合要求的有10000-（2500+2000+1666）+（500+416+333）-83=5000（个） 27. 因为k=2C(k,2)+C(k,1)=2×k(k－1)/2+k= k
2
2
所以1+2+??+n=2(C(1,2)+C(2,2)+??+C(n,2))+C(1,1)+C(2,1)+??+C(n,1)
222
=2×C(n+1,3)+C(n+1,2)
=2×(n+1)n(n－1)/(3×2)+(n+1)n/2
=n(n+1)(2n+1)/6
28. N=C(7+5,7)=C(7+5,5)=C(12,5)=792
一般情况 N=C(m+n,n)
29. N=(1+5)(1+2)(1+3)(1+4)=360
4822052105481020
30. 令x=y, 则x=y, x=y,于是（1+y+y）中y项的系数N即为(1+x+x)中x项的系
5222
数，而y=y?y·y·y·y=y·y·y·y=y·y·y，于是
N=C(10,5)+c(10,3)c(7,1)+c(10,1) ·c(9,2)=1326
31 S3={(1)(2)(3),(23),(12),(13),(123),(132)}
3
(1)(2)(3)的格式是(1)
12
(23),(12),(13)的格式是(1)(2)
1
(123),(132)的格式是(3)
32 因为bk=vr , r(k-1)=λ(v-1),已知 b=14,k=3,λ=2
所以 14×3=vr 即时 vr=42 求得 v=7 r(3-1)=2(v-1) 2r=2(v-1) r=6 33. 39=4!+2?3!+2!+1!=24+12+2+1 34. N=7!=5040
n-1
35. 因为C(n,1)+2C(n,2)+?+nC(n,n)=n?2
10-1
所以C(10,1)+2C(10,2)+?+10C(10,10)=10?2=5120
36.
?1??2?3? ?4?5??6??7234567??1??345671??3456712??5??567123?和?7?2671234???712345??4??123456??6234567??456712?671234??123456? 345671??567123??712345?37. N=C(2n+1,0)+C(2n+1,1)+?+C(2n+1,2)+?+C(2n+1,n)
=2(C(2n+1,0)+C(2n+1,1)+?+C(2n+1,n))/2
=(C(2n+1,0)+C(2n+1,2n+1)+C(2n+1,1)+C(2n+1,2n)+? +C(2n+1,n)+C(2n+1,n+1))/2
2n+12nn=2/2=2=4 312
38. N=(2+2?2+3?2)/6=4 39. 解：N=2?7！=10080
40304030
40. 解：∵M=gcd(10,20)=2?5,∴N=(40+1)(30+1)=1271
41. 解：N=int(1000/3)-int(1000/15)-int(1000/21)+int(1000/105)=333-66-47+9=229
4
42. 解： ∵ △Sn=Sn+1-Sn=(n+1)
∴可设Sn=A?C(n,0)+B?C(n,1)+C?C(n,2)+D?C(n,3)+E?C(n,4)+F?C(n,5),于是
可知：
A=0 解得： A=0 A+B=1 B=1 A+2B+C=17 c=15 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. Ｓｎ＝ｎ（ｎ＋１）（ｎ＋２）（ｎ＋３）／４
Ｓｎ＝１·２·３＋２·３·４＋．．．＋ｎ（ｎ＋１）（ｎ＋２） ＝３！（１·２·３／３！＋２·３·４／３！＋．．．＋ｎ（ｎ＋１）（ｎ＋２）／３！） ＝３！（Ｃ（３，３）＋Ｃ（４，３）＋．．．＋Ｃ（ｎ＋２，３）） ＝３！（Ｃ（３，０）＋Ｃ（４，１）＋．．．＋Ｃ（ｎ＋２，ｎ－１）） ＝３！Ｃ（ｎ＋３，ｎ－１） ＝３！Ｃ（ｎ＋３，４）