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

第二章

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个人总坐在后排，求有多少种方法将学生安排在座位上？

5解：前排8个座位，5人固定，共C8*5!种方法；后排8个座位，4人固定，共C84*4!种5方法；前排和后排还剩7个座位，由剩下的5人挑选5个座位，共C7*5!种方法；则一共545545有C8*C8*C7*5!*5!*4!?P8*P8*P7?28449792000种安排方法。 168277386545另一种解法：C5P?7!。 8P8?C5P8P8?C5P8P8?P8?P8?P7?140?8!3.5 将英文字母表中的26个字母排序，要求任意两个元音字母不能相邻，则有多少种排序方法？

解：先排21个辅音字母，共有21！

5 再将5个元音插入到22个空隙中，P22

52155故所求为21!?P22?P21C22P5

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相邻，那么有多少种排坐方式？

解：

22方法1：除B和C以外，A可以在剩余的12人中挑选2人坐在自己的两边，有C12P2。将

A与其两边的人看作一个元素，与其他12个人形成共13个元素的圆排列，有(13-1)!，所以

222共有C12P)!?P2(13?11212!= 63228211200种排列。

11方法2：除去A、B和C的12人共有P11种坐法，A在12人中插入位置的坐法有12种。B

和C不与A相邻的坐法共有11*12种，由于15人围成圆桌坐，故排列方式共有

11P1112?11?12?132?12!= 63228211200种坐法。

3.9 求方程x1?x2?x3?x4?20，满足x1?2,x2?0,x3?5,x4??1的整数解的个数。

?14?4?1????680

3??

3.10 书架上有20卷百科全书，从中选出4卷使得任意两本的卷号都不相邻的选法有多少

种？ 解： n=20，r=4，??n?r?1??20?4?1??17?????????2380

4?r????4??17??种，对应序号都不会相?4?相当于有16卷已经排好，把4卷插入到17个“空隙”中，有?邻。

3.20 证明： （1）S?n,3??1n(3?1)?2n?1 2（2）S?n,n?2???????3????； （3）S?n,n?3???????10?????15????.

证明： （1）

组合分析方法：

n个元素分成3组，允许为空的方案为3n；

n个元素分成3组，有一组必为空的方案为3*2n； n个元素分成3组，有两组必为空的方案为3；

n个元素分成3组，根据容斥原理，不允许为空的方案为3n-3*2n+3；

?n??3??n??4??n??4??n??5??n??6?3n?3?2n?31n?1?(3?1)?2n?1 不考虑组间顺序，方案为

3!2（2）

?n??n?S?n,n?2????3???3??4??

????3个元素一组、其余元素一个各一组或者选4个元素分两组（每组2个）、其余元素一个各一组。

3个元素一组、其余元素一个各一组：??

?n??3??n?选4个元素分两组（每组2个）、其余元素一个各一组：选4个元素的方案为??，

?4?分成2组的方案为??2!?3种，所以有3??。

（3）

?4??2??n??4??n??n??n?????S?n,n?3????10?15?4??5??6??. ??????4个元素一组、其余元素一个各一组，或者选5个元素分两组（一组2个一组3个）、

其余元素一个各一组，或者6个元素分三组（每组2个）、其余元素一个各一组。

?n?4个元素一组、其余元素一个各一组：??。

?4?选5个元素分两组（一组2个一组3个）、其余元素一个各一组：选5个元素为??，

?n??5?分两组（一组2个一组3个）方案为???10，所以有10??。

?5??2??n??5?选6个元素分三组（每组2个）、其余元素一个各一组：选6个元素为??，分三组

?n??6?（每组2个）的方案为??6??n?，所以有153!?15?? ?222?6???3.21 (1)会议室中有2n+1个座位，现摆成3排，要求任意两排的座位都占大多数，求有多少

种摆法？ 解：

(1)

方法1：如果没有附加限制则相当于把2n+1个相同的小球放到3个不同的盒子里，有

?2n?1?3?1??2n?3??????种方案，而不符合题意的摆法是有一排至少有n+1个座位。这? 3-1?? 2?相当于将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个，第二排座位有x2个，第三排座位有x3个。x1+x2+x3=2n+1，且x1+x2≥(2n+1)/2，x1+x3≥(2n+1)/2，x2+x3≥(2n+1)/2，即x1+x2≥n+1，x1+x3≥n+1，x2+x3≥n+1，令y1= x1+x2-n-1，y2= x1+x3-n-1，y3= x2+x3-n-1，可知y1+y2+y3=2(2n+1)-3(n+1)=n-1且yi≥0，1≤i≤3。显然，x方程满足要求的解与y方程非负整数解一一对应，有

?n?1?3?1??n?1??????种。 ?3?1??2?方法3：要求每行非空

如果没有附加限制则相当于把2n+1个相同的小球放到3个不同的盒子里，不允许为空，有??2n?1?1??2n?????种方案，而不符合题意的摆法是有一排至少有n+1个座位。这相当

? 3-1??2?于将n个座位先放到3排中的某一排，再将剩下的2n+1-n=n+1个座位任意分到3排中，每

?2n?1?n?1??n?排不允许为空，这样的摆法共有3????3???种方案，所以符合题意的摆法

2???2?有：

?2n??n??n?1??3???????? ?2??2?? 2? 第四章

4.13 计算棋盘多项式R( 解：

)。

R() = x*R()+R() =x*(1+3x+x2)+(1+x)*R(

)

= x3+3x2+x+(1+x)[xR(

)+R()]

= x3+3x2+x+(1+x)[x(1+x)+(1+4x+2x2)] = 5x3+12x2+7x+1

第五章

2?3x?9x25.3 已知数列?ak?的生成函数是A(x)?，求ak.

1?3x?2?3x?9x22A(x)???3x??2?3kxk?3x

1?3x1?3xk?0?9ak??k?2?3k?1 k?1

5.7一个1×n的方格图形用红、蓝、绿和橙四种颜色涂色，如果有偶数个方格被涂成红色，还有偶数个方格被涂成绿色，求有多少种方案？ 解：涂色方案数为bk则：

2x42x3x?e?x2x2e4x?2e2x?122xxeG{b}?(1????)?(1????)?()?(e)?ek2!4!2!3!24?nn?1n1???4?2?x44n!n?0

?4n?1?2n?1 因此：bn??1?n?0n?0，所以有4n?1?2n?1种方案。

本文来源：https://www.bwwdw.com/article/yjxo.html