组合数学 试题及答案06
高高在上-彐怎么读
…
…
…
…
…
…
…
…
效
…
…
…
…
…
无
…
…
…
…
…
题
…
…
院
…
学
…
…
答
…
…
…
…
…
内
…
…
…
名
…
…
姓
以
…
…
…
…
…
线
…
…
…
…
…
封
…
…
号
…
…
学
…
密
…
…
…
…
…
…
…
…
电子科技大学研究生试卷
（考试时间： 14：30 至 16：30 ，共 2 小时）
课程名称 组合数学 教师 学时 40 学分
2
教学方式 讲授 考核日期 2006 年 12 月 2
日 成绩
考核方式： （学生填写）
一．填空题（每空2分，共22分）
1．食品店有三种不同的月饼（同种月饼不加
区分），第一种有5个，第二种有6个，
第三种有7个，
(1)
从中取出4个装成一盒（盒内无序），则不同的装法数有 种 ；
(2) 从中取出6个装成一盒（盒内无序），则不同的装法数有 种 ；
（3）若将所有的月饼排在一个货架上，则排法数有
种（给出表达
式，不必算出数值结果）。
（4）若将所有的月饼装在三个不同的盒
子中，盒内有序（即盒内作线排列），盒子不
空，则不同的装法数又有
种（给出表达式，不必算出数值结果）。
2．棋盘C
如图1所示，则棋子多项式
R(C) =
图1
3．设有足够多的红球、黄球和绿球，同色球不加区分，设从中无序地取出n
个球的方
式数为a
n
，有序地取出n个球的方式数为b
n
，但均需满
足红球的数量为偶，黄球的数
量为奇，则
(1)
由组合意义写出的{a
n
}的普通母函数为
；
求和后的母函数为
。
组合数学试题 共 6 页 ，第 1 页
效
…
…
…
…
…
…
…
…
(2)由组合意义写出的{b
n
}的指数母函数为
；
求和后的母函数为
。
4．（1） 将6个无区别的球放入3个无区别的盒子中且盒子不空的放法数为
。
…
…
…
…
…
无
…
…
…
…
…
题
…
…
院
…
学
…
…
答
…
…
…
…
…
内
…
…
…
名
…
…
姓
以
…
…
…
…
…
线
…
…
…
…
…
封
…
…
号
…
…
学
…
密
…
…
…
…
…
…
…
…
（2）将6个有区别的球放入3个无区别的盒子中且盒子不空的放法数为
。
（已知将5个有区别的球放入3个无区别的盒子中且盒子不空的放法数为25）
二、（14 分） 给定重集B = {3·A, 3·B, 4·C,10·D
}。求B的8-组合数。
三、（14分）解下列递归关系
a
n
6a
n1
7a
n2
(1)
n
a,a
7
0
7
1
8
四、（10分）用三种颜色对下图的小圆点着色，证明必存在两列，其着色完全相同。
1 2 3 4 5 6 7 8
9 10
五、（16分） 设长为n的三元序列（
即用0,1,2组成序列）中1与2的个数之和为奇的序
列个数为a
n
。
1．试建立{a
n
}的递归关系（不要求解出）。
2．用另一方法（即不用解递归关系的方法）求出a
n
。
六、
（14分）对下图中的7个小方格用红、黄、绿和黑四种颜色着色，问:
着红、黄和绿色的小方格的个数均不为2的着色方案数是多少 ？
七、（共10分）
1.现有7个人，其中恰有一对夫妇。试问从中取出6个人的夫妇不相邻的线排列有多
少种？
2.若7个人中有三对夫妇，试问从中取出6个人的夫妇均不相邻的圆排列又有多少
种？
组合数学试题 共 6 页 ，第 2 页
组合数学试题 共 6 页 ，第 3 页
电子科技大学试题答案
考试时间：2006年秋 考试对象：硕士
考试科目：组合数学 班
级：
一．填空题（每空2分，共20分）
1． （1）F(3,4)=C(6,
4)=15；（2）F(3,6)-1=C(8,2)-1=27；（3）
2． R(C) =
(1+3x+x
2
)(1+2x)=
1+5x+7x
2
+2x
3
3．（1）
(1+x
2
+x
4
+…)(x+x
3
+…)
(1+x
2
+…);
18!
18!
17
；（4）
5!•6!•7!
5!•6!•7!
2
1x1x<
br>
2232
1x1x
1x
(1x)(1x
)
x
2
x
4
xx
3
xx
2
L
)(L)(1L)
; （2）
(1
2!4!1!3!1!2!
e
x
e
x
e
x
e
x
x
e<
br>3x
e
x
e
224
4．（1）3；（2）90
二、（14 分） 给定重集B =
{3·A, 3·B, 4·C,10·D }。求B 的8-组合数。
解
令集合S为
{A,B,C,D}
的所有8-组合构成的集合。则有
|S|=F(4,8) = 165
令
A
1
表示S中至少含有4个A的元素构成的集合,
A
2
表示S中至少含有4个B的元素构
成的集合,
A
3
表示S中至少含有5个C的元素构成的集合, 于是
A
1
A
2
F
4,4
3
5,
A
1
IA
2
1,
3
A
3
F
4,3
20
A
1
IA
3
A
2
IA
3
A
1
IA
2
IA
3
0
由容斥原理，所求的8-组合数为
A
1
I
A
2
I
A
3
S
A
i
A
i
I
A
j
A
1
I
A
2
IA
3
=165 – (35+35+20)+1= 76
i1ij
三.（14分）解 x
2
-6x-7=0 有根
x
1
= -1，x
2
=7 ，所以
a
n
*=c
1
(-1)
n
+
c
2
7
n
设
a
n
= A n(-1)
n
，代入原关系
A n(-1)
n
-6 A( n-1)(-1)
n
-1
-7 A( n-2)(-1)
n
-2
=(-1)
n
A n + 6A( n-1) - 7A( n-2) =1
组合数学试题 共 6 页 ，第 4 页
1
8
nn
所以
a
n
=(-1)
n
，
a
n
= c
1
(-1)
n
+
c
2
7
n
+ (-1)
n
88
令
n=2：2A +6 A=1
A =
c
1c
2
7
17
c
1
=6， c
2
=1
c7c
12
88
n
(-1)
n
8
∴ a
n
=
6(-1)
n
+ 7
n
+
四、（10分） 证明
因每点有3种颜色可选,故每列恰有9 种着色方案,现有10列,由鸽笼原
理,知必有两列着色相同.
a
n
2•3
n1
a
n1
a
n
a
n1
2a
n2
23
n2
五、（16分）解 (1)
或者
a2
a2,a4
2
1
1
x
2
x4
xx
3
xx
2
L)(L)(1L)
（2）f
e
(x) ＝ 2
(1
2!4!1!3!1!2!
ex
e
x
e
x
e
x
x
e
3x
e
x
e
= ＝
2
22
2
[3
n
(1)
n
]
x
n<
br>=
2n!
n0
3
n
(1)
n
所以
a
n
2
六、（14分） 解
取全集S为用4种色对7个小方格的着色方案构成的集合。
设A
1
为S中着红色的小
方格的个数为2的着色方案的集合，A
2
为S中着黄色的小方格的
个数为2的着色方案
的集合，A
3
为S中着绿色的小方格的个数为2的着色方案的集合。有
S4
＝16384
A
i
=
C(7,2)3
5
= 5103, i＝1,2,3
7
A
i
A
j
= C(7,2)
C(5,2)2
3
= 1680 ，i, j∈{1,2,3}, i >
j；
A
1
A
2
A
3
= 630
∴ 所求数 =
A
1
A
2
A
3
=
16384 - 3×5103 + 3×1680 - 630 = 5485
七、（10分）解 1. 总数＝取到夫妇两人＋没有取到夫妇两人
＝C(5,4)[6!-2•5!] + 2•6! = 5•480 + 1440
=2400+1440=3840 或
总数 ＝ 总的排列数 － 夫妇相邻的排列方式数 ＝
P(7,6) - 5•2•5! = 5040 - 1200 = 3840
2.
分两种情况。情况1. 取出的6个人中恰含3对夫妇。计算如下
组合数学试题 共 6 页
，第 5 页
取全集S为6个人的圆排列的集合。令A
i
为S中第i对夫妇相邻的圆排列的集合，i = 1,2,3。
有 |
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。由容斥原理
A
1
A
2
A
3
=
120－3•48＋3•24－16 ＝32
情况2. 取出的6个人中恰含2对夫妇。此时取6人的
方式有6种，对取定的每一种取全集S
为6个人的圆排列的集合。令A
i
为S
中第i对夫妇相邻的圆排列的集合，i = 1,2。有
| S | = 5！＝120, |
A
i
| = 2•4！＝48， i = 1,2；|
A
1
∩A
2
| ＝4•3！＝24。由容斥原理
A
1
A
2
= 120－2•48＋24 ＝48
所以此类总数为 6•48＝288 最终结果为: 32 ＋
288＝320
组合数学试题 共 6 页 ，第 6 页