辩论赛辩词-windows7没声音

组合数学卢习题答案


【篇一：005_2009组合数学_计算机科学与技术学院】

t>太原理工大学

博士研究生入学考试专业基础课考试大纲

一、 参考书目

1. 《组合数学》(第4版)，卢开澄，卢开明著，清华大学出版社，
2011

二、 考查要点

一、组合数学基础

1.加法法则和乘法法则

2.排列与组合及其应用

3.组合等式及其组合意义

4.排列、组合的生成算法

ng公式

重点：排列与组合及其应用、组合等式及其组合意义

二、递推关系与母函数

1. 递推关系

2. 母函数及其性质

3. 指数型母函数

4. 整数的拆分

5. 常系数线性递推关系

6. stirling数和catalanta数

重点：母函数及其应用

三、容斥原理

1. 容斥原理

2. 容斥原理的应用

3. 棋盘多项式与有限制条件的排列

4. 有禁区的排列

5. 广义的容斥原理及其应用

6. 容斥原理的推广

重点：容斥原理的应用

四、鸽巢原理

1. 鸽巢原理

2. 鸽巢原理的应用

3. 鸽巢原理的推广

4. ramsey数

重点：鸽巢原理的应用

1. 群论基础

2. 置换群

3. 伯恩赛德（burnside）引理

【篇二：组合试题及答案08[1].11_工硕_】


> ??

效

??

???无???

???内

???题???

???以

????

答??

????

?线?

?内??

???封????

???以?????密???????? ???答?????题?????无?????
效????????（考试时间： 2 小时） 课程名称组合数学 教师卢光
辉、杨国武 学时40 学分 2教学方式 讲授 考核日期 2008 年 11
月 26 日 成绩 考核方式： （学生填写） 名 学 院 学 姓 名学 号
姓 错误！未找到引用源。、（16 分）求方程??x1?x2?x3?x4?10
的正整数解的?1?x1?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-组合数为 31?2?3?s??ai??ai?aj?a1?a2?a3i?1i?j
-----------------3分 =56 – (4+1+20) = 31 -----------------1分二、（16

分） 现有一项目，全国4个片 区共28家单位申报，其中，西南片区
有5家，华北片区有8家，华东片区有4家，华南片区有11家。 假
定同一片区的各个单位不加以区别，现在要从中选取8家单位入围。
（1）问理论上有多少种不同的选取方案？ （2）现为了考虑不同片
区的特殊情况，如果西南片区至少有1家入围，华北片区至少有 组
合数学试题 共 5 页 ，第 1 页

??

??

??

?

?

效

?

?

?

?

?

无

?

?

?

?

?

题

?

?

院?

学??

答

?

?

?

?

?

内

?

?

?

名??

姓以

?

?

?

?

?

线

?

?

?

?

?

封

?

?

号??

学?密

??

??

??

?

?2家入围，问理论上有多少种不同的选取方案？ 解 （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-组合数为 a1?a2?s??2i?1ai??|ai?aj|---
-------------2分 =165 – (10+20)= 135 -----------------1分 （2）设ar
为选取r家入围的方案数，故(a1,a2,?,ar,?)的母函数为
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) 组合数学试题 共 5 页 ，第 2 页

＝1?8x?22x?24x?10x?x

-----------------6分

所以安排方案数为

= 21

即共有21种。 -----------------1分

四、（10分）一位女主人宴请5位男士和4位女士，该女主人有
多少种方法让所有男士和女士（包含该 女主人）围一张圆桌（男女）
交替就坐？

解：先将5个男的围圆桌而坐，其就坐方式为23455! ，－4分 5

然后加入一个女的有5种方式，再加第2个女的就有 4种方式，加
入第3个女的就有3种方式，……加入第5个女的只有1种方式，

－4分

故由乘法规则知，其就坐方式共有：

5!?5?4?3?2?1?4!?5! ＝2880－2分 5

五、（12分）解下列递归关系

?a?an?1?2an?2?n ?a1?1 , a2?3

解 其特征方程为：

x2?x?2?0. -----------------4分 特征根

------2分 通解

an?c1(?1)n?c22n

.----------------- 2分

由初始条件得

?c1?(?1)?c2?2?1?22c?(?1)?c?2?32?1

解得 -----------------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－x

9xe10x?e8x

?e? 22

n1nnx= ?(10?8) n!n?02?

所以 an = 1(10n?8n） ，n≥1 -----------------3分 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,?,ar,?)对应的指数母函数为：-----------------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?
24

