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

第二章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人固定，共种方法；后排8个座位，4人固定，共种方法；前排和后排还剩7个座位，由剩下的5人挑选5个座位，共种方法；则一共有种安排方法。另一种解法：。3.5 将英文字母表中的26个字母排序，要求任意两个元音字母不能相邻，则有多少种排序方法？解：先排21个辅音字母，共有21！ 再将5个元音插入到22个空隙中， 故所求为3.6 有6名先生和6名女士围坐一个圆桌就餐，要求男女交替就坐，则有多少种不同的排坐方式？解：6男全排列6!；6女全排列6！；6女插入6男的前6个空或者后6个空，即女打头或男打头6!*6!*2；再除以围圈重复得(6!*6!*2)/12=6!*5!= 864003.7 15个人围坐一个圆桌开会，如果先生A拒绝和先生B和C相邻，那么有多少种排坐方式？解：方法1：除B和C以外，A可以在剩余的12人中挑选2人坐在自己的两边，有。将A与其两边的人看作一个元素，与其他12个人形成共13个元素的圆排列，有(13-1)!，所以共有= 63228211200种排列。方法2：除去A、B和C的12人共有种坐法，A在12人中插入位置的坐法有12种。B和C不与A相邻的坐法共有11*12种，由于15人围成圆桌坐，故排列方式共有= 63228211200种坐法。3.9 求方程，满足的整数解的个数。3.10 书架上有20卷百科全书，从中选出4卷使得任意两本的卷号都不相邻的选法有多少种？解：n=20，r=4，相当于有16卷已经排好，把4卷插入到17个“空隙”中，有种，对应序号都不会相邻。3.20 证明： （1）（2）；（3）证明：（1）组合分析方法：n个元素分成3组，允许为空的方案为3n；n个元素分成3组，有一组必为空的方案为3*2n；n个元素分成3组，有两组必为空的方案为3；n个元素分成3组，根据容斥原理，不允许为空的方案为3n-3*2n+3；不考虑组间顺序，方案为（2）3个元素一组、其余元素一个各一组或者选4个元素分两组（每组2个）、其余元素一个各一组。3个元素一组、其余元素一个各一组：选4个元素分两组（每组2个）、其余元素一个各一组：选4个元素的方案为，分成2组的方案为种，所以有。（3）4个元素一组、其余元素一个各一组，或者选5个元素分两组（一组2个一组3个）、其余元素一个各一组，或者6个元素分三组（每组2个）、其余元素一个各一组。4个元素一组、其余元素一个各一组：。选5个元素分两组（一组2个一组3个）、其余元素一个各一组：选5个元素为，分两组（一组2个一组3个）方案为，所以有。选6个元素分三组（每组2个）、其余元素一个各一组：选6个元素为，分三组（每组2个）的方案为，所以有3.21 (1)会议室中有2n+1个座位，现摆成3排，要求任意两排的座位都占大多数，求有多少种摆法？解：(1)方法1：如果没有附加限制则相当于把2n+1个相同的小球放到3个不同的盒子里，有种方案，而不符合题意的摆法是有一排至少有n+1个座位。这相当于将n+1个座位先放到3排中的某一排，再将剩下的2n+1-(n+1)=n个座位任意分到3排中，这样的摆法共有种方案，所以符合题意的摆法有：方法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+x2n+1，x1+x3n+1，x2+x3n+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且yi0，1i3。显然，x方程满足要求的解与y方程非负整数解一一对应，有种。方法3：要求每行非空如果没有附加限制则相当于把2n+1个相同的小球放到3个不同的盒子里，不允许为空，有种方案，而不符合题意的摆法是有一排至少有n+1个座位。这相当于将n个座位先放到3排中的某一排，再将剩下的2n+1-n=n+1个座位任意分到3排中，每排不允许为空，这样的摆法共有种方案，所以符合题意的摆法有：第四章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)