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

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

| 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?!n!m! ·1=

?m?n?!,以下化为较简单形式:

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

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

21 / 35

?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?? =(2)

?a0?1 ,其中cx<1 1?cx??,aa01????,a???,?,aa12a2r?a????1?r??r??,???

?F?x??a0?a1x?a2x2???arxr??22 / 35

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

=

?????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?3?11?4?1???x?????x???x???2344?5444?54?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-1阶台阶迈一步

上去的,共有an?1种方式;另一类是从第n-2阶台阶迈两个台阶上去的,有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

a1?1,a2?2? 利用特征方程法:由于为2阶常系数齐次递推关系,所以特征方程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.

23 / 35

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

通解为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 利用消元法 得 11n1故an????3????3?n431278. 解 先求对应齐次递推关系特征方程的根。

特征方程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

24 / 35

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

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. 解:①每3人至少缺1把钥匙,且每3人所缺钥匙不同。故至少共有钥匙。

=35把不同的

②任一人对于其他6人中的每3人,都至少有1把钥匙与之相配才能开锁。故每人至少持

=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。

25 / 35