《组合数学》测试题含答案
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. Ｓｎ＝ｎ（ｎ＋１）（ｎ＋２）（ｎ＋３）／４
Ｓｎ＝１·２·３＋２·３·４＋．．．＋ｎ（ｎ＋１）（ｎ＋２） ＝３！（１·２·３／３！＋２·３·４／３！＋．．．＋ｎ（ｎ＋１）（ｎ＋２）／３！） ＝３！（Ｃ（３，３）＋Ｃ（４，３）＋．．．＋Ｃ（ｎ＋２，３）） ＝３！（Ｃ（３，０）＋Ｃ（４，１）＋．．．＋Ｃ（ｎ＋２，ｎ－１）） ＝３！Ｃ（ｎ＋３，ｎ－１） ＝３！Ｃ（ｎ＋３，４）
16 / 35
《组合数学》测试题含答案
＝ｎ（ｎ＋１）（ｎ＋２）（ｎ＋３）／４ 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数。
17 / 35
《组合数学》测试题含答案
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） 18 / 35 2 《组合数学》测试题含答案 3 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． ?1110100???H??0111010? ?1101001???3?7因为 ?1??0G??0??0?而 000101??100111???I3|A4?3? 010110??001011??4?7?1110???TA??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位中已出 19 / 35 《组合数学》测试题含答案 现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， 20 / 35