吉林大学组合数学习题解答
————————————————————————————————作者: ————————————————————————————————日期:
第二章
2.1 证明：在一个至少有2人的小组中,总存在两个人,他们在组内所认识的人数相同。 证明: 假设没有人谁都不认识：那么每个人认识的人数都为[1,n －１]，由鸽巢原理知，ｎ个人认识的人数有n-１种,那么至少有2个人认识的人数相同。 假设有1人谁都不认识：那么其他ｎ-１人认识的人数都为[1,n-２]，由鸽巢原理知,n －１个人认识的人数有ｎ-2种,那么至少有2个人认识的人数相同。
2.3 证明:平面上任取5个坐标为整数的点，则其中至少有两个点,由它们所连线段的中点的
坐标也是整数。 证明: 方法一:
有5个坐标，每个坐标只有4种可能的情况:（奇数，偶数）；(奇数,奇数）;（偶数，偶数）;(偶数,奇数）。由鸽巢原理知,至少有２个坐标的情况相同。又要想使中点的坐标也是整数,则其两点连线的坐标之和为偶数。因为 奇数＋奇数 = 偶数 ； 偶数+偶数=偶数。因此只需找以上2个情况相同的点。而已证明:存在至少２个坐标的情况相同。证明成立。
第三章
3.4 教室有两排,每排8个座位。现有学生14人，其中的５个人总坐在前排，4个人总坐在后排，求有多少种方法将学生安排在座位上？
解：前排8个座位，５人固定,共58*5!C 种方法；后排８个座位，4人固定,共4
8*4!C 种方法;前排和后排还剩7个座位,由剩下的5人挑选5个座位,共5
7*5!C 种方法；则一共有545
545887887***5!*5!*4!**28449792000C C C P P P ==种安排方法。 另一种解法：168277386545
5885885888871408!
7!C P P C P P C P P P P P ++=⨯⨯=⨯⨯。 3.5 将英文字母表中的26个字母排序,要求任意两个元音字母不能相邻,则有多少种排序方
法？
解：先排21个辅音字母，共有２1!
再将5个元音插入到2２个空隙中，5
22P
故所求为52155
222122521!P P C P ⨯=
3.６ 有6名先生和6名女士围坐一个圆桌就餐，要求男女交替就坐，则有多少种不同的排坐方式？
解：6男全排列6！;6女全排列６!；6女插入6男的前6个空或者后6个空,即女打头或男打头6!*６!＊２;再除以围圈重复得(６!*６!*２)／1２=6！*5!= 8６400
3.７ 15个人围坐一个圆桌开会,如果先生Ａ拒绝和先生Ｂ和C 相邻，那么有多少种排坐方式? 解:
方法1:除Ｂ和C 以外，A 可以在剩余的12人中挑选２人坐在自己的两边，有22
122C P 。将A 与其两边的人看作一个元素，与其他12个人形成共13个元素的圆排列，有(13-1)!,所以共
有222
12212(131)!12!C P P -== 63228211200种排列。
方法2:除去A 、B 和C 的12人共有11
11P 种坐法,Ａ在12人中插入位置的坐法有12种。B 和C 不与A 相邻的坐法共有1１＊12种，由于1５人围成圆桌坐，故排列方式共有
111112*********!P ⨯⨯=⨯= 6３22８21１2０0种坐法。
3.9 求方程123420x x x x +++=，满足12342,0,5,1x x x x ≥≥≥≥-的整数解的个数。
14416803+-⎛⎫= ⎪⎝⎭
3.10 书架上有20卷百科全书，从中选出4卷使得任意两本的卷号都不相邻的选法有多少种? 解：
n=20,ｒ=4，1204117238044n r r -+-+⎛⎫⎛⎫⎛⎫
=== ⎪ ⎪ ⎪⎝⎭⎝⎭⎝⎭
相当于有16卷已经排好,把４卷插入到17个“空隙”中,有174⎛⎫
⎪⎝⎭
种，对应序号都不会相邻。
3.20 证明:
（１）()11,3(31)22
n
n S n -=
+- （2)()⎪⎪⎭
⎫ ⎝⎛+⎪⎪⎭⎫ ⎝⎛=-4332,n n n n S ； (3）().61551043,⎪⎪⎭
⎫ ⎝⎛+⎪⎪⎭⎫ ⎝⎛+⎪⎪⎭⎫ ⎝⎛=-n n n n n S
证明： (1)
组合分析方法：
n 个元素分成3组，允许为空的方案为3n ;
ｎ个元素分成3组,有一组必为空的方案为3*２n ; n 个元素分成3组，有两组必为空的方案为３;
n 个元素分成3组，根据容斥原理,不允许为空的方案为3n －3*2n +３；
不考虑组间顺序,方案为
1
133231(31)23!2
n n n n ---⨯+=+-
（2)
()⎪⎪⎭
⎫
⎝⎛+⎪⎪⎭⎫ ⎝⎛=-4332,n n n n S
3个元素一组、其余元素一个各一组或者选４个元素分两组(每组2个）、其余元素一个各一组。
3个元素一组、其余元素一个各一组：3n ⎛⎫
⎪⎝⎭
选4个元素分两组(每组2个)、其余元素一个各一组：选4个元素的方案为4n ⎛⎫ ⎪⎝⎭
，分成
2组的方案为42!32⎛⎫= ⎪⎝⎭种,所以有34n ⎛⎫
⎪⎝⎭
。
(３）
().61551043,⎪⎪⎭
⎫ ⎝⎛+⎪⎪⎭⎫ ⎝⎛+⎪⎪⎭⎫ ⎝⎛=-n n n n n S 4个元素一组、其余元素一个各一组，或者选5个元素分两组（一组2个一组３个）、
其余元素一个各一组，或者6个元素分三组(每组2个）、其余元素一个各一组。
4个元素一组、其余元素一个各一组:4n ⎛⎫ ⎪⎝⎭
。
选5个元素分两组(一组2个一组3个）、其余元素一个各一组：选5个元素为5n ⎛⎫
⎪⎝⎭
，
分两组(一组２个一组３个)方案为5102⎛⎫= ⎪⎝⎭,所以有105n ⎛⎫ ⎪⎝⎭
。
选6个元素分三组(每组2个)、其余元素一个各一组：选6个元素为6n ⎛⎫ ⎪⎝⎭
，分三组（每
组2个）的方案为63!15222⎛⎫=
⎪⎝⎭,所以有156n ⎛⎫
⎪⎝⎭
3.21 (１)会议室中有２n +１个座位，现摆成3排，要求任意两排的座位都占大多数，求有多
少种摆法? 解：
(1)
方法1：如果没有附加限制则相当于把2ｎ+1个相同的小球放到3个不同的盒子里,有
213123 3-1 2n n ++-+⎛⎫⎛⎫= ⎪ ⎪⎝⎭⎝⎭
种方案,而不符合题意的摆法是有一排至少有n ＋１个座位。这
