………………… … 效
… … … … … 无 … … … …
… 题 … …院… 学…… 答 … … … … … 内 … … … 名…… 姓以 … … … … … 线 … … … … … 封 … … 号…… 学…密…………………… 电子科技大学研究生试卷
（考试时间： 至 ，共 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+17x2+18x3+8x4+x5 -----------------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 分）求方程??x1?x2?x3?x4?13?3?x1?6,2?x 的正整数解的个数。
2?6,x3?2解 等价于求集合S0＝{3.A,4.B,1.C,∞.D}的所有6-组合构成的集合。-----------------4分
令集合S为{??A,??B,??C,??D}的所有6-组合构成的集合。 -----------------2分
则有 |S|=F(4,6) = 84。
令 A1表示S中至少含有4个A的元素构成的集合, A2表示S中至少含有5个B的元素构成的集合, A3表示S中至少含有2个C的元素构成的集合, -----------------4分 于是
|A1|?F(4,2)?10,|A2|?F(4,1)?4,|A3|?F(4,4)?35 |A1?A3|?1
|A1?A2|?|A2?A3|?|A1?A2?A3|?0 -----------------2分
由容斥原理，所求的5-组合数为
3A1IA2IA3?S??Ai??AiIAj?A1IA2IA3i?1i?j -----------------3分
=84– (10＋4+35)＋1 = 36 -----------------1分
四、（14分）解下列递归关系
??an?5an?1?14an?2?(?2)n ?a0?2,a1?5解 对应的齐关系的特征方程 x2-5x-14=0 -----------------3分 有根 x1 = 7，x2 = -2。 -----------------1分
故齐关系的通解为a*n=c17n+c2(-2)n -----------------1分
设特解 an= An(-2)n，代入原关系：An(-2)n -5A(n-1) (-2)n-1-14A(n-2) (-2)n-2 = (-2)n
-----------------3分
? A = 22n（－2）n9 ? an =
9 -----------------2分 ∴ an = a*n+
a = c2n（－2）nn17n+c2(-2)n + 9 -----------------1分
组合数学试题 共 5 页 ，第 2 页
?c1?c2?2?由初值得 ? ? 47c1?2c2－?5?9?85?c?1??81 -----------------2分 ??c?772?81?n2n（－2）85n77∴ an = 7+ (-2)n + -----------------1分
98181
五、（12分）求1出现奇数次且2出现偶数次的n位十进制数的个数。
解：
设an是由0,1,……,9组成的满足“1出现奇数次”且“2出现偶数次”的长为n的序列的个数， -----------------2分 则an的指数母函数为：
xx3x2x4xx2ex－e－xex＋e－x8xe10x－e6x8fe(x) = (???)(1? ???)(1＋???)??e?1!3!2!4!1!2!224n1nnx=?(10?6) -----------------4分 n?04n!?1n ，n≥1 -----------------3分 (10?6n）4以0为首项的长为n的序列有an－1个，在上述序列中去掉以0为首项的长为n的序列便可得到1出现奇数次且2出现偶数次的n位十进制数的个数： -----------------2分 所以 an =
1an－an－1＝(9?10n－1?5?6n－1） -----------------1分
4 六、（14分）求由数字0，1，2，3，4，5，6，7组成的r位数中，1和5都出现偶数次，2和6至少出现一次的r位数的个数。
解：这是一个排列问题。设满足条件的r位数字串的个数为ar，则序列(a1,a2,L,ar,L)对应的指数母函数为： -----------------3分
x2x4xx2xx2???)2(???)2(1＋???)4 -----------------4分 fe(x) = (1?2!4!1!2!1!2!ex?e－x2xe8x?2e7x?3e6x?4e5x?3e4x?2e3x?e2x24x?()(e?1)e?
24n1rrrrrrrx??(8?2?7?3?6?4?5?3?4?2?3?2)
n!n?04? 组合数学试题 共 5 页 ，第 3 页
所以
1ar＝(8r?2?7r?3?6r?4?5r?3?4r?2?3r?2r) -----------------3分
4首位取0的r位数字串的个数为ar?1，故所求的r位数的个数为ar－ar?1＝
-----------------2分
?1r?1r?1r?1r?1r?1r?1r?1?(7?8?12?7?15?6?16?5?9?4?4?3?2) r?0 ?4??0 r?0 -----------------2分；如果没有针对r=0单独结果的，只得1分
七、（6分）设an表示一个凸n边形被它的对角线划分成互不重叠的区域个数(没有三条对角线在该n边形内交于一点)。试建立an的递规关系（不需要求解）。
解：
?n?1?an?an?1??? 3???n?2,n>3.
??其中： a3?1
―――――――――――――――――过程4分，结果2分。
八、（14分）若7个人中有3对夫妇，试问从中取出6个人的夫妇均不相邻的圆排列有多少种？
解：分两种情况。
情况1. 取出的6个人中恰含3对夫妇。 -----------------1分 计算如下:
取全集S为6个人的圆排列的集合。令Ai 为S中第i对夫妇相邻的圆排列的集合，i = 1,2,3。有 -----------------1分 | S | = 5！＝120, | Ai| = 2?4！＝48， i = 1,2,3； | Ai∩Aj | = 4?3！＝24（i j = 1,2,3；i ? j）；| A1∩A2∩A3 | ＝ 16。 -----------------2分 由容斥原理 -----------------1分 A1?A2?A3 = 120－3?48＋3?24－16 ＝32 -----------------1分
情况2. 取出的6个人中恰含2对夫妇。 -----------------1分 此时取6人的方式有6种，对取定的每一种取全集S为6个人的圆排列的集合。令
组合数学试题 共 5 页 ，第 4 页
Ai 为S 中第i对夫妇相邻的圆排列的集合，i = 1,2。 -----------------2分
有
| S | = 5！＝120, | Ai| = 2?4！＝48， i = 1,2；| A1∩A2 | ＝4?3！＝24。---------------1分 由容斥原理 -----------------1分 A1?A2 = 120－2?48＋24 ＝48 -----------------1分 所以此类总数为 6?48＝288 -----------------1分 最终结果为: 32 ＋ 288＝320 -----------------1分
组合数学试题 共 5 页 ，第 5 页
组合数学 试题及答案09
