………………… … 效
… … … … … 无 … … … …
… 题 … …院… 学…… 答 … …… …… …… …… 内… …… …… …… 名…效 …… 以… 姓 …… …… …… …无 …… 线… …… …… …… …题 …… 封… 院 …… …… 学 号…… …答 学 …… 密… …… …… …… …内 …… …… 名…………… 姓以 … … … … … 线 电子科技大学研究生试卷
（考试时间： 至 ，共 2 小时）
课程名称 组合数学 教师 学时 40 学分 2 教学方式 讲授 考核日期 2008 年 11 月 26 日 成绩 考核方式： （学生填写）
一、（16 分）求方程??x1?x2?x3?x4?101?x 的正整数解的个数。
?1?4,2?x2?6,0?x3?2解 等价于求集合S0＝{3.A,4.B,1.C,∞.D}的所有5-组合构成的集合。-----------------4分
令集合S为{??A,??B,??C,??D}的所有5-组合构成的集合。 -----------------2分 则有 |S|=F(4,5) = 56。
令 A1表示S中至少含有4个A的元素构成的集合, A2表示S中至少含有5个B的元素构成的集合, A3表示S中至少含有2个C的元素构成的集合, -----------------4分 于是
|A1|?F(4,1)?4,|A2|?F(4,0)?1,|A3|?F(4,3)?20
|A1?A2|?|A1?A3|?|A2?A3|?|A1?A2?A3|?0 -----------------2分
由容斥原理，所求的5-组合数为
3A1IA2IA3?S??Ai??AiIAj?A1IA2IA3i?1i?j -----------------3分
=56 – (4+1+20) = 31 -----------------1分 二、（16 分） 现有一项目，全国4个片区共28家单位申报，其中，西南片区有5家，华北片区有8家，华东片区有4家，华南片区有11家。假定同一片区的各个单位不加以区别，现在要从中选取8家单位入围。
（1）问理论上有多少种不同的选取方案？
（2）现为了考虑不同片区的特殊情况，如果西南片区至少有1家入围，华北片区至少有
2家入围，问理论上有多少种不同的选取方案？
解 （1）
组合数学试题 共 5 页 ，第 1 页
………………… … 效 … … … … … 无 … … … … … 题 … …院… 学…… 答 … … … … … 内 … … … 名…… 姓以 … … … … … 线 … … … … … 封 … … 号…… 学…密……………………等价于求集合S0＝{5.A,8.B,4.C,11.D}的所有8-组合构成的集合。-----------------2分
令集合S为{??A,??B,??C,??D}的所有8-组合构成的集合。则有 |S|=F(4,8) = 165。 令 A1表示S中至少含有6个A的元素构成的集合, A2表示S中至少含有5个C的元素构成的集合， -----------------2分 于是
|A1|?F(4,2)?10,|A2|?F(4,3)?20,
|A1?A2|?0 -----------------1分
由容斥原理，所求的9-组合数为
A21?A2?S??i?1Ai??|Ai?Aj| ----------------2分
=165 – (10+20)= 135 -----------------1分
（2）设ar为选取r家入围的方案数，故(a1,a2,L,ar,L)的母函数为
f(x)?(x?x2?x3?x4?x5)?(x2?x3?...?x8)?(1?x?x2?...?x4)?(1?x?x2?...?x11)
-----------------5分
?x3?...?16x8?... -----------------2分
因此理论上有54种不同的选取方案。 -----------------1分
三、(16分) 假如未来连续的5届奥运会（简称第一届到第五届）分别由五大洲的一个国家承办，每个大洲承办一次。根据具体情况，亚洲不能承办第一届和第二届，欧洲不能承办第二届和第三届，非洲不能承办第三届，北美洲不能承办第四届和第五届，南美洲不能承办第五届。问未来的5届奥运会有多少种不同的安排方案？ 解 原问题可模型化为一个5元有禁位的排列. 其禁区棋盘C如下图的阴影部分。 -----------------5分
由图,可得C的棋盘多项式为 R(C)=
1 2 3 4 5 =(1?3x?x2)?(1?5x?6x2?x3) A B ＝1?8x?22x2?24x3?10x4?x5C 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!?5?4?3?2?1?4!?5! ＝2880 －2分 5 五、（12分）解下列递归关系
?an?an?1?2an?2 ?
a?1 , a?32?1解 其特征方程为：
x2?x?2?0. -----------------4分
特征根
x1??1,x2?2. -----------------2分
通解
an?c1(?1)n?c22n由初始条件得
. -----------------2分
?c1?(?1)?c2?2?1?22?c1?(?1)?c2?2?3解得
-----------------2分
12c1?,c2?33. -----------------1分
该递推关系的解为
组合数学试题 共 5 页 ，第 3 页
12an?(?1)n?2n?33 -----------------1分
六、（12分）试用母函数法求出现偶数个5的n位十进制数的个数。
解：
设an是由0,1,……,9组成的满足“5出现偶数次”的长为n的序列的个数，
-----------------2分 则an的指数母函数为：
x2x4xx2???)(1＋???)9 -----------------4分 fe(x) = (1?2!4!1!2!ex?e－x9xe10x?e8x?e?
22n1nnx= ?(10?8)
n!n?02?所以 an =
1 ，n≥1 -----------------3分 (10n?8n）2以0为首项的长为n的序列有an－1个，在上述序列中去掉以0为首项的长为n的序列便可得到出现偶数个5的n位十进制数的个数： -----------------2分 an－an－1＝
1(9?10n－1?7?8n－1） -----------------1分 2 七、（12分）求由数字0，1，2，3，4，5，6，7组成的r位数中，3和5都出现偶数次，2和4至少出现一次的r位数的个数。
解：这是一个排列问题。设满足条件的r位数字串的个数为ar，则序列
(a1,a2,L,ar,L)对应的指数母函数为： -----------------2分
fe(x) =
x2x4xx2xx2(1????)2(???)2(1＋???)4 -----------------4分
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 页 ，第 4 页
所以
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 -----------------1分 八、（6分）设an为边长是整数且最大的边长为n的不全等的三角形的个数，试建立
an的递规关系（不需要求解）。
解：
?(n?1)2/4 n是奇数an??
n是偶数?(n?2)l/4 纠错：n为偶数An=（n+2）n/4
―――――――――――――――――过程4分，结果2分；如果只有结果，可以给5分。
组合数学试题 共 5 页 ，第 5 页
组合数学 试题及答案
