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

且每列的元素和均相等）

35.证明：把有n个元素的集合s划分为k个有序集合的个数等于kn 36.试证明：1/?1?x?????1?c?n?k?1,k?xk,x?1

nk?0?k 37.证明：如果在边长为1的等边三角形内任取10个点，则必有2个点，它们

的距离不大于1/3。

11 / 35

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

测 试 题 答 案

——组合数学

一、选择题

1.D 2.C 3.A 4.C 5.A 6.D 7.A 8.B 9.C 10.C 11.B 12.C 13.C 14.A 15.C 16.B 17.D 18.A 19.D 20.C 21.C 22.B 23.D 24.B 25.D 二、填空题 1. 267

4n?2n2.

2n3. an?c1?2n?c2???2??c3?3n?n?0,1,2,???

4. 3?3?2?3

5.

nn1?7t?14t2?8t3?t4

6. 210 7. 0 8. 420 9. 2

10.

2n3?5n2?3n?1

n?111. 2?n?1

?n2?3??n?k?12. ? ?????12??2?13. 23

三、计算题

1、 在1000至9999之间的数都是4位数。我们可以先选个位，再选千位，百位和十位。因

为我们要的数是奇数，所以个位数字可以是1，3，5，7，9中的任何一个，即有5种选择。选定个位数之后，十位就只有8种选择了。百位也只有8种选择，而十位则只有7种选择，因此应用乘法原则，问题的答案是5×8×8×7=2240种。

2、 在这个问题中，我们要计算的是组合数，因为粉笔的特性与上面三种数的顺序无关，利

用乘法法则可知共有3×8×4=96种不同种类的粉笔。

12 / 35

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

3、 因为2进制数必须考虑其数字的次序，故要计算的是排列问题。有4种选择要做，并且

每种都可以独立地选择0或1，于是有2×2×2×2=24=16种至多4位数字的2进制数，它们分别是{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??151200。

6、 因为任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个这样的数。 8、 因为7715785?3?5?7?11，所以共有?4?1??2?1??3?1??1?1??1?119个不同

的正因子

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的前

13 / 35

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

面且在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

14 / 35

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

=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 15 / 35