意志坚强的名言-惯性思维

武汉大学计算机学院
2017-2018学年度第二学期期末考试
《组合数学》试卷（A卷）参考答案
1. (20分，每小题5分)
（1）书架上 有一套《资治通鉴》共20卷，从中选出4卷使得任意两本的卷号都
不相邻的选法有多少种？
解：就是不相邻组合，因此为C(n-r+1,r)，此处n=20,r=4，代入得到
C(20-4 +1,4)=C(17,4)=2380

（2）将英文字母表中的26个字母排序，要求任 意两个元音字母不能相邻，则有
多少种排序方法？
解：先排21个辅音字母，共有21！， 再将5个元音插入到22个空隙中(首尾)有
P(22,5)，故所求为21!×P(22,5)

（3）现在有3个女士和4个男士围一个圆桌就坐，则其中
a）女士两两不相邻的入座方式数有Q(4,4)P(4,3)=3!4!=144 种； -----3分
b）所有女士坐在一起的方式数有 Q(5,5)P(3,3)=4!3!=144种。 -----2分

（4）在一局乒乓 球比赛中，运动员甲以11:7战胜运动员乙，若在比赛过程中甲
的得分一直不少于乙的得分，求有多少 种可能的比分记录？
解：根据题意，由于球赛规则，因此实际求的是求从点(0,0)到点(7,10 )—(7,11）
且从上方不穿过y=x的非降路径数，参见书p32页结果，m=7,n=10,代入 结果为
C(m+n,m)-C(m+n,m-1)=C(17,7)-C(17,6) ---未考虑球赛规则的，可以给3分

2. (15分) 解下列递推关系
< br>a
n
-
a
n
1
-6
a
n
2
3
n
,
n
2



a
0
5,
a
1
2

解：其对应的特征 方程为:x
2
-x-6=0,即为(x-3)(x+2)=0，
其特征根为r
1
=3,r
2
=-2;
由于3是其特征根，因此特解形如Cn3
n
，代入方程得到
Cn3
n
- C(n-1)3
n-1
– 6C(n-2)3
n-2
=3
n

3
解得C= 5
故方程的通解形如
a
n

A
(2)
n
B
3
n

3
n
n
3
，代入 初始条件
5


74
A


AB 5



25

3
---》


-2A3
B
132
51


B

5


25

可得
a
n< br>
7451
n
3
(2)
n
3
n
3
n

25255

3. (10分)

一个1 ×n的方格图形用红、蓝、绿和黄四种颜色涂色，如果有偶数个
方格被涂成红色，还有偶数个方格被涂成 绿色，求有多少种方案？
解：
设涂色方案为a
n
，则对应的母函数为：
G
e
(
x
)(1
(
x
2
2 !
2


2
x
4
4!
)(1
(
e
4
x
2
x
e
x

e

x
)(
e
)
x
2
1!2!
2e
2
x
1)
4

x
2
)
2

1

4
4
n
2
n1
x
n
（）

4n!
n0

4
n
1
2
n
1
n
0
因此其染色方案有
an


，故所求方案数为4
n-1
+2
n-1
种。
1
n
0



x
1
< br>x
2

x
3

x
4
18
4. (15分)求方程

的整数解组的个数。

1
x
i
9,i1,2,3,4
解：做变换y
i
=x
i
-1 ，i=1,2,3,4得

yy
2
y
3
y
4
14


1


0y
i
8,i1,2,3,4< br>设全部无约束解组集合S，其个数|S|为可重复组合数
C(14+4-1,14)=C(17, 3)=680，
令集合A
1
,A
2
,A
3
,A< br>4
分别为约束方程的解组集合：
A
1
：
y
1
9，y
2
0，y
3
0，y
4
0

A
2
：
y
1
0，y
2
9，y< br>3
0，y
4
0

A
3
：
y
1
0，y
2
0，y
3
9，y
4
 0

A
4
：
y
1
0，y
2
0，y
3
0，y
4
9

类似做变换z
1< br>=y
1
-9，可求解出|A
1
|=C(5+4-1,5)=C(8,3 )=56，同理
|A
2
|=|A
3
|=|A
4
|= |A
1
|=56，

而
A
i
A
j
0，ij

A
i
A
j
A
k
0，i，j，k不相等时


A
1
A
2
A
3
A4
0，
故所求
A
1
A
2
A
3< br>A
4
680-456450


5.证明题
（a）(10分）一名实验员在50天里每天至少做一次实验，而实验总次数不超过
75。证明一定存 在连续的若干天，她正好做了24次实验。
证明：令b1，b2，...，b50 分别为这50天中他每天的实验数，并做部分和
a1 = b1，a2 = b1+b2 ，…，a50 = b1+b2+...+b50 .
由题，bi>=1(1<=i<=50)且a50<=75，所以 1<=a1考虑数列 a1，a2，...，a50 ，a1+24，a2+24，a50+24，它们都在1与75+24=99
之间。
由鸽巢原 理知，其中必有两项相等。由（*）知，a1，a2，...，a50互不相等，从
而a1+24，.. .a50+24 也互不相等，所以一定存在1<=i即 24=aj-ai=(b1+b2+b3+…+bi+…+bj)-(b1+b2+…+bi)=
b
i+1
+b
i+2
+...+b
j
所
以从第 i+1天到第j天这连续j-i天中，她正好做了24次实验。

（b）（5分）证明：平面 上任取5个坐标为整数的点，则其中至少有两个点，由
它们所连线段的中点的坐标也是整数。
解答：顶点整数坐标只有4种可能的情况：（奇数，奇数）、（奇数，偶数）、（偶
数，奇数）、（偶数 ，偶数），而一共有5个顶点。由鸽巢原理知，至少有2个顶
点坐标的取值情况相同，而这两个顶点的对 应坐标之和必然为偶数（奇数+奇
数 = 偶数 ； 偶数+偶数=偶数），则其连线段的中点的坐标必然为整数，即为所
求。

6.(15分) 一个项链由7颗珠子装饰而成的，其中2颗珠子是红的，3颗是蓝的，
其余2 颗是绿的，问有多少种不同的装饰方案？其对应的置换群G的循环指标
为
P
G
(
x
1
,
x
2
,,
x
7
)
1
73
（x
1
7
x
1
x
26
x
7
）
14

解答：设r、g、b分别表示红、绿、篮这3种颜色，因此实际要求的是
P(b,g,r)=
1
[(b+g+r)
7
+6(b
7
+g
7
+r
7
)
1
+7(b+g+r)
1
(b
2
+g
2
+r
2
)
3
]
14
中b
3
g
2
r
2
的系数，故有 
3

1

7


[

6071]


14

322
 
111

17!3!11
7]
=
[21042]
=
252
=18(种)。 =
[
14
143!2!2!1!1!1!14

7.(10分) 证明第2类Stirling数具有如下性质
(
n
,2)2
n
1
-1

(5分) (a)
S
证明：对某个元素a放到一个盒子中，考虑其余的元素 与a是否同盒，这样由乘
法法则有2
n-1
种方案，再由于不允许空盒，因此去掉都和 元素a同盒的情况，故
S(
n
,2)2
n
1
-1
。


n

n


b)
S(
n
,
n
2)

3

3

4


(5分)

证明：分情况讨论，可分为

n

（1）3个元 素一组、其余元素一个各一组，其有


3


种方案 < br>
（2）有4个元素分两组（每组2个）、其余元素一个各一组；则选4个元素的方

n

案是


4


种，再考虑 其中一个元素和其余3个元素两两组合有3种情况，因此由


n

乘法法则共有3


4




< br>n

n


再由加法法则有
S(
n,
n
2)

3

3

4


