组合数学 试题及答案09
教师赞歌-按图索骥的故事
…
…
…
…
…
…
…
…
效
…
…
…
…
…
无
…
…
…
…
…
题
…
…
院
…
学
…
…
答
…
…
…
…
…
内
…
…
…
名
…
…
姓
以
…
…
…
…
…
线
…
…
…
…
…
封
…
…
号
…
…
学
…
密
…
…
…
…
…
…
…
…
电子科技大学研究生试卷
（考试时间： 至 ，共 2 小时）
课程名称
组合数学 教师 学时 40 学分 2
教学方式 讲授 考核日期 2009 年 12 月 日 成绩
考核方式： （学生填写）
一、(14分)
现安排从星期一至星期五对5个项目A, B, C, D, E进行评审，每个项目安排
一天，每天安
排一个项目。但要求项目A不安排在星期二评审，项目B不安排在星期三
和星期五评审，项目C不安排在
星期四评审，项目D不安排在星期一评审，项目E不安
排在星期三和星期四评审。问有多少种不同的评审
安排方案？
解 原问题可模型化为一个5元有禁位的排列.
其禁区棋盘C如下图的阴影部分。
-----------------4分
由图,可得C的棋盘多项式为
R(C)=
1 2 3 4 5
A
=
1+7x+17x
2
+18x
3
+8x
4
+x
5
-----------------5分
B
所以安排方案数为
C
5! - 7·4! + 17·3! - 18·2! + 8-1
-----------------4分
D
= 25
E
即共有25种。
-----------------1分
二、（10分）用2种颜色对下图的小圆点着色，证明必存在两列，其着色完全相同。
1 2 3 4 5 6 7 8
9
证明：因每个小圆点有2种颜色可选,故每列恰有8 种着色方案,
-------------5分
组合数学试题 共 5 页 ，第 1 页
…
…
…
…
…
…
…
…
效
…
…
…
…
…
无
…
…
…
…
…
题
…
…
院
…
学
…
…
答
…
…
…
…
…
内
…
…
…
名
…
…
姓
以
…
…
…
…
…
…
…
…
…
线
…
…
…
…
…
…
…
…
效
…
…
封
…
…
…
…
号
…
…
…
…
学
无
…
…
密
…
…
…
…
…
…
…
…
现有9列,由鸽笼原理,知必有两列着色相同.
-------------5分
三、（16 分）求方程
x
1
x
2
x
3
x
4
13
3x
1
6,2x
的正整数解的个数。
2
6,x
3
2
解
等价于求集合S
0
＝
{3.A,4.B,1.C,∞.D}的所有6-组合构成的集合。---------------
--4分
令集合S为
{A,B,C,D}
的所有6-组合构成的集合。
-----------------2分
则有 |S|=F(4,6) = 84。
令 A
1
表示S中至少含有4个A的元素构成的集合,
A
2
表示S中至少含有5个B的元素构
成的集合,
A
3
表示S中至少含有2个C的元素构成的集合,
-----------------4分
于是
|A
1
|F(4,2
)10
,
|A
2
|F(4,1)4
,
|A
3
|F(4,4)35
|A
1
A
3
|
1
|A
1
A
2
||A
2
A
3
||A
1
A<
br>2
A
3
|0
-----------------2分
由容斥原理，所求的5-组合数为
3
A
1
I
A
2
I
A
3
S
A
i
A
i
I
A
j
A1
I
A
2
I
A
3
i1ij
-----------------3分
=84– (10＋4+35)＋1 = 36
-----------------1分
四、（14分）解下列递归关系 <
br>
a
n
5a
n1
14a
n2(2)
n
a
0
2,a
1
5
解
对应的齐关系的特征方程 x
2
-5x-14=0
-----------------3分
有根
x
1
=
7，x
2
= -2
。
-----------------1分
故齐关系的通解为
a
*
n
=c
1
7
n
+c
2
(-2)
n
-----------------1分
设特解
a
n
=
An(-2)
n
，代入原关系：An(-2)
n
-5A(n-1)
(-2)
n
-1
-14A(n-2) (-2)
n
-2
=
(-2)
n
-----------------3分
A =
2
2n（－2）
n
9
a
n
=
9
-----------------2分
∴ a
n
=
a
*
n
+
a
= c
2n（－2）
n<
br>n
1
7
n
+c
2
(-2)
n
+
9
-----------------1分
组合数学试题 共 5 页 ，第 2 页
c
1
c<
br>2
2
由初值得
<
br>4
7c
1
2c
2
－5
9
<
br>85
c
1
81
-----------------2分
c
77
2
81
n
2n（－2）
85
n
77
∴
a
n
= 7+ (-2)
n
+
-----------------1分
9
81
81
五、（12分）求1出现奇数次且2出现偶数次的n位十进制数的个数。
解：
设a
n
是由0,1,……,9组成的满足“1出现奇数次”且“2出现偶数次”的长为n的
序列的
个数， -----------------2分
则a
n
的指数母函数为：
xx
3
x
2
x
4
xx2e
x
－e
－x
e
x
＋e
－x
8x
e
10x
－e
6x
8
f
e
(x) =
()(1
)(1＋)e
1!3
!2!4!1!2!224
n
1
nn
x
=
(10
6)
-----------------4分
n0
4n!
1
n
，n≥1
-----------------3分
(106
n
）
4
以0
为首项的长为n的序列有a
n
－
1
个，在上述序列中去掉以0为首项的长为n
的序列便
可得到1出现奇数次且2出现偶数次的n位十进制数的个数：
-----------------2分
所以 a
n
=
1<
br>a
n
－a
n
－
1
＝
(910
n－
1
56
n－1
）
-----------------1分
4
六、（14分）求由数字
0，1，2，3，4，5，6，7组成的
r
位数中，1和5都出现偶数次，
2和6至少
出现一次的
r
位数的个数。
解
：这是一个排列问题。设满足条件的
r
位数字串的个数为
a
r
，则序列
(a
1
,a2
,L,a
r
,L)
对应的指数母函数为：
-----------------3分
x
2
x
4
xx2xx2
)
2
()
2
(1＋)
4
-----------------4分 f
e
(x) =
(1
2!4
!1!2!1!2!
e
x
e
－x
2x
e
8x2e
7x
3e
6x
4e
5x
3e
4x
2e
3x
e
2x
24x
()(e1)e
24
n
1
rrrrrrr
x
(82
7364534232)
n!
n0
4
组合数学试题 共 5 页 ，第 3 页
所以
1
a
r
＝
(8
r
27
r
36
r
45
r
34
r
23
r
2
r
)
-----------------3分
4
首位取0的
r
位数字串的个数
为
a
r1
，故所求的
r
位数的个数为
a
r
－
a
r1
＝
-----------------2分
1
r1r1r1r1r1r
1r1
(7812715616594432)
r0
4
0
r0
-----------------2分；如果没
有针对r=0单独结果的，只得1分
七、（6分）设
a
n
表示一个凸n边形被它的对角线划分成互不重
叠的区域个数
(没有三条对角线在该n边形内交于一点)。试建立
a
n
的递规
关系（不需要求解）。
解
：
n1
a
n<
br>a
n1
3
n2
,n>3.
其中：
a
3
1
―――――――――――――――――过程4分，结果2分。
八、（14分）若7
个人中有3对夫妇，试问从中取出6个人的夫妇均不相邻的圆排列有多
少种？
解
：分两种情况。
情况1. 取出的6个人中恰含3对夫妇。
-----------------1分
计算如下:
取全集S为6个人的圆排列的集合。令A
i
为S中第i对夫妇相邻的圆排列的集合，i = 1,2,3。
有
-----------------1分
| S | = 5！＝120, |
A
i
| = 2•4！＝48， i = 1,2,3；
|
A
i
∩A
j
| = 4•3！＝24（i j = 1,2,3；i
j）；| A
1
∩A
2
∩A
3
| ＝ 16。
-----------------2分
由容斥原理
-----------------1分
A
1
A
2
A
3
=
120－3•48＋3•24－16 ＝32 -----------------1分
情况2. 取出的6个人中恰含2对夫妇。
-----------------1分
此时取6人的方式有6种，对取定的每一种取全集S为6个人的圆排列的集合。令
组合数学试题 共 5 页 ，第 4 页
A
i
为S
中第i对夫妇相邻的圆排列的集合，i = 1,2。
-----------------2分
有
| S | = 5！＝120, |
A
i
| = 2•4！＝48， i = 1,2；|
A
1
∩A
2
| ＝4•3！＝24。---------------1分
由容斥原理
-----------------1分
A
1
A
2
= 120－2•48＋24 ＝48
-----------------1分
所以此类总数为 6•48＝288
-----------------1分
最终结果为: 32 ＋ 288＝320
-----------------1分
组合数学试题 共 5 页 ，第 5 页