n1rrrrrrrx??(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?1r?0 ?(7?8?12?7?15?6?16?5?9?4?4
?3?2) ?4? r?0?0

-----------------1分

八、（6分）设an为边长是整数且最大的边长为n的不全等的三角
形的个数，试建立

。 an的递规关系（不需要求解）

解：

?(n?1)24n是奇数an?? n是偶数?(n?2)l4

纠错：n为偶数an=（n+2）n4

―――――――――――――――――过程4分，结果2分；如果
只有结果，可以给5分。

组合数学试题 共 5 页 ，第 5 页

【篇三：组合试题及答案06】


p> … 效

… … … … … 无 … … … …

… 题 … …院… 学…… 答 … … … … … 内 … … … 名……
姓以 … … … … … 线 … … … … … 封 … … 号…… 学…
密……………………

（考试时间：至，共 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个球的方式数为an，有序 地取出n个球的方式数为bn，
但均需满足红球的数量为偶，黄球的数量为奇，则

(1) 由组合意义写出的{an}的普通母函数为；

求和后的母函数为。

组合数学试题 共 6 页 ，第 1 页

效……………………

(2)由组合意义写出的{bn}的指数母函数为

求和后的母函数为。

4．（1） 将6个无区别的球放入3个无区别的盒子中且盒子不空的
放法数为 。

… … … ……

无 … … … … … 题 … …院… 学…… 答 … … … … …
内 … … … 名…… 姓以 … … … … … 线 … … … … …
封 … … 号…… 学…密…………

?a ?n?6an?1?7an?2?(?1)n

???

a,a7

0?71?

8

四、（10分）用三种颜色对下图的小圆点着色，证明必存在两列，
其着色完全相同。

五、（16分） 设长为n的三元序列（即用0,1,2组成序列）中1与
2的个数之和为奇的序

列个数为an。

1．试建立{an}的递归关系（不要求解出）。

2．用另一方法（即不用解递归关系的方法）求出an。

六、（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)(1+2x)= 1+5x+7x+2x3．（1）
(1+x+x+…)(x+x+…) (1+x+…);

2

4

3

2

2

2

3

18!5!?6!?7!

；（4）

?17

??

5!?6!?7!?218!??? ?

11?x

2

?

x1?x

2

?

11?x

?

x

(1?x)(1?x)

3

2

（2）(1?

x

2

2!

?

x

4

4!

??)(

x1!

?

x

3

3!

??)(1?

x1!

?x

?

x

2

2!

??);

e?e

2

x?x

?

e?e

2

x?x

?e?

x

e

3x

?e4

4．（1）3；（2）90

解 令集合s为{??a,??b,??c,??d}的所有8-组合构成的集合。则有
|s|=f(4,8) = 165

令 a1表示s中至少含有4个a的元素构成的集合, a2表示s中至
少含有4个b的元素构成的集合, a3表示s中至少含有5个c的元
素构成的集合, 于是

a1?a2?f?4,4??35,a1?a2?1,

a1?3?

??fa2?

a34??,3a?1

a?2

20

a?30

由容斥原理，所求的8-组合数为

3

a1?a2?a3?s?

?

i?1

ai?

?

i?j

ai?aj?a1?a2?a3=165 – (35+35+20)+1= 76

三.（14分）解 x2-6x-7=0 有根 x1= -1，x2=7 ，所以 an*=c1(-
1)n+ c27n

设an= 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 页

令 n=2：2a +6 a=1 ? a =所以 an=

n8

18

n8

(-1)n， an= c1(-1)n + c27n + (-1)n

?

?c1?c2?7??17 ? c1=6， c2=1 ?c?7c??2?1

88?

n8

∴ an= 6(-1)n+ 7n+(-1)n

四、（10分） 证明 因每点有3种颜色可选,故每列恰有9 种着色方
案,现有10列,由鸽笼原理,知必有两列着色相同.

?an?2?3n?1?an?1?an?an?1?2an?2?2?3n?2

五、（16分）解 (1) ? 或者?

?a1?2,a2?4?a1?2

（2）fe(x) ＝ 2(1?

x

2

2!

?

x

4

4!

??)(

x1!

?

x

3

3!e

??)(1?

x1!

?

x

2

2!

??)

＝2

e?e

2

?

n

x?x

?

e?e2

n

x?x3x

?e=

x

?e2

?x

=

?

n?0

[3?(?1)]x

2

n

n!

n

所以 an?

3?(?1)

2

n

六、（14分） 解 取全集s为用4种色对7个小方格的着色方案构
成的集合。

设a1为s中着红色的 小方格的个数为2的着色方案的集合，a2为
s中着黄色的小方格的个数为2的着色方案的集合，a3为 s中着绿
色的小方格的个数为2的着色方案的集合。有

s?4＝16384ai= c(7,2)35 = 5103, i＝1,2,3

ai?aj= c(7,2) c(5,2)2 = 1680 ，i, j∈{1,2,3}, i j；a1?a2?a3= 630

3

7

七、（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 页