情声-exchanged

吉林大学组合数学习题解答

第二章
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
个坐标的情况相同。证明成立。

第三章

3.4 教室有两排，每排8个座位。现有学生14
人，其中的5 个人总坐在前排，4个人总坐在后
排，求有多少种方法将学生安排在座位上？
解：前排8个座 位，5人固定，共
C
后排8个座位，4人固定，共
C
位，共
5
C
7
*5!
5
8
*5!
种方法；
4
8< br>*4!
种方法；前排
和后排还剩7个座位，由剩下的5人挑选5个座
种方法；则 一共有
种安排方法。
。
386
C
5
2
P8
7
P
8
7
C
5
P
8
P< br>8
P
8
5
P
8
4
P
7
5
1408!7!
5
C
8
5
*C
8
4
*C
7
*5!*5!*4!P
8
5
*P
8< br>4
*P
7
5
28449792000
另一种解法：
CPP
168
588
3.5 将英文字母表中的26个字母排序，要求任
意两个元音字母不能相邻，则有多少种排序方
法？
解：先排21个辅音字母，共有21！
再将5个元音插入到22个空隙中，
P

5
22
故所求为
21!P

5
22
21 5
P
21
C
22
P
5
5

3.6 有6名先生和6名女士围坐一个圆桌就餐，

要求男女交替就坐，则有多少种不同的排坐方
式？
解：6男全排列6!；6女全排列 6！；6女插入6
男的前6个空或者后6个空，即女打头或男打头
6!*6!*2；再除以围圈 重复得(6!*6!*2)12=6!*5!=

86400

3.7 15个人围坐一个圆桌开会，如果先生A拒绝
和先生B和C相邻，那么有多少种排坐方式？
解：
方法1：除B和C以外，A可以在剩余的12人
中挑选2人坐在自己的两边，有
C
22
122
P
。将A与其
两边的人看作一个元素，与其他 12个人形成共
13个元素的圆排列，有(13-1)!，所以共有
22
C
1 2
P
2
2
(131)!P
12
12!
= 63228211200种排列。
11
11
方法2：除去A、B和C的12人共有< br>P
种坐法，
A在12人中插入位置的坐法有12种。B和C不
与A相邻的坐法共 有11*12种，由于15人围成
圆桌坐，故排列方式共有
63228211200种坐法。
3.9 求方程
xx
12
11
P
11
1211 1213212!
=
x
3
x
4
20
，满足
x2,x
12
0,x
3
5,x
4
 1
的
整数解的个数。


1441


680
3



3.10 书架上有20卷百科全书，从中选出4卷使
得任意两本的卷号都不相邻的选法有多少
种？
解：
nr1

2041

17
< br>n=20，r=4，






 2380

r44

相当于有16卷已经排好，把4卷插入到17 个“空
隙”中，有

3.20 证明：
（1）
S

n,3


1
(3
2

n

17



4

种，对应序号都不会相邻。
1)2
n1

n

n


（2）
S

n,n2




3

3


4


；
 
n

n

n


（3）< br>S

n,n3



1015
4

5

6


.


证明：
（1）
组合分析方法：
n个元素分成3组，允许为空的方案为3
n
；
n个元素分成3组，有一组必为空的方案为3*2
n
；

n个元素分成3组，有两组必为空的方案为3；
n个元素分成3组，根据容斥原理，不允许为 空
的方案为3
n
-3*2
n
+3；
不考虑组间顺序，方案为
（2）

n

n
< br>S

n,n2




3

3


4



3
n
32
n
31
n1
(31)2
n13!2


3个元素一组、其余元素一个各一组或者选4
个元素分两组（ 每组2个）、其余元素一个各一
组。
n

3个元素一组、其余元素一个各一组：



3

选4个元素分两组（每组2个）、其余元素一
个各一组：选4个元素的方案为
4

方案为


2

2!3

n



4

，分成2组的
n
种，所以有
3


。
4


（3）

n

n

n

 
S

n,n3



1015

4

5

6


.
 

4个元素一组、其余元素一个各一组，或者选
5个元素分两组（一组2个一 组3个）、其余元
素一个各一组，或者6个元素分三组（每组2个）、

其余元素一个各一组。
n

4个元素一组、其余元素一个各一组：


。 4

选5个元素分两组（一组2个一组3个）、其
n

余元素 一个各一组：选5个元素为

分两组（一

，
5
5

n

组2个一组3个）方案为

，所以有
1010

。
25

选6个元素分三组（每组2 个）、其余元素一
n

个各一组：选6个元素为


，分 三组（每组2
6

个）的方案为

6

3!15
222

，所以有

n

15< br>

6


3.21 (1)会议室中有2n+1个座位， 现摆成3排，
要求任意两排的座位都占大多数，求有多少种
摆法？
解：
(1)
方法1：如果没有附加限制则相当于把2n+1
个相同的小球放到3个不同的 盒子里，有

2n131

2n3




3-1 2

种方案，而不符合题意的摆 法是
有一排至少有n+1个座位。这相当于将n+1个
座位先放到3排中的某一排，再将剩下的
2n+1-(n+1)=n个座位任意分到3排中，这样的摆

2n 1(n1)31

n2

法共有
3

3

种方案，所以符合
2 2

题意的摆法有：

2n3

n2

n1


3



2 2

2


方法2：设第一排座位有x1
个，第二排座位有
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< br>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方程非负整数解一
一对应，有

n131
< br>n1




31

2

种。
方法3：要求每行非空
如果没有附加限制则相当于把2n+1个相同的< br>小球放到3个不同的盒子里，不允许为空，有

2n11

2n




3-1

2

种方案，而不符合题意的摆法是有一
排至少有n+1个座位。这相当于将n个座位先放到3排中的某一排，再将剩下的2n+1-n=n+1个
座位任意分到3排中，每排不允许为空，这 样的
2n1n1

n

摆法共有
3
< br>3

种方案，所以符合题意
22


的摆法有：

2n
< br>n

n1

3


22 2



第四章

4.13 计算棋盘多项式R(

解：
R() = x*R(
)
)+R()
)。
=x*(1+3x+x
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
)]
= 5x
3
+12x
2
+7x+1

第五章
5.3 已知数列

a

的生成函数是
k
23x9x
2
A(x)
13x
，求
a
k
.

< br>23x9x
2
2
A(x)3x

23
k
x
k
3x
13x13x
k0

< br>
9
a
k


k

23
k1
k1



5.7一个1×n的方格图形用红、蓝、绿和橙 四种
颜色涂色，如果有偶数个方格被涂成红色，还有
偶数个方格被涂成绿色，求有多少种方案？
解：涂色方案数为
b
则：
k
2423xx4x2x
G{ b}(1
x

x

L
)
2
g
(1
x

x

L
)
2
(
e e
)
2
g
(e
x
)
2

e2e 1
ek
2!4!2!3!24

nn1
x
n
1 42


g
44n!
n0

因此：


4
n1
2
n1
n0
b
n


1n0

，所以有
4
n12
n1
种方案。