《组合数学》测试题含答案 下载本文

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

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=0,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 =A+B

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

解此方程组得 A=(3+2√3)/6

B=(3-2√3)/6

nn

an=[(3+2√3)(1+√3)+(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.C(n-1,r-1)

将n个球排成一行,两球之间有一间隔,共有n-1个间隔。在此n-1个间隔中任取r-1个,将n个球分成r段,将第i段的球(其中至少有1球)放入第i个盒子,所以共有C(n-1,r-1)种方案。 50. C(n,4)

凸n边形有n个顶点,任取其中4个顶点可以组成一个凸4边形,该4边形的两条对角线有一个交点,所以凸n边形的对角线交于C(n,4)个交点(根据假设,没有3条对角线相交于一点)。 51. Sn=n(n+1)(n+2)(n+3)/4

Sn=1·2·3+2·3·4+...+n(n+1)(n+2) =3!(1·2·3/3!+2·3·4/3!+...+n(n+1)(n+2)/3!) =3!(C(3,3)+C(4,3)+...+C(n+2,3)) =3!(C(3,0)+C(4,1)+...+C(n+2,n-1)) =3!C(n+3,n-1) =3!C(n+3,4)

16 / 35

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

=n(n+1)(n+2)(n+3)/4 52. an=(k/(2(k-1))+k/(2·sqrt((k-1)(k+3)))·

((k-1+sqrt((k-1)(k+3)))/2) +(k/(2(k-1))-k/(2·sqrt((k-1)(k+3)))·

((k-1-sqrt((k-1)(k+3)))/2)

假设从k(k>1)个不同文字取出n个(可以重复)作排列,但不允许一个文字连续出现3次的排列所组成的集合为An,则所求排列数an=|An|。将An中的字符串按最后一个文字可以分成两类:一类是最后一个文字同其前一个文字不相同的那些字符串,共有(k-1)an-1个(最后一位有k-1种选择,而前n-1位是没有一个文字连续出现3次的字符串),另一类是最后两个文字相同,但与倒数第3个文字不相同的字符串,共有(k-1)an-2个,所以有递推关系

an=(k-1)an-1+(k-1)an-2(

23

而a1=k,a2=k,a3=k-k=k(k-1)(k+1 递推关系的特征方程为

x-(k-1)x-(k-1)=0 其根为:

α1=(k-1+sqrt((k-1)(k+3)))/2 α2=(k-1-sqrt((k-1)(k+3)))/2

nn

于是知 an=A1α1+A2α2

由于a1=k,a2=k,由递推关系知a0=k/(k-1),所以

00

a0=k/(k-1)=A1α1+A2α2A=A1+A2

11

a1=k=A1α1+A2α2=A1(k-1+sqrt((k-1)(k+3)))/2 +A2(k-1-sqrt((k-1)(k+3)))/2 解得

A1=(k/(2(k-1))+k/(2·sqrt((k-1)(k+3))) A2=(k/(2(k-1))-k/(2·sqrt((k-1)(k+3))) 所以

an=(k/(2(k-1))+k/(2·sqrt((k-1)(k+3)))·

((k-1+sqrt((k-1)(k+3)))/2) +(k/(2(k-1))-k/(2·sqrt((k-1)(k+3)))·

((k-1-sqrt((k-1)(k+3)))/2)

n+1n+1

53. f(n)=(((1+√5)/2)-((1-√5)/2))/√5

假设从A(编号为0)到编号为i的顶点有f(i)条路径,则f(1)=1,f(2)=2,当i>2时,f(i)=f(i-1)+f(i-2),由此知f(0)=f(A)=1。当i=n时,f(n)=f(n-1)+f(n-2),即f(n)-f(n-1)-f(n-2)=0。其特征方程为: 2

x-x-1=0,它的两个根分别为:α1=(1+√5)/2,α2=(1-√5)/2。

nn

于是知f(n)=A1α1+A2α2,根据 f(0)=1=A1+A2

f(1)=1=A1(1+√5)/2+A2(1-√5)/2, 解得

A1=(1+√5)/(2√5),A2=(1-√5)/(2√5)

所以,

n+1n+1

f(n)=(((1+√5)/2)-((1-√5)/2))/√5=F(n+1) 其中F(n)为第n个Fibonacci数。

17 / 35

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

54. an=(n+n+2)/2

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

an-1-an-2=n-1,由此得an-2an-1+an-2=1,同样有an-1-2an-2+an-3=1,

32

故得an-3an-1+3an-2-an-3=0,其特征方程为x-3x+3x-1=0,解此方程

2n2

得α=α1=α2=α3=1,所以an=(A0+A1n+A2n)α=A0+A1n+A2n ,而

a0=1=A0 a1=2=A0+A1+A2

a2=4=A0+2A1+4A2

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

由此知

2

an=(n+n+2)/2

55、56

因为x1+x2+x3+x4=31,xi≥0(i=1,2,3,4)的整数解共有C(4+31-1,31)=C(34,3)=34·33·32/6=5984(个)。

再考虑x1+x2+x3+x4=31,xi≥10(i=1,2,3,4)的整数解的个数。令N为全体非负整数解,则|N|=5984。

令Ai(i=1,2,3,4)为其中xi≥10的解集合。则|A1|即为(x1+10)+x2+x3+x4=31,也就是x1+x2+x3+x4=21的非负整数解的个数。所以,

|A1|=C(4+21-1,21)=C(24,3)=24·23·22/6=2024。同理可知 |A2|=|A3|=|A4|=|A1|=2024。类似地,

|Ai∩Aj|=C(4+11-1,11)=C(14,3)=14·13·12/6=364(1≤i

根据容斥原理,a+b+c+d=31,0≤a,b,c,d≤9的整数解个数等于 |?1∩?2∩?3∩?4|=

|N|-4|A1|+C(4,2)|A1∩A2|-C(4,3)|A1∩A2∩A3|+ |A1∩A2∩A3∩A4|

=5984-4·2024+6·364—4·4+0=56 56. 190800

假设6个学生参加第1位教师的面试的顺序为1、2、3、4、5、6(即对第1个面试的学生编号1,...,对第6个面试的学生编号6),那么,这6个学生参加第2位教师的面试的顺序必定是1、2、3、4、5、6的一个错排。不然,就有至少一个学生要同时参加两为教师的面试。于是面试方案总数为

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) 格式为(1)

p2(逆时针旋转60o) (123456) 格式为(6)

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) 格式为(6)

22

p7(沿14轴翻转) (1)(4)(26)(35) 格式为(1)(2) 22

p8(沿25轴翻转) (2)(5)(13)(46) 格式为(1)(2)

22

p9(沿36轴翻转) (3)(6)(15)(24) 格式为(1)(2)

p10(沿12边54边中线翻转)(12)(36)(45) 格式为(2)

p11(沿23边56边中线翻转)(14)(23)(56) 格式为(2)

p12(沿16边34边中线翻转)(16)(25)(34) 格式为(2) 所以,总方案数为

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. C(m+1,n)

将m个0排成一行,两个0之间有一间隔,共有m+1(≥n)个间隔(包括头尾处的间隔)。在此m+1个间隔中任取n个插入1,则所得符号串满足要求,所以共有 C(m+1,n)个这样的符号串。 60. (n-1)!n!,(n-1)!n!/(n-m)!

先让n个男人围坐一圈,共有(n-1)!种坐法。对应于每一种坐法,有n个间隔,将n个女人排成一行插入这n个间隔中,有n!种方案,所以共有(n—1)!n!种不同的坐法。

若只有m(m

nn+1n+1

61.an=4-√3(2+√3)/6+√3(2-√3)/6

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

19 / 35

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

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

nn-2n-2

an=4an-1 +bn-2,而an+bn=4,即an-2+bn-2=4,也就是bn-2=4 -an-2,

n-2n-2n-2

由此知an=4an-1 +4 -an-2,即an-4an-1 +an-2=4,可推知4(an-1-4an-2 +an-3)=4

32

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

nnn

α1=4,α2=2+√3,α3=2-√3,所以可设an=A1α1+A2α2+A3α3,已知a1=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 所以

nnn

an=4-(3+2√3)(2+√3)/6-(3-2√3)(2-√3)/6

nn+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,根据容斥原理可知,符合条件的解的个数为

|?1∩?2∩?3|=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