作业习题答案
习题二
证明：在一个至少有2人的小组中，总存在两个人，他们在组内所认识的人数相同。
证明：
假设没有人谁都不认识：那么每个人认识的人数都为[1,n-1]，由鸽巢原理知，n个人认识的人数有n-1种，那么至少有2个人认识的人数相同。
假设有1人谁都不认识：那么其他n-1人认识的人数都为[1,n-2]，由鸽巢原理知，n-1个人认识的人数有n-2种，那么至少有2个人认识的人数相同。
证明：平面上任取5个坐标为整数的点，则其中至少有两个点，由它们所连线段的中点的坐标也是整数。
证明：
方法一：
有5个坐标，每个坐标只有4种可能的情况：（奇数，偶数）；（奇数，奇数）；（偶数，偶数）；（偶数，奇数）。由鸽巢原理知，至少有2个坐标的情况相同。又要想使中点的坐标也是整数，则其两点连线的坐标之和为偶数。因为奇数+奇数 = 偶数；偶数+偶数=偶数。因此只需找以上2个情况相同的点。而已证明：存在至少2个坐标的情况相同。证明成立。
方法二：
对于平面上的任意整数坐标的点而言，其坐标值对2取模后的可能取值只有4种情况，即：(0,0) ,(0,1) ,(1,0), (1,1)，根据鸽巢原理5个点中必有2个点的坐标对2取模后是相同类型的，那么这两点的连线中点也必为整数。
一次选秀活动，每个人表演后可能得到的结果分别为“通过”、“淘汰”和“待定”，至少有多少人参加才能保证必有100个人得到相同的结果
证明：
根据推论，若将3*（100-1）+1=298个人得到3种结果，必有100人得到相同结果。
将一个矩形分成(m+1)行
1
1
2
m
m
+
??
+
?
??
列的网格每个格子涂1种颜色，有m种颜色可以选择，
证明：无论怎么涂色，其中必有一个由格子构成的矩形的4个角上的格子被涂上同一种颜色。
证明：
（1）对每一列而言，有（m+1）行，m种颜色，有鸽巢原理，则必有两个单元格颜色相同。
（2）每列中两个单元格的不同位置组合有
1
2
m+
??
?
??
种，这样一列中两个同色单元格的位
置组合共有
1
2
m
m
+
??
?
??
种情况
（3）现在有112m m +??
+
???
列，根据鸽巢原理，必有两列相同。证明结论成立。 证明：从S={1,3,5,…,599}这300个奇数中任意选取101个数，在所选出的数中一定存在2个数，它们之间最多差4。 证明：
将S 划分为{1,3,5}，{7,9,11}……,{ 595,597,599}共100组，由鸽巢原理知任意选取101个数中必存在2个数来自同一组，即其差最多为4.
证明：从1~200中任意选取70个数，总有两个数的差是4，5或9。 设从1~200中任意选取的70个数构成一组，即 第一组： 1270,,,a a a K ；
第二组： 12704,4,,4a a a +++K ； 第三组：12709,9,,9a a a +++K ；
显然，这三组数均在1~209之间，且共有3*70=210个数，根据鸽巢原理一定有两个数相等，又因为任取的这70个数均不相同，所以这2个相等的数一定来自不同组，根据不同组的分布讨论如下：
1） 如果这两个数分别来自第一组和第二组，则有4j i a a =+； 2） 如果这两个数分别来自第一组和第三组，则有9j i a a =+； 3） 如果这两个数分别来自第二组和第三组，则有5j i a a =+；
得证。
习题三
3.8 确定多重集{3,4,5}M a b c =???的11-排列数
11!11!11!
277203!4!4!3!3!5!2!4!5!
++=
3.9 求方程123420x x x x +++=，满足12342,0,5,1x x x x ≥≥≥≥-的整数解的个数。
14416803+-??= ???
3.10 架上有20卷百科全书，从中选出4卷使得任意两本的卷号都不相邻的选法有多少
种
解：n=20，r=4，1204117238044n r r -+-+??????
===
? ? ???????
3.17 一局乒乓球比赛中，运动员甲以11:7战胜运动员乙，若在比赛过程中甲从来没有
落后过，求有多少种可能的比分记录
解：根据题意，相当于求从点(0,0)到点(11,7)且从下方不穿过y=x 的非降路径数，即为：
11711171(117)!(1171)
-13260 10 12(111)!7!+-+-????+-+=
= ? ?+????
3.21 1)会议室中有2n +1个座位，现摆成3排，要求任意两排的座位都占大多数，求有多少种摆法 解：
(1)
方法1：如果没有附加限制则相当于把2n+1个相同的小球放到3个不同的盒子里，有
213123 3-1 2n n ++-+????= ? ?????
种方案，而不符合题意的摆法是有一排至少有n+1个座位。这相当于将n+1个座位先放到3排中的某一排，再将剩下的2n+1-(n+1)=n 个座位任意分到3排
中，这样的摆法共有21(1)31233 2 2n n n +-++-+?????=? ? ?????
种方案，所以符合题意的摆法
有：
23213 2 2 2n n n +++??????
-?= ? ? ???????
方法2：设第一排座位有x 1个，第二排座位有x 2个，第三排座位有x 3个。x 1+x 2+x 3=2n+1，且x 1+x 2≥(2n+1)/2，x 1+x 3≥(2n+1)/2，x 2+x 3≥(2n+1)/2，即x 1+x 2≥n+1，x 1+x 3≥n+1，x 2+x 3≥n+1，令y 1= x 1+x 2-n-1，y 2= x 1+x 3-n-1，y 3= x 2+x 3-n-1，可知y 1+y 2+y 3=2(2n+1)-3(n+1)=n-1且y i ≥0，1≤i ≤3。显然，x 方程满足要求的解与y 方程非负整数解一一对应，有
1311312n n -+-+????= ? ?-????
种。 方法3：要求每行非空
如果没有附加限制则相当于把2n+1个相同的小球放到3个不同的盒子里，不允许为空，有2112 3-12n n +-????
=
? ?????
种方案，而不符合题意的摆法是有一排至少有n+1个座位。这相当于
将n 个座位先放到3排中的某一排，再将剩下的2n+1-n=n+1个座位任意分到3排中，每排
不允许为空，这样的摆法共有21133 22n n n +--????
?=? ? ?????
种方案，
所以符合题意的摆法有： 21322 2n n n +??????
-?= ? ? ???????
(2)会议室中有2n 个座位，现摆成3排，要求任意两排的座位都占大多数，求有多少种摆法 解：
(2)
方法1：如果没有附加限制则相当于把2n 个相同的小球放到3个不同的盒子里，有
23122 2 2n n +-+????= ? ?????
种方案，而不符合题意的摆法是有一排至少有n 个座位。这相当于将n 个座位先放到3排中的某一排，再将剩下的2n-n=n 个座位任意分到3排中，这样的摆法共有231233 2 2n n n -+-+????
?=?
? ?????
种方案。需要注意的是，三排中如果任意两排都是
n 个座位共有3种情况，这3种情况在23 2n +??
? ???
中被重复计算了2次，因此需要将重复减去的3次加上。所以符合题意的摆法有：
222133 2 2 2n n n ++-??????
-?+= ? ? ???????
方法2：设第一排座位有x 1个，第二排座位有x 2个，第三排座位有x 3个。x 1+x 2+x 3=2n ，且x 1+x 2≥n +1，x 1+x 3≥n +1，x 2+x 3≥n +1，令y 1=x 1+x 2-n-1，y 2=x 1+x 3-n-1，y 3=x 2+x 3-n-1，可知y 1+y 2+y 3=2(2n)-3n-3=n-3且y i ≥0，1≤i ≤3。显然，x 方程满足要求的解与y 方程非负整数解一一对应，有
3311312n n -+--????= ? ?-????
种。
方法3：要求每行非空
如果没有附加限制则相当于把2n 个相同的小球放到3个不同的盒子里，不允许为空，有21212 2n n --????
=
? ?????
种方案，而不符合题意的摆法是有一排至少有n 个座位。这相当于将
n-1个座位先放到3排中的某一排，再将剩下的2n-(n-1)=n+1个座位任意分到3排中，每排不允许为空，这样的摆法共有2(1)13322n n n ---????
?=? ? ?????
种方案，所以符合题意的摆
法有：
2113 222n n n --??????
-?= ? ? ???????
3.24 n(n ≥2)个不同的球分给甲、乙、丙3人，使得甲至少分得两个球，有多少种不同的分法 解：1
2322
2n
n
n
n n i i n n i --=??--= ???
∑
3.25 24个相同的球分堆，使得每堆的球不少于5，有多少种不同的分堆方法 方法1：
24
5
24i
i i k
=?=∑
55266224242243(1())(1())(1()())
x x x x x x x ++++++++++L L L L 56241
(1)(1)(1)
x x x =
---L
每堆去掉4个球，剩余球分堆的方法数
5
1
(244,)(20,1)(16,2)(12,3)(8,4)(4,5)18125026
i B i i B B B B B =-=++++=++++=∑
其中
(12,3)(9,1)(9,2)(9,3)
14(6,1)(6,2)(6,3)1413(3,1)(3,2)(3,3)141311112
B B B B B B B B B B =++=++++=++++++=++++++=
(8,4)(4,1)(4,2)(4,3)(4,4)12115B B B B B =+++=+++=
习题四
4.3 一项对于A,B,C 三个频道的收视调查表明，有20%的用户收看A ，16%的用户收看B ，14%
的用户收看C ，8%的用户收看A 和B ，5%的用户收看A 和C ，4%的用户收看B 和C ，2%的用户都看。求不收看A,B,C 任何频道的用户百分比
解：设性质P 1是收看A 频道的用户百分比；P 2是收看B 频道的用户百分比；P 3是收看C 频道的用户百分比；Ai={x|x ∈S ∧x 具有性质P i }，i=1,2,3。S 是受调查的所有用户的集合。
||1S =；
123||20%,||16%,||14%A A A ===
121323||8%,||5%,||4%A A A A A A ?=?=?= 123||2%A A A ??=
根据定理，有
123123121323123||||(||||||)(||||||)||1(20%16%14%)(8%5%4%)2%65%
A A A S A A A A A A A A A A A A ??=-+++?+?+?-??=-+++++-=
4.4 某杂志对100名大学新生的爱好进行调查，结果发现他们喜欢看球赛和电影、戏剧。其
中58人喜欢看球赛，38人喜欢看戏剧，52人喜欢看电影，既喜欢看球赛又喜欢看戏剧的有18人，既喜欢看电影又喜欢看戏剧的有16人，三种都喜欢看的有12人，求有多少人只喜欢看电影 解： 方法1：
设性质P 1喜欢看球赛；P 2喜欢看戏剧；P 3喜欢看电影。Ai={x|x ∈S ∧x 具有性质P i }，i=1,2,3。
S 是100名大学新生的集合。
||100S =
123||58,||38,||52A A A ===
121323||18,||?,||16A A A A A A ?=?=?= 123||12A A A ??=
由题意可得，这100名大学生中每人至少有三种兴趣中的一种，
12312312132312313||||(||||||)(||||||)||100(583852)(18||16)120A A A S A A A A A A A A A A A A A A ??=-+++?+?+?-??=-++++?+-= 所以可得既喜欢看球赛有喜欢看电影的人有
13||(583852)100(1816)1226A A ?=++--++=
因此只喜欢看电影的人有
12331323123||||||||||A A A A A A A A A A A ??=-?-?+??
=52-(26+16)+12=22人 方法2：
1231212||||||||||100(5838)1822A A A S A A A A ??=--+?=-++=
A
C
B
65
方法3：
设只喜欢看球赛的人数为x ；设只喜欢看电影的人数为y ；喜欢看球赛和电影但不喜欢看戏
剧的人数为z ，则
1003858185216x y z x z y z ++=-??
+=-??+=-?
解得y=22，所以22人只喜欢看电影。
4.5 某人有六位朋友，他跟这些朋友每一个都一起吃过晚餐12次，跟他们中任二位一起吃
过6次晚餐，和任意三位一起吃过4次晚餐，和任意四位一起吃过3次晚餐，任意五位一起吃过2次晚餐，跟六位朋友全部一起吃过一次晚餐，另外，他自己在外吃过8次晚餐而没碰见任何一位朋友，问他共在外面吃过几次晚餐
解：设n 为在外面共吃过晚餐的次数，性质Pi(1i 6)表示他和第i 位朋友吃过晚餐，
Ai(1i 6)表示他和第i 位朋友吃过晚餐的次数。显然满足对称筛公式，其中
(1)12,(2)6,(3)4,(4)3,(5)2,(6)1,N N N N N N ======
由题可得方程：
123456
123456666666||12643218
A A A A A A n C C C C C C ?????=-?+?-?+?-?+?=解得吃饭次数为123456
6666661264321836C C C C C C ?-?+?-?+?-?+=
计算棋盘多项式。
解：
) = x*R()+R(
2
)+(1+x)*R( )
= x 3
+3x 2
+x+(1+x)[xR()+R()]
= x 3+3x 2+x+(1+x)[x(1+x)+(1+4x+2x 2
)]
球赛
戏剧
电影
12
6
4
16
14
26
22
= 5x3+12x2+7x+1
A,B,C,D,E五种型号的轿车，用红、白、蓝、绿、黑五种颜色进行涂装。要求A型车不能涂成黑色；B型车不能涂成红色和白色；C型车不能涂成白色和绿色；D型车不能涂绿色和蓝色；E型号车不能涂成蓝色，求有多少种涂装方案
解：
红
白
蓝
绿
黑
蓝
绿
白
红
黑
红
白
绿
蓝
黑
1.若未规定不同车型必须涂不同颜色，则：
????=
涂装方案43334432
2.若不同车型必须涂不同颜色，则：
禁区的棋盘多项式为：
=R()R()=(1+x)(xR()+R())
=(1+x)(xR()R()+R()R())
=(1+x)(x(1+2x) 2+(1+3x+x2)2)
=1+8x+22x2+25x3+11x4+x5
所以：
N =5!-r1×4!+r2×3!–r3×2!+r4×1!- r5×0!
=5！-8*4！+22*3！-25*2！+11*1！-1=20
习题五
5.1 求如下数列的生成函数。
（1）)1()1( k a k k ；（2）k
k k k a 2)1(-=；
（3）6+=k a k ； （4）)2(+=k k a k ；
（5）???
? ??+=k k n a k ； （6）3k k a ??
= ???；
解：
12
1
(1)()(1)(1)[(1)]'[
]'1(1)k
k
k k k k x A x k x x x x ∞
∞
+===-+=-==++∑∑ 2
2(2)()(1)2(2)(12)k
k
k
k k k k x
A x k x k x x ∞∞
==-=-=-=
+∑∑
222
66665(3)()(6)6(1)1(1)(1)
k
k
k k k k x x x x
A x k x kx x x x x x ∞∞∞
===+--=+=+=
+==----∑∑∑ 1
2
323
1
(4)()(2)(1)[
]''[]'1123(1)(1)(1)k
k k k k k x A x k k x x k k x
kx x x x x
x x x x
x x x ∞∞
∞
-====+=++=+---=
+=
---∑∑∑
1
01
(5)()(1)k k n k n k A x x k x ∞
-=+??== ?-??
∑ 323200
000234322332334
4
32111(6)()36623141(1)16(1)2(1)3(1)
4332426(1)(1)k k k k k
k k k k k k k k k A x x x k x k x kx
x x x x x x x x x x x x x x x x x x x x ∞
∞∞∞∞=====??-+===-+ ???+++=-+---++-++-+==--∑∑∑∑∑ 3
303333340(6)()33333(1)k k k k k k k k k k k k k k A x x x x x x
k k k x x x k x ∞
∞∞∞
-====∞
=????????==== ? ? ? ?--????????
+??== ?
-??
∑∑∑∑∑
5.3 已知数列{}k a 的生成函数是x
x x x A 31932)(2
--+=，求k a .
20
2392()32331313k k k x x A x x x x x x ∞
=+-==+=?+--∑
9
123
1
k n
n a n =?=??≠?
5.15
知数列{k a }的指数生成函数是2()5x
x G x x e =+，求k a 。
22
0()5252!!
k
x
x k x x G x x e k ∞==+=+∑
72
52k k a k =?=?
≠?
平面上有n 条直线，它们两两相交且沿有三线交于一点，设这n 条直线把平面分成
()f n 个区域，求()f n 的递推关系并求解.
解：设n-1条直线把平面分成(-1)f n 个区域，则第n 条直线与前n-1条直线都有一个交点，即在第n 条直线上有n-1个交点，并将其分成n 段，这n 段又把其所在的区域一分为二。
0101#11()(1),(2) (1)2 10 1 *()()12
(1)()2
1(1) ()12
f n f n n n f x x f n b b n n b b n n
f n c c n n f n =-+≥?∴?
=?-===+==+=+
=+∴=+
齐次特征方程：特征根：非齐次特解：代入递推关系得：，
代入递推关系得：
一个1n ?的方格图形用红、蓝两色涂色每个方格，如果每个方格只能涂一种颜色，且不允许两个红格相邻，设()f n 有种涂色方案，求()f n 的递推关系并求解.
解：
设f (n )为n ?1的方格图形的涂色方案。
当n=1时，f (1)=2，即一个方格有红、蓝两种涂色方案。 当n=2时，f (2)=3，即两个方格有（红、蓝），（蓝、红）、（蓝、蓝）三种涂色方案。由于不允许两个红格相邻，所以不存在（红、红）的情况。
当n>2时，如果第一个格子涂为蓝色，则剩余n-1个格子的涂色方案数为f (n -1)；如果第一个格子涂为红色，由于不允许两个红格相邻，所以第二个格子必为蓝色，则剩余n-2个格子的涂色方案数为f (n -2)。于是，当n>2时涂色方案数为f (n )= f (n -1)+ f (n -2)。
(1)2;(2)3;
() (-1) (-2).
f f f n f n f n ==??
=+? 先求解这个递推关系的通解，它的特征方程为
,012=--x x
解这个方程，得
.2
5
1,25121-=+=
x x 所以，通解为
.251251)(21n
n
c c n f ???
?
??-+???
? ??+
=
代入初值来确定1c 和2
c ，得
1
2122,3.
=+= 求解这个方程组，得
2
11,2c ?+=? ??
2
21.2
c ??=
?
???
所以，原递推关系的解为
3
3
()n n f n ++=?
?
（Λ,2,1,0=n ）.
核反应堆中有α和β两种粒子，每秒钟内1个α粒子可反应产生出3个β粒子，而1个β粒子又可反应产生出1个α粒子和2个β粒子.若在t =0s 时刻反应堆中只有1个α粒子，求t =100s 时刻反应堆里将有多少个α粒子和β粒子.
解：
设t 时刻反应堆中α粒子数为()f t ，β粒子数为()g t
212#1212()(1),(2)()3(1)2(1)(0)1,(0)0()3(2)2(1),(2)(0)0,(1)3 230 3,1
()3(1)3344
3 ()34t t f t g t n g t f t g t f g g t g t g t n g g x x x x g t c c c c g t =-≥??
=-+-??==?
=-+-≥??
==?--===-=?+?-==-
∴=?齐次特征方程：特征根：齐次通解：代入递推关系得：
，t 11
3
(1)43333 ()3(1)(1)4444
t t
t t t f t ---?-∴=?-?-=+?-
求下列n 阶行列式的值n d
2
100012100012000001
2
n d =?L L L
L L L L L L
解：当n=1时，122d == 当n=2时，221312
d =
=
当n>2时，-1-22n n n d d d =-
先求解这个递推关系的通解，它的特征方程为
2210,x x -+=
解这个方程，得
121.x x ==
所以，通解为
12()11.n n f n c c n =+?
代入初值来确定1c 和2c ，得
1212
2,
2 3.c c c c +=??+=?
求解这个方程组，得 11,c =21.c = 所以，原递推关系的解为
()1f n n =+ （Λ,2,1,0=n ）.
设h(n)表示n+2条边的凸多边形为它的对角线划分所得的区域数，其中假定没有二条对角线在凸多边形内有一公共点。定义h(0)=0，对n=l ，2，…，证明
1()(1)3n h n h n n +??
=-++ ???
证明：
如图所示，在凸n+2边形中，划出以任意两相邻边为边的三角形，例如△ABC 。则余下的是n+1个顶点的凸多边形，它的对角线划分所得的区域数为h(n-1)。由A 点引出的对角线共有n-1条，分△ABC 为n 块。下面我们计算一下由A 点引出的对角线对n+1条边的凸多边形划分所增加的区域数。
在n+1个顶点中仟取三个，不妨设为D ，F ，H ，其中必有一个顶点(这里是F)使得对角线AF 把D 和H 分在两边。所以对角线DH 必与对角线AF 相交。又由题意知，这个交点不会有其它对角线通过。这说明每新增加一个交点必与n+1个顶点中的三个顶点相对应。故新增加的交点数为C(n+1,3)个。
另外，从A 引出的每一条对角线上的交点数正好与这条对角线在凸n+1边形内截成的
线段数相同，而每一线段恰好把n+1边形内某一区域分为两个，故新增加区域数为C(n+1,3)个。所以有
1()(1)3n h n h n n +??
=-++ ???
这是一个线性常系数非齐次递推关系，可以求得
2(1)()42n n n h n +??+=+ ???
《组合数学》试题 姓名 学号 评分 一、填空题（每小题3分，共18分） 1、 红、黄、蓝、白4个球在桌上排种排法。成一圈，有 2、设P 、Q 为集合，则|P ∪Q| |P| + |Q|. 3、0max i n n i ≤≤????=?? ????? 。 4. 366个人中必有 个人生日相同。 5.的系数为的展开式中，342326 41x x x x i i ?? ? ??∑= 。 6.解常系数线性齐次递推关系的常用方法称为 法 。 二、单项选择题（每小题2分，共12分） 1、数值函数f = (1,1,1,...)的生成函数F(x) =（ ） A 、(1+x)n B 、1－x C 、(1－x)－1 D 、(1+x)－n 2、递推关系f(n) = 4f(n －1)－4f(n －2)的特征方程有重根2，则（ ）是它的一般解 。 A 、C 12n －1+C 22n B 、( C 1+C 2n)2n C 、C(1+n)2n D 、C 12n +C 22n . 3、由6颗不同颜色的珠子可以做成 （ ）种手链。 A 、720 B 、120 C 、60 D 、6
4、=??? ??-∑=n k k k n 0 )1(（ ）。 A 、2n B 、0 C 、n2n －1 D 、1 5、设F(x),G(x)分别是f 和g 的生成函数，则以下不成立的是（ ） 。 A 、F(x)+G(x) 是f+g 的生成函数 B 、F(x)G(x) 是fg 的生成函数 C 、x r F(x) 是S r (f)的生成函数 D 、F(x)－xF(x) 是?f 的生成函数. 6、在无柄茶杯的四周画上四种不同的图案，共有（ ）种画法。 A 、24 B 、12 C 、6 D 、3 三、 解答题（每小题10分，共70分） 1. 有4个相同的红球，5个相同的白球，那么这9个球有多少种不同的排列方 式？ 2. 公司有5台电视机，4台洗衣机，7台冰箱，现要把其中3台电视机，2台洗 衣机，4台冰箱选送到展销会，试问有多少种选法？ 3. 设S = {1, 3?2, 3?3, 2?4, 5}是一个多重集，那么由集合S 的元素能组成多少个 不同的四位数。 4.试求在1到300之间那些不能被3, 5和7中任何一个整除的整数个数。 5. 解非齐次递推关系 1201 693,20,1n n n a a a n a a --++=≥??==? 6. 将字母a,b,c,d,e,f,g 排成一行，使得模式beg 和cad 都不出现的排列总数是多少？ 7. 某次会议有10个代表参加，每一位代表至少认识其余9位中的一位，则10位代表中至少有两位代表认识的人数相等。
习题二证明：在一个至少有2人的小组中，总存在两个人，他们在组内所认识的人数相同。证明：假设没有人谁都不认识：那么每个人认识的人数都为[1,n-1]，由鸽巢原理知，n个人认识的人数有n-1种，那么至少有2个人认识的人数相同。假设有1人谁都不认识：那么其他n-1人认识的人数都为[1,n-2]，由鸽巢原理知，n-1个人认识的人数有n-2种，那么至少有2个人认识的人数相同。假设至少有两人谁都不认识，则认识的人数为0的至少有两人。
任取11个整数，求证其中至少有两个数的差是10的整数倍。证明：对于任意的一个整数，它除以10的余数只能有10种情况：0，1，…，9。现在有11个整数，由鸽巢原理知，至少有2个整数的余数相同，则这两个整数的差必是10的整数倍。证明：平面上任取5个坐标为整数的点，则其中至少有两个点，由它们所连线段的中点的坐标也是整数。证明：有5个坐标，每个坐标只有4种可能的情况：（奇数，偶数）；（奇数，奇数）；（偶数，偶数）；（偶数，奇数）。由鸽巢原理知，至少有2个坐标的情况相同。又要想使中点的坐标也是整数，则其两点连线的坐标之和为偶数。因为奇数+奇数= 偶数；偶数+偶数=偶数。因此只需找以上2个情况相同的点。而已证明：存在至少2个坐标的情况相同。证明成立。
一次选秀活动，每个人表演后可能得到的结果分别为“通过”、“淘汰”和“待定”，至少有多少人参加才能保证必有100个人得到相同的结果证明：根据推论2.2.1，若将3*（100-1）+1=298个人得到3种结果，必有100人得到相同结果。一个袋子里装了100个苹果、100个香蕉、100个橘子和100个梨。那么至少取出多少水果后能够保证已经拿出20个相同种类的水果证明：根据推论2.2.1，若将4*（20-1）+ 1 = 77个水果取出，必有20个相同种类的水果。
第二章作业答案 7. 证明，对任意给定的52个整数，存在两个整数，要么两者的和能被100整除，要么两者的差能被100整除。 证明 用100分别除这52个整数，得到的余数必为0, 1,…, 99这100个数之一。将余数是0的数分为一组，余数是1和99的数分为一组，…，余数是49和51的数分为一组，将余数是50的数分为一组。这样，将这52个整数分成了51组。由鸽巢原理知道，存在两个整数分在了同一组，设它们是a 和b 。若a 和b 被100除余数相同，则b a -能被100整除。若a 和b 被100除余数之和是100，则b a +能被100整除。 11. 一个学生有37天用来准备考试。根据过去的经验，她知道她需要不超过60小时的学习时间。她还希望每天至少学习1小时。证明，无论她如何安排她的学习时间（不过，每天都是整数个小时），都存在连续的若干天，在此期间她恰好学习了13小时。 证明 设从第一天到第i 天她共学习了i a 小时。因为她每天至少学习1小时，所以 3721,,,a a a 和13,,13,133721+++a a a 都是严格单调递增序列。因为总的学习时间 不超过 60 小时，所以6037≤a ，731337≤+a 。3721,,,a a a , 13,,13,133721+++a a a 是1和73之间的74个整数，由鸽巢原理知道，它们中存在相 同的整数，有i a 和13+j a 使得13+=j i a a ，13=-j i a a ，从第1+j 天到第i 天她恰好学习了13小时。 14. 一只袋子装了100个苹果、100个香蕉、100个桔子和100个梨。如果我每分钟从袋子里取出一个水果，那么需要多少时间我就能肯定至少已拿出了1打相同种类的水果？ 解 由加强形式的鸽巢原理知道，如果从袋子中取出451)112(4=+-?个水果，则能肯定至少已拿出12个相同种类的水果。因此，需要45分钟。 17. 证明：在一群1>n 个人中，存在两个人，他们在这群人中有相同数目的熟人（假设没有人与他/她自己是熟人）。 证明 因为每个人都不是自己的熟人，所以每个人的熟人的数目是从0到1-n 的整数。若有两个人的熟人的数目分别是0和1-n ，则有人谁都不认识，有人认识所有的人，这是不可能的。因此，这n 个人的熟人的数目是1-n 个整数之一，必有两个人有相同数目的熟人。 第三章作业答案 6. 有多少使下列性质同时成立的大于5400的整数？ (a) 各位数字互异。 (b) 数字2和7不出现。 解 因为只能出现数字0, 1, 3, 4, 5, 6, 8, 9，所以整数的位数至多为8。
组合数学试题集 一.简单题目 可以根据需要改成选择题或者填空题 1．在1到9999之间，有多少个每位上数字全不相同而且由奇数构成的整数？（参见课本21页） 解：该题相当于从“1，3，5，7，9”五个数字中分别选出1，2，3，4作排列的方案数； （1）选1个，即构成1位数，共有15P 个； （2）选2个，即构成两位数，共有25P 个； （3）选3个，即构成3位数，共有35P 个； （4）选4个，即构成4位数，共有4 5P 个； 由加法法则可知，所求的整数共有：12345555205P P P P +++=个。 2．一教室有两排，每排8个座位，今有14名学生，问按下列不同的方式入座，各有多少种做法？（参见课本21页） （1）规定某5人总坐在前排，某4人总坐在后排，但每人具体座位不指定； （2）要求前排至少坐5人，后排至少坐4人。 解：（1）因为就坐是有次序的，所有是排列问题。 5人坐前排，其坐法数为(8,5)P ，4人坐后排，其坐法数为(8,4)P ， 剩下的5个人在其余座位的就坐方式有(7,5)P 种， 根据乘法原理，就座方式总共有： (8,5)(8,4)(7,5)28449792000P P P =（种） （2）因前排至少需坐6人，最多坐8人，后排也是如此。 可分成三种情况分别讨论： ① 前排恰好坐6人，入座方式有(14,6)(8,6)(8,8)C P P ； ② 前排恰好坐7人，入座方式有(14,7)(8,7)(8,7)C P P ； ③ 前排恰好坐8人，入座方式有(14,8)(8,8)(8,6)C P P ；
各类入座方式互相不同，由加法法则，总的入座方式总数为： (14,6)(8,6)(8,8)(14,7)(8,7)(8,7)(14,8)(8,8)(8,6)10461394944000 C P P C P P C P P ++= 3．一位学者要在一周安排50个小时的工作时间，而且每天至少工作5小时，问共有多少种安排方案？（参见课本21页） 解：用i x 表示第i 天的工作时间，1,2,,7i =，则问题转化为求不定方程 123456750x x x x x x x ++++++=的整数解的组数，且5i x ≥，于是又可以转化为求不定方程123456715y y y y y y y ++++++=的整数解的组数。 该问题等价于：将15个没有区别的球，放入7个不同的盒子中，每盒球数不限，即相异元素允许重复的组合问题。 故安排方案共有：(,15)(1571,15)54264RC C ∞=+-= （种） ? 另解： 因为允许0i y =，所以问题转化为长度为1的15条线段中间有14个空，再加上前后两个空，共16个空，在这16个空中放入6个“＋”号，每个空放置的“＋”号数不限，未放“＋”号的线段合成一条线段，求放法的总数。从而不定方程的整数解共有： 212019181716(,6)(1661,6)54264654321 RC C ?????∞=+-= =?????（组） 即共有54 264种安排方案。 4.求下列函数的母函数: {(1)}n n -；（参见课本51页） 母函数为： 2 323000222()(1)(1)2(1)(1)(1)n n n n n n x x x G x n n x n n x nx x x x ∞∞∞====-=+-=-=---∑∑∑； ? 方法二： ()()()()()220 22220 02222023 ()(1)00121121n n n n n n n n n n G x n n x x n n x x n n x x x x x x x x x x ∞∞-==∞∞ +==∞+==-=++-"=++=""????== ? ?-???? =-∑∑∑∑∑
作业习题答案 习题二 2.1证明：在一个至少有2人的小组中，总存在两个人，他们在组内所认识的人数相同。 证明： 假设没有人谁都不认识：那么每个人认识的人数都为[1,n-1]，由鸽巢原理知，n 个人认识的人数有n-1种，那么至少有2个人认识的人数相同。 假设有1人谁都不认识：那么其他n-1人认识的人数都为[1,n-2]，由鸽巢原理知，n-1个人认识的人数有n-2种，那么至少有2个人认识的人数相同。 2.3证明：平面上任取5个坐标为整数的点，则其中至少有两个点，由它们所连线段的中点的坐标也是整数。 证明： 方法一： 有5个坐标，每个坐标只有4种可能的情况：（奇数，偶数）；（奇数，奇数）；（偶数，偶数）；（偶数，奇数）。由鸽巢原理知，至少有2个坐标的情况相同。又要想使中点的坐标也是整数，则其两点连线的坐标之和为偶数。因为 奇数+奇数 = 偶数 ； 偶数+偶数=偶数。因此只需找以上2个情况相同的点。而已证明：存在至少2个坐标的情况相同。证明成立。 方法二： 对于平面上的任意整数坐标的点而言，其坐标值对2取模后的可能取值只有4种情况，即：(0,0) ,(0,1) ,(1,0), (1,1)，根据鸽巢原理5个点中必有2个点的坐标对2取模后是相同类型的，那么这两点的连线中点也必为整数。 2.4一次选秀活动，每个人表演后可能得到的结果分别为“通过”、“淘汰”和“待定”，至少有多少人参加才能保证必有100个人得到相同的结果？ 证明： 根据推论2.2.1，若将3*（100-1）+1=298个人得到3种结果，必有100人得到相同结果。 2.9将一个矩形分成(m +1)行112m m +?? + ??? 列的网格每个格子涂1种颜色，有m 种颜色可以选择，证明：无论怎么涂色，其中必有一个由格子构成的矩形的4个角上的格子被涂上同一种颜色。 证明： （1）对每一列而言，有（m+1）行，m 种颜色，有鸽巢原理，则必有两个单元格颜色相同。 （2）每列中两个单元格的不同位置组合有12m +?? ??? 种，这样一列中两个同色单元格的位置组合共有 12m m +?? ??? 种情况 （3）现在有112m m +?? + ??? 列，根据鸽巢原理，必有两列相同。证明结论成立。 2.11证明：从S={1,3,5,…,599}这300个奇数中任意选取101个数，在所选出的数中一定存在2个数，它们之间最多差4。 证明：
排列组合》 一、排列与组合 1. 从9 人中选派2 人参加某一活动，有多少种不同选法？ 2. 从9人中选派2人参加文艺活动，1人下乡演出，1人在本地演出，有多少种不同选派方法？ 3. 现从男、女8名学生干部中选出2名男同学和1 名女同学分别参加全校“资源”、“生态” 和“环保”三个夏令营活动，已知共有90 种不同的方案，那么男、女同学的人数是 A.男同学2人，女同学6人 B.男同学3人，女同学5人 C. 男同学5人，女同学3人 D. 男同学6人，女同学2人 4. 一条铁路原有m个车站，为了适应客运需要新增加n个车站（n>1），则客运车票增加了58 种（从甲站到乙站与乙站到甲站需要两种不同车票），那么原有的车站有 A.12 个 B.13 个 C.14 个 D.15 个 5．用0，1 ，2，3，4，5 这六个数字， （1 ）可以组成多少个数字不重复的三位数？ （2）可以组成多少个数字允许重复的三位数？ （3）可以组成多少个数字不允许重复的三位数的奇数？ （4）可以组成多少个数字不重复的小于1000 的自然数？ （5）可以组成多少个大于3000，小于5421 的数字不重复的四位数？ 二、注意附加条件 1.6 人排成一列（1 ）甲乙必须站两端，有多少种不同排法？ （2）甲乙必须站两端，丙站中间，有多少种不同排法？ 2. 由1 、2、3、4、5、6 六个数字可组成多少个无重复数字且是6 的倍数的五位数？ 3. 由数字1 ，2，3，4，5，6，7 所组成的没有重复数字的四位数，按从小到大的顺序排列起来，第379 个数是 A.3761 B.4175 C.5132 D.6157 4. 设有编号为1、2、3、4、5 的五个茶杯和编号为1、2、3、4、5的五个杯盖，将五个杯盖盖在
《组合数学》期末试题（A ）姓名班级学号成绩 一，把m 个负号和n 个正号排在一条直线上，使得没有两个负 号相邻，问有多少种不同的排法。 二，在1和100之间既不是某个整数的平方，也不是某个整数的 立方的数有多少个？ 三，边长为1的等边三角形内任意放10个点，证明一定存在两 个点，其距离不大于1/3。 四，凸10边形的任意三条对角线不共点，试求(1)这凸10边形的 对角线交于多少个点？(2)又把所有对角线分割成多少段？五，求和=?? ???∑k－（－）k+1111n k n k 六，求解递推关系--++=??==?12016930,1 n n n a a a a a 七，用红白蓝三种颜色对1×n 的方格涂色，每个方格只能涂一种颜色，如果要求偶数个方格涂成红色，问有多少种方法？ 八，用红、蓝二种颜色对1×n 的方格涂色，每个方格只能涂一种颜色，如果要求涂成红色的两个方格不能相邻，问有多少种方法？注，1-4、6题各15分，第5题10分，第7题8分，第八题7分。
北京邮电大学2005 ——2006 学年第1 学期 《组合数学》期末试题答案 一， (15) 解： 由于正负号不能相连，故先将正号排好，产生n+1个空档。 --------5分 则负号只能排在两个正号之间，这相当于从n+1个数中取m 个数的组合，故有---------10分 1n m +????? ?种方式。----15 备注：若写出m>n+1时为0，m=n+1时为1，给5分 二， （19分） 解：设A 表示是1-100内某个数的平方的集合，则 |A|=10, -----4分 设B 表示是1-100内某个数的立方的集合，则|B|=4, --8分 |A ∩B|=2, -----12分 由容斥原理得 100|||||| 100104288A B A B A ∩=??+∩=??+=B --------19分 三， （15分） 证明：将此三角形剖分成9个小的边长为1/3的等边三角形。 - ------5分 由鸽巢原理，必有两点在某一个小三角形内，----12分 此时，这两点的距离不超过小三角形边长1/3。从而得证。 -------15分 四， （15分） 解：（1）由于没有三条对角线共点，所以这凸多边形任取4点，组成的多边形内唯一的一个四边形，确定唯一一个交点，--5分 从而总的交点数为C(10,4)=210-------------10分 （2）如图，不妨取顶点1，考察由1出发的对角线被其他对角线 剖分的总数。不妨设顶点标号按顺时针排列，取定对角线1 i
?1.证：对n 用归纳法。先证可表示性： 当n=0,1时，命题成立。 假设对小于n 的非负整数，命题成立。对于n,设k!≤n ＜(k+1)!,即0≤n-k!＜k·k!由假设对n-k!,命题成立， 设n-k!=∑a i ·i!，其中a k ≤k-1,n=∑a i ·i!+k!，命题成立。i=1 k i=1 k 再证表示的唯一性： 设n=∑a i ·i!=∑b i ·i!, 不妨设a j ＞b j ,令j=max{i|a i ≠b i }a j ·j!+a j-1·(j-1)!+…+a 1·1! =b j ·j!+b j-1·(j-1)!+…+b 1·1!,(a j -b j )·j!=∑(b i -a i )·i!≥j!＞∑i·i!≥∑|b i -a i |·i!≥∑(b i -a i )·i! 另一种证法：令j=min{i|a i ≠b i }∑a i ·i!=∑b i ·i!,两边被(j+1)!除,得余数a j ·j!=b j ·j!,矛盾. i=1 k i=1k i=1 j-1i=1 j-1 i=1j-1i=1 j-1 i ≥j i ≥j ?2.证： 组合意义： 等式左边：n 个不同的球，先任取出1个，再从余下的n-1个中取r 个； 等式右边：n 个不同球中任意取出r+1个，并指定其中任意一个为第一个。显然两种方案数相同。 nC(n-1,r) = n ————= ——————— (n-1)! (r+1)·n! r!·(n-r-1)! (r+1)·r!·(n-r-1)! = ——————= (r+1)C(n,r+1).(r+1)·n! (r+1)!·(n-r-1)! ?3.证： 设有n 个不同的小球，A 、B 两个盒子,A 盒中恰好放1个球,B 盒中可放任意个球。有两种方法放球： ①先从n 个球中取k 个球(k ≥1),再从中挑 一个放入A 盒,方案数共为∑kC(n,k),其余球放入B 盒。 ②先从n 个球中任取一球放入A 盒，剩下n-1个球每个有两种可能，要么放入B 盒， 要么不放，故方案数为n2 . 显然两种方法方案数应该一样。 k=1n n-1 ?4.解：设取的第一组数有a 个,第二组有b 个,而 要求第一组数中最小数大于第二组中最大的，即只要取出一组m 个数(设m=a+b),从大到小取a 个作为第一组,剩余的为第二组。此时方案数为C(n,m)。从m 个数中取第一组数共有m-1中取法。总的方案数为∑(m-1)C(n,m)=n ·2 +1. ?5.解：第1步从特定引擎对面的3个中取1个有 C(3,1)种取法，第2步从特定引擎一边的2个中 取1个有C(2,1)种取法，第3步从特定引擎对面的2个中取1个有C(2,1)中取法，剩下的每边1个取法固定。 所以共有C(3,1)·C(2,1)·C(2,1)=12种方案。 m=2 n n-1 ?6.解：首先所有数都用6位表示，从000000到 999999中在每位上0出现了10 次,所以0共出现 了6·10 次,0出现在最前面的次数应该从中去掉， 000000到999999中最左1位的0出现了10 次， 000000到099999中左数第2位的0出现了10 次， 000000到009999左数第3位的0出现了10 次, 000000到000999左数第4位的0出现了10 次, 000000到000099左数第5位的0出现了10 次, 000000到000009左数第6位的0出现了10 次。另外1000000的6个0应该被加上。所以0共出现了 6·10 –10 –10 –10 –10 –10 –10 +6 = 488895次。 5 5 5 4 3 2 1 5543210 ?7.解：把n 个男、n 个女分别进行全排列，然后 按乘法法则放到一起，而男女分别在前面,应该 再乘2,即方案数为2·(n!) 个. 围成一个圆桌坐下， 根据圆排列法则，方案数为2 ·(n!) /(2n)个. ?8.证：每个盒子不空，即每个盒子里至少放一 个球，因为球完全一样，问题转化为将n-r 个小球放入r 个不同的盒子，每个盒子可以放任意个球，可以有空盒，根据可重组合定理可得共有C(n-r+r-1,n-r) = C(n-1,n-r)中方案。根据C(n,r)=C(n,n-r),可得 C(n-1,n-r)=C(n-1,n-1-(n-r))=C(n-1,r-1)个方案。证毕。 2 2 ?9.解：每个能整除尽数n 的正整数都可以选取每个素数p i 从0到a i 次，即每个素数有a i +1种选择，所以能整除n 的正整数数目为(a 1+1)·(a 2+1)·…·(a l +1)个。 ?10.解：相当于把n 个小球放入6个不同的盒子里，为可重组合，即共有C(n+6-1,n)中方案，即C(n+5,n)中方案。 ?11.解：根据题意,每4个点可得到两条对角线,1个对角线交点,从10个顶点任取4个的方案有C(10,4)中,即交于210个点。
组合数学课后标准答案
————————————————————————————————作者：————————————————————————————————日期：
习题二证明：在一个至少有2人的小组中，总存在两个人，他们在组内所认识的人数相同。证明：假设没有人谁都不认识：那么每个人认识的人数都为[1,n-1]，由鸽巢原理知，n个人认识的人数有n-1种，那么至少有2个人认识的人数相同。假设有1人谁都不认识：那么其他n-1人认识的人数都为[1,n-2]，由鸽巢原理知，n-1个人认识的人数有n-2种，那么至少有2个人认识的人数相同。假设至少有两人谁都不认识，则认识的人数为0的至少有两人。
任取11个整数，求证其中至少有两个数的差是10的整数倍。证明：对于任意的一个整数，它除以10的余数只能有10种情况：0，1，…，9。现在有11个整数，由鸽巢原理知，至少有2个整数的余数相同，则这两个整数的差必是10的整数倍。证明：平面上任取5个坐标为整数的点，则其中至少有两个点，由它们所连线段的中点的坐标也是整数。2.3证明：有5个坐标，每个坐标只有4种可能的情况：（奇数，偶数）；（奇数，奇数）；（偶数，偶数）；（偶数，奇数）。由鸽巢原理知，至少有2个坐标的情况相同。又要想使中点的坐标也是整数，则其两点连线的坐标之和为偶数。因为奇数+奇数= 偶数；偶数+偶数=偶数。因此只需找以上2个情况相同的点。而已证明：存在至少2个坐标的情况相同。证明成立。
一次选秀活动，每个人表演后可能得到的结果分别为“通过”、“淘汰”和“待定”，至少有多少人参加才能保证必有100个人得到相同的结果？证明：根据推论2.2.1，若将3*（100-1）+1=298个人得到3种结果，必有100人得到相同结果。一个袋子里装了100个苹果、100个香蕉、100个橘子和100个梨。那么至少取出多少水果后能够保证已经拿出20个相同种类的水果？证明：根据推论2.2.1，若将4*（20-1）+ 1 = 77个水果取出，必有20个相同种类的水果。
组合数学 例1: 将8个“车”放在8×8的国际象棋棋盘上，如果它们两两均不能互吃，那么称8个“车”处于一个安全状态。问共有多少种不同的安全状态? 解：8个“车”处于安全状态当且仅当它们处于不同的8行和8列上。 用一个排列a1,a2,…,a8 ，对应于一个安全状态，使ai 表示第i 行的ai 列上放置一个“车”。这种对应显然是一对一的。因此，安全状态的总数等于这8个数的全排列总数8!＝40320。 例4：n 位客人在晚会上每人与他人握手d 次，d 是奇数。证明n 偶数。 证：由于每一次握手均使握手的两人各增加 一次与他人握手的次数，因此n 位客人与他人握手 次数的总和 nd 是偶数 — 握手次数的2倍。根据奇偶 性质，已知d 是奇数，那么n 必定是偶数。 例４ 从1到2n 的正整数中任取n +1个，则这n +1个数中，至少有一对数，其中一个是另一个的倍数。 证 设n +1个数是a 1, a 2, ···, an +1。每个数去掉一切2的因子，直至剩下一个奇数为止。组成序列r 1, r 2,, ···, rn +1。这n +1个数仍在[1 , 2n ]中，且都是奇数。而[1, 2n ]中只有n 个奇数，故必有ri =rj = r , 则ai = 2αi r , aj = 2αj r 。若ai ＞aj ，则ai 是aj 的倍数。 例5 设a 1, a 2, ···, am 是正整数，则至少存在一对k 和l , 0≤k
排例组合专题训练 1． 将3个不同的小球放入4个盒子中，则不同放法种数有A ．81 B ．64 C ．12 D ．14 2．5个人排成一排,其中甲、乙两人至少有一人在两端的排法种数有 A ．33A B ．334A C ．523533A A A - D ．23113 23233A A A A A + 3．,,,,a b c d e 共5个人，从中选1名组长1名副组长，但a 不能当副组长，不同的选法总数是 A.20 B ．16 C ．10 D ．6 4．现有男、女学生共8人，从男生中选2人，从女生中选1人分别参加数学、物理、化学三科竞赛，共有90种不同方案，那么男、女生人数分别是 A ．男生2人女生6人 B ．男生3人女生5人 C ．男生5人女生3人 D ．男生6人女生2人. 5．在8 2 x ? ?的展开式中的常数项是A.7 B ．7- C ．28 D ．28- 6．5 (12)(2)x x -+的展开式中3 x 的项的系数是A.120 B ．120- C ．100 D ．100- 7．22n x ???展开式中只有第六项二项式系数最大,则展开式中的常数项是 A ．180 B ．90 C ．45 D ．360 8．由数字1、2、3、4、5组成没有重复数字的五位数，其中小于50000的偶数共有 A ．60个 B ．48个 C ．36个 D ． 24个 9．3张不同的电影票全部分给10个人,每人至多一张,则有不同分法的种数是 A ．1260 B ．120 C ．240 D ．720 10．n N ∈且55n <,则乘积(55)(56) (69)n n n ---等于 A ．5569n n A -- B ．15 69n A - C ．15 55n A - D ．14 69n A - 11．从不同号码的5双鞋中任取4只，其中恰好有1双的取法种数为 A ．120 B ．240 C ．280 D ．60 12．把10 )x -把二项式定理展开，展开式的第8项的系数是 A ．135 B ．135- C ．- D ． 13．2122n x x ??+ ?? ?的展开式中，2 x 的系数是224，则2 1x 的系数是A.14 B ．28C ．56 D ．112 14．不共面的四个定点到面α的距离都相等，这样的面α共有几个A ．3 B ．4 C ．6 D ．7
李凡长版-组合数学课后习题答案-习题3
第三章递推关系 1.在平面上画n条无限直线,每对直线都在不同的点相交,它们构成的无限 区域数记为f(n),求f(n)满足的递推关系. 解： f(n)=f(n-1)+2 f(1)=2,f(2)=4 解得f(n)=2n. 2.n位三进制数中,没有1出现在任何2的右边的序列的数目记为f(n),求 f(n)满足的递推关系. 解：设a n-1a n-2 …a 1 是满足条件的n-1位三进制数序列，则它的个数可以用f(n-1) 表示。 a n 可以有两种情况： 1）不管上述序列中是否有2，因为a n 的位置在最左边，因此0 和1均可选； 2）当上述序列中没有1时，2可选； 故满足条件的序列数为 f(n)=2f(n-1)+2n-1 n 1, f(1)=3 解得f(n)=2n-1(2+n). 3.n位四进制数中,2和3出现偶数次的序列的数目记为f(n),求f(n)满足 的递推关系. 解：设h(n)表示2出现偶数次的序列的数目，g(n)表示有偶数个2奇数个3的序列的数目，由对称性它同时还可以表示奇数个2偶数个3的序列的数目。 则有 h(n)=3h(n-1)+4n-1-h(n-1),h(1)=3 （1） f(n)=h(n)-g(n),f(n)=2f(n-1)+2g(n-1) （2） 将（1）得到的h(n)=(2n+4n)/2代入（2），可得 n+4n)/2-2f(n), 4.求满足相邻位不同为0的n位二进制序列中0的个数f(n). 解：这种序列有两种情况： 1)最后一位为0，这种情况有f(n-3)个； 2)最后一位为1，这种情况有2f(n-2)个； 所以 f(1)=2,f(2)=3,f(3)=5. 5.求n位0,1序列中“00”只在最后两位才出现的序列数f(n). 解：最后两位是“00”的序列共有2n-2个。 f(n)包含了在最后两位第一次出现“00”的序列数，同时排除了在n-1位第一次出现“00”的可能； f(n-1)表示在第n-1位第一次出现“00”的序列数，同时同时排除了在n-2位第一次出现“00”的可能； 依此类推，有 17
第一部分：填空题。 题目1:求n 元布尔函数f (x1，x2，…，xn ）的数目，其中布尔函数是指含有与（∧）、或（∨）、非（－）等基本布尔运算的函数。 解答：设有n 个布尔变元x 1，x 2，…，x n ，其中x i ∈{0，1}，i =1，2，…，n ，根据乘法原理(x 1，x 2，…，x n )共有2n 种不同指派，对每个指派，布尔函数取值为{0，1}，故不同的布尔函数的数目为：22n 。 （考试中会给定n 的具体数值，带入公式直接计算即可。） 题目2：n 对夫妻围一圆桌而坐，求每对夫妻相邻而坐的方案数。 解答：夫妻相邻而坐，可以将一对夫妻看成一个整体，其圆排列数为(n -1)!，由于每对夫妻可以交换位置，故所求方案数为(n -1)!×2n 。 题目3：求多重集合M = {∞·a 1, ∞·a 2, …, ∞·a n }的r 排列数。 解答：在构造的M 的一个r 排列时，第一项有n 种选择，第二项有n 种选择，……， 第r 项有n 种选择，故M 的r 排列数为n r 。 (一般地，n 元多重集合表示为：M = {k 1·a 1, k 2·a 2, …, k n ·a n }其中：a i （i = 1, 2, …, n ）表示元素的种类，k i （i = 1, 2, …, n ）表示元素a i 的个数。) 题目4：求多重集合M = { k 1·a 1, k 2·a 2, …, k n ·a n }的全排列数。 解答：先把M 中的所有的k 1 + k 2 + … + k n 个元素看成是互不相同的，则它的全排列数为(k 1 + k 2 + … + k n )!。但是这里k i !个a i 是相同的，所以k i !个a i 的位置相同并且同其他元素排列也相同的排列是同一个，故M 的全排列数为： ! !!)! (2121n n k k k k k k +++。 题目5：确定1054321)(x x x x x ++++的展开式中x 13 x 2 x 34 x 52的系数。 解答：??? ? ??=???? ?????? ?????? ?????? ??2,4,1,310224617310 ! 2!4!1!3!10! 0!2!2! 2!4!6! 6!1! 7!7!3! 10= ? ? ? = （? ?? ? ??r n 表示从n 中取r 个的组合，与r n C 的意义完全相同。试题中可能会改变具体的数值，例如求15 54321)(x x x x x ++++的展开式中x 15x 24 x 34 x 52的系数，只需按上述过程计算即可。） 题目6： 求正整数n 的有序k 分拆的个数，要求第i 个分部量大于等于p i 。 解答：分拆的个数为：?? ? ? ? ??---+∑=111k p k n k i i ，其中（1≤i ≤k ）。 例如：9的有序3分拆，要求所有分部量都大于等于2，其个数为：
组合数学及其图论 1、一个图G 是指一个有序三元组（V （G ），E （G ），G ?），其中G ?是：________________. 关联函数 2、 是有40个点的简单图且 中任两个点之间有且只有1条路，则 。 39 3、只有一个顶点所构成的图称为：________________ 平凡图 4、如果H 是G 的子图，其中V （H ）=V （G ）和E （G ）=E （H ）至少有一个不成立，就称H 是G 的：_____________. 真子图 5、设G 是p 阶简单图，则__________________等号成立当且仅当G 是完全图。 q(G)≤p(p-1)/2 6、如果一条途径的_________与___________相同，就称这条途径为闭途径。 起点 终点 7、如果对图G=（V ，E ）的任何两个顶点u 与v ，G 中存在一条（u-v ）路，则称G 是___________否则称为是______________ 连通图、 非连通图 8、设G 是P 阶连通图，则__________________. q(G)≥p-1 9、若二分图 有Hamilton 回路，则 与 满足 。 10、若G 是2-边连通图，则G 有强连通的________________. 定向图 11、边数最少的连通图是 。
树 12、没有回路的连通图称为_______________. 树 13、的图是图或图。 平凡图，不连通图 14、树T的每一个非悬挂点都是T的 __________. 割点 15、二分图中若与满足，则必有完美对集。 16、给定一个图G，如果图G的一个生成子图T是一棵树，则称T是G的一个_______________. 生成树 17、设G是无环图，e是G的一条边，则 τ(G)=___________________________. τ （G－e）+τ (G·e) 18、是阶简单图，则，等号成立当且仅当是图。 ，完全图 2、 19、___________________________的生成树称为最优生成树。 连通赋权图中具有最小权 20、的一个对集是最大对集的充要条件是。 中无可扩路 21、一个有向图D，如果略去每条弧的方向时所得无向图是一棵树，就称D为_____________________. 有向树 22、经过G的每条边的迹称为G的Euler迹，如果这条迹是闭的，则称这条闭迹为G的 ________________. Euler环游 23、是简单图且，则。
组合数学作业 第一章引言 Page 13, ex3,4,7,30 ex3. 想象一座有64个囚室组成的监狱，这些囚室被排列成8 8棋盘。所有相邻的囚室间都有门。某角落处意见囚室例的囚犯被告知，如果他能够经过其它每一个囚室正好一次之后，达到对角线上相对的另一间囚室，那么他就可以获释。他能获得自由吗？ 解：不能获得自由。 方法一：对64个囚室用黑白两种颜色染色，使得横和竖方向相邻的囚室颜色不同。则对角线上两个囚室颜色为同黑或同白。总共偶数个囚室，若能遍历且不重复，则必然是黑出发白结束，矛盾。 方法二：64个囚室，若要经过每个囚室正好一次，需要走63步，即奇数步。 不妨假设该囚犯在第1行第1列，那么到第8行第8列，横着的方向需要走奇数步，竖着的方向需要走奇数步，即总共需要偶数步。 所以不能恰好经过每个囚室一次到达对角线上的囚室。 ex4. (a) 设f(n)是用多米诺牌(2-牌)对2×n棋盘作完美覆盖的个数。估计一下f(1),f(2),f(3),f(4)和f(5). 试寻找(或证明)这个计数函数f满足的简单关系。利用这个关系计算f(12)。 (b) 设g(n)是用多米诺牌(2-牌)对3×n棋盘作完美覆盖的个数。估计g(1),g(2),…,g(6). 解：(a) f(1)=1, f(2)=2, f(3)=3, f(n+2)=f(n+1)+f(n) f(4)=f(3)+f(2)=5, f(5)=f(4)+f(3)=8 f(6)=f(5)+f(4)=13 f(7)=f(6)+f(5)=21 f(8)=f(7)+f(6)=34 f(9)=f(8)+f(7)=55 f(10)=f(9)+f(8)=89 f(11)=f(10)+f(9)=144 f(12)=f(11)+f(10)=233 (b) g(1)=0, g(2)=3, g(3)=0, g(4)=9+2=11, g(n+4)=4g(n+2)-g(n), g(5)=0, g(6)=41. ex7. 设a和b是正整数，且a是b的因子。证明m×n棋盘有a×b的完美覆盖当且仅当a 既是m又是n的因子，而b是m或n的因子。(提示: 把a×b牌分割成a个1×b牌。) 解：充分性。当a既是m又是n的因子，而b是m或n的因子，则m×n棋盘有a×b的平凡完美覆盖。 必要性。假设m×n棋盘有a×b牌的完美覆盖。则m×n棋盘必有b牌的完美覆盖。根据书中的定理，b是m的因子或n的因子。 下面证明a既是m的因子又是n的因子。 方法一: 因为a是b的因子，所以a×b牌可以分割成b/a个a×a牌。m×n棋盘有a×a的完美覆盖，则必然有a×a牌的完美覆盖。而a×a牌是正方形的，所以只有唯一的一种平凡覆盖方式。从而m是a的倍数，n也是a的倍数。 方法二: 因为a是b的因子，不妨设b=ka。由m×n棋盘有a×b牌的完美覆盖，可任取一个完美覆盖。设第一行的n个方格由p个a×b牌和q个b×a牌盖住，则有n=pb+qa=(pk+q)a，所以n是a的倍数。同理，m也是a的倍数。
排列组合 一、选择题： 1． 将3个不同的小球放入4个盒子中，则不同放法种数有 A ．81 B ．64 C ．12 D ．14 2．5个人排成一排,其中甲、乙两人至少有一人在两端的排法种数有 A ．33A B ．334A C ．523533A A A - D ．23113232 33A A A A A + 3．,,,,a b c d e 共5个人，从中选1名组长1名副组长，但a 不能当副组长，不同的 选法总数是 A.20 B ．16 C ．10 D ．6 4．现有男、女学生共8人，从男生中选2人，从女生中选1人分别参加数学、物理、化学三科竞赛，共有90种不同方案，那么男、女生人数分别是 A ．男生2人女生6人 B ．男生3人女生5人 C ．男生5人女生3人 D ．男生6人女生2人. 5． 6． A ．180 B ．90 C ．45 D ．360 6．由数字1、2、3、4、5组成没有重复数字的五位数，其中小于50000的偶数共有 A ．60个 B ．48个 C ．36个 D ． 24个 7．3张不同的电影票全部分给10个人,每人至多一张,则有不同分法的种数是 A ．1260 B ．120 C ．240 D ．720 8．n N ∈且55n <,则乘积(55)(56)(69)n n n ---L 等于 A ．5569n n A -- B ．1569n A - C ．1555n A - D ．1469n A -
9．从不同号码的5双鞋中任取4只，其中恰好有1双的取法种数为 A ．120 B ．240 C ．280 D ．60 10．不共面的四个定点到面α的距离都相等，这样的面α共有几个 A ．3 B ．4 C ．6 D ．7 11．设含有10个元素的集合的全部子集数为S ，其中由3个元素组成的子集数为T ，则T S 的值为 A. 20128 B ．15128 C ．16128 D ．21 128 15．4名男生，4名女生排成一排，女生不排两端，则有 种不同排法. （8640 ） 17．在1,2,3,...,9的九个数字里，任取四个数字排成一个首末两个数字是奇数的四位数，这样的四位数有_________________个. （840） 18．用1,4,5,x 四个不同数字组成四位数,所有这些四位数中的数字的总和为288,则x = . （2） 5．若2222345363,n C C C C ++++=L 则自然数n =_____.(13) 19．n 个人参加某项资格考试，能否通过，有 种可能的结果？( 2n ) 20．已知集合{}1,0,1S =-,{}1,2,3,4P =,从集合S ,P 中各取一个元素作为点的坐标,可作出不同的点共有_____个. (23) 22．{}1,2,3,4,5,6,7,8,9A =，则含有五个元素，且其中至少有两个偶数的子集个数为_____.105 23．8张椅子排成,有4个人就座,每人1个座位,恰有3个连续空位的坐法共有多少种?_______ 480 25．7个人排成一排，在下列情况下，各有多少种不同排法？