组合数学 试题及答案
学习用品-统计分析师
…
…
…
…
…
…
…
…
效
…
…
…
…
…
无
…
…
…
…
…
题
…
…
院
…
学
…
…
答
…
…
…
…
…
…
…
…
…
内
…
…
…
…
…
…
…
名
…
效
…
…
以
…
姓
…
…
…
…
…
…
…
无
…
…
线
…
…
…
…
…
…
…
…
题
…
…
封
…
院
…
…
…
…
学
号
…
…
…
答
学
…
…
密
…
…
…
…
…
…
…
…
内
…
…
…
…
名
…
…
…
…
…
姓
以
…
…
…
…
…
线
电子科技大学研究生试卷
（考试时间： 至 ，共 2
小时）
课程名称 组合数学 教师 学时 40
学分 2
教学方式 讲授 考核日期 2008 年 11 月
26 日 成绩
考核方式： （学生填写）
一、（16 分）求方程
x
1
x
2
x
3
x
4
10
1x
的正整数解的个数。
1
4,2x
2
6,0x
3
2
解 <
br>等价于求集合S
0
＝
{3.A,4.B,1.C,∞.D}的所有5-组合构成
的集合。-----------------4分
令集合S为
{A,B,C,D}
的所有5-组合构成的集合。
-----------------2分
则有 |S|=F(4,5) = 56。
令 A
1
表示S中至少含有4个A的元素构成的集合,
A
2
表示S中至少含有5个B的元素构
成的集合,
A
3
表示S中至少含有2个C的元素构成的集合,
-----------------4分
于是
|A
1
|F(4,1
)4
,
|A
2
|F(4,0)1
,
|A
3<
br>|F(4,3)20
|A
1
A
2
||A<
br>1
A
3
||A
2
A
3
||A
1
A
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分
=56 – (4+1+20) = 31
-----------------1分
二、（16 分） 现有一项目，全
国4个片区共28家单位申报，其中，西南片区有5家，华
北片区有8家，华东片区有4家，华南片区有
11家。假定同一片区的各个单位不加以区
别，现在要从中选取8家单位入围。
（1）问理论上有多少种不同的选取方案？
（2）现为了考虑不同片区的特殊情况，如果西南
片区至少有1家入围，华北片区至少有
2家入围，问理论上有多少种不同的选取方案？
解
（1）
组合数学试题 共 5 页 ，第 1 页
…
…
…
…
…
…
…
…
效
…
…
…
…
…
无
…
…
…
…
…
题
…
…
院
…
学
…
…
答
…
…
…
…
…
内
…
…
…
名
…
…
姓
以
…
…
…
…
…
线
…
…
…
…
…
封
…
…
号
…
…
学
…
密
…
…
…
…
…
…
…
…
等价于求集合S
0
＝
{5.A,8.B,4.C,11.D}的所有8-组合构成的集合。-----------------2分
令集合S为
{A,B,C,D}
的所有8-组合构成的集合。则有
|S|=F(4,8) = 165。
令
A
1
表示S中至少含有6个A的元素构成的集合,
A
2
表示S中至少含有5个C的元素构
成的集合，
-----------------2分
于是
|A
1
|F(4,2
)10
,
|A
2
|F(4,3)20
,
|A
1
A
2
|0
-----------------1分
由容斥原理，所求的9-组合数为
A
2
1
A
2
S
i1
A
i<
br>
|A
i
A
j
|
----------------2分
=165 – (10+20)= 135
-----------------1分
（2）设
a
r
为选取
r家入围的方案数，故
(a
1
,a
2
,L,a
r
,
L)
的母函数为
f(x)(xx
2
x
3
x
4
x
5
)(x
2
x
3
...x
8
)(1xx
2
...x
4
)(1xx
2
...x
11
)
-----------------5分
x
3
...16x
8
...
-----------------2分
因此理论上有54种不同的选取方案。
-----------------1分
三、(16分) 假如未来连续的5届奥运会（
简称第一届到第五届）分别由五大洲的一个国
家承办，每个大洲承办一次。根据具体情况，亚洲不能承办
第一届和第二届，欧洲不能
承办第二届和第三届，非洲不能承办第三届，北美洲不能承办第四届和第五届
，南美洲
不能承办第五届。问未来的5届奥运会有多少种不同的安排方案？
解
原问题可模型化为一个5元有禁位的排列. 其禁区棋盘C如下图的阴影部分。
-----------------5分
由图,可得C的棋盘多项式为
R(C)=
1 2 3 4 5
=(13xx
2
)(15x6x
2
x
3
)<
br>
A
B
＝
18x22x
2
24x
3
10x
4
x
5
C
D
组合数学试题 共 5 页 ，第 2 页
E
-----------------6分
所以安排方案数为
5! - 8·4! +
22·3! - 24·2! +10-1
-----------------4分
= 21
即共有21种。
-----------------1分
四、（10分）一位女主人宴请5位男士和4位
女士，该女主人有多少种方法让所有男士和
女士（包含该女主人）围一张圆桌（男女）交替就坐？
解：先将5个男的围圆桌而坐，其就坐方式为
5!
，
－4分
5
然后加入一个女的有5种方式，再加第2个女的就有
4种方式，加入第3个女的就有3
种方式，……加入第5个女的只有1种方式，
－4分
故由乘法规则知，其就坐方式共有：
5!
543214!5!
＝2880
－2分
5
五、（12分）解下列递归关系
a
n
a
n1
2a
n2
a1 , a3
2
1
解
其特征方程为：
x
2
x20.
-----------------4分
特征根
x
1
1,x
2
2
.
-----------------2分
通解
a
n
c
1<
br>(1)
n
c
2
2
n
由初始条件得
.
-----------------2分
c
1
(1)c
2
21
22
c
1
(1)c
2
23
解得
-----------------2分
12
c
1
,c
2
33
.
-----------------1分
该递推关系的解为
组合数学试题 共 5
页 ，第 3 页
12
a
n
(1)
n
2
n
33
-----------------1分
六、（12分）试用母函数法求出现偶数个5的n位十进制数的个数。
解：
设a
n
是由0,1,……,9组成的满足“5出现偶数次”的长为n的序列的个数，
-----------------2分
则a
n
的指数母函数为：
x
2
x
4
xx
2
)(1＋)
9
-----------------4分
f
e
(x) =
(1
2!4!1!2!
e
x
e
－x
9x
e
10x
e
8x
e
22
n
1
nn
x
=
(108)
n!
n0
2
所以
a
n
=
1
，n≥1
-----------------3分
(10
n
8
n
）2
以0为首项的长为n的序列有a
n
－
1
个，在上述序列中去掉
以0为首项的长为n的序
列便可得到出现偶数个5的n位十进制数的个数：
-----------------2分
a
n
－a
n
－
1
＝
1
(910
n－1
78
n－1
）
-----------------1分
2
七、（12分）求由数字0，1，2，3，4，5，6，7组成的
r
位数中，3和5都出现
偶
数次，2和4至少出现一次的
r
位数的个数。
解：这是一个排列问题。设
满足条件的
r
位数字串的个数为
a
r
，则序列
(a
1
,a
2
,L,a
r
,L)
对应的指数母函数为：
-----------------2分
f
e
(x) =
x
2
x
4
xx2xx2
(1)
2
()
2
(1＋)
4
-----------------4分
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 页 ，第 4 页
所以
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
-----------------1分
八、（6分）设
a
n
为边长是整
数且最大的边长为n的不全等的三角形的个数，试建立
a
n
的递规关系（不需要求解）
。
解：
(n1)
2
4
n是奇数
a
n
n是偶数
(n2)l4
纠错：n为偶数An=（n+2）n4
―――――――――――――――――过程4分，结果2分；如果只有结果，
可以给5分。
组合数学试题 共 5 页 ，第 5 页