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

| 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－１阶台阶迈一步

上去的，共有an?1种方式；另一类是从第n－２阶台阶迈两个台阶上去的，有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? 利用特征方程法：由于为２阶常系数齐次递推关系，所以特征方程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. 解:①每３人至少缺１把钥匙，且每３人所缺钥匙不同。故至少共有钥匙。

=35把不同的

②任一人对于其他６人中的每３人，都至少有１把钥匙与之相配才能开锁。故每人至少持

＝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