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

1、吉林大学组合数学习题解答作者:日期:第二章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、（偶数，偶数）；（偶数,奇数）。由i巢原理知，至少有2个坐标的情况相同。又要想使中点的坐标也是整数，则其两点连线的坐标之和为偶数。因为奇数+奇数 =偶数；偶数+偶数=偶数。因此只需找以上2个情况相同的点。而已证明：存在至少2个坐标的情况相同。证明成立。第三章3.4教室有两排，每排8个座位。现有学生14人，其中的5个人总坐在前排，4个人总坐在后排，求有多少种方法将学生安排在座位上？54.解：刖排8个座位，5人固定，共c8*5!种方法；后排8个座位，4人固定洪c8*4!种方法；前排和后排还剩7个座位，由剩下的5人挑选5个座位，共c5*5!种方法；则一共有c； * c； * c5 *5!*5!*4!

3、p5 * p4 * p75 28449792000 种安排方法。另一种解法：c5p86p88 c52p87p87 c；p：r6 p85 p84 p75 140 8! 7!。3.5 将英文字母表中的26个字母排序，要求任意两个元音字母不能相邻，则有多少种排序方法？解：先排21个辅音字母，共有21!再将5个元音插入到2 2个空隙中，p22故所求为21!葭吸c52p553.6 有6名先生和6名女士围坐一个圆桌就餐，要求男女交替就坐， 则有多少种不同的排坐方式？解：6男全排列6! ;6女全排列6 !; 6女插入6男的前6个空或者后6个空，即女打头或男 打头 6!* 6 ! * 2 ;再除以围圈重复得（

4、6 !* 6 !* 2 ）/1 2 =6! *5!=8 6 4003.7 15个人围坐一个圆桌开会，如果先生a拒绝和先生b和c相邻，那么有多少种排坐方 式？解：方法1:除b和c以外，a可以在剩余的12人中挑选2人坐在自己的两边，有c122p22。将a与其两边的人看作一个元素，与其他12个人形成共13个元素的圆排列，有（13-1）!,所以共有 ci2p2 (13 1)!电12!= 63228211200 种排歹u。1112种。b和万法2:除去a、b和c的12人共有p1种坐法，人在12人中插入位置的坐法有c不与 a相邻的坐法共有1 1 * 12种，由于 1 5人围成圆桌坐，故排列方式共有_11 _

5、 _p112 11 12 132 12!=6 3 22 8 21 1 20 0 种坐法。3.9求方程x1x2x3x420 ,满足x1 2, x2 0, x3 5,x41的整数解的个数。14 4 16803.10书架上有解：20卷百科全书,从中选出4卷使得任意两本的卷号都不相邻的选法有多少种n=20, r =4,n r 120 4 11723804相当于有16卷已经排好，把4卷插入到人“ ，17，4 上一人17个“空隙”中，有种，对应序号都不会相邻。43.20证明：(1) s n,31)2n(2)s n,n(3) s n,nn 105n 156证明：（1）组合分析方法: n个元素分成 n个元素分

6、成 n个元素分成n个元素分成3组，允许为空的方案为3n；3组，有一组必为空的方案为 3* 2 n；3组，有两组必为空的方案为3 3组，根据容斥原理，不允许为空的方案为 3n-3*2 n+ 3 ;不考虑组间顺序，方案为 33 1（3n1 1） 2n 13!2(2)nnsn,n 23343个元素一组、其余元素一个各一组或者选4个元素分两组（每组2个）、其余元素个各一组。n3个元素一组、其余元素一个各一组：3选4个元素分两组（每组2个）、其余元素一个各一组：选 4个元素的方案为 n ,分成42组的方案为 4 /2! 3种,所以有3 n24(3)nnns n,n 310154564个元素一组、其余元素

7、一个各一组，或者选5个元素分两组（一组 2个一组3个）、其余元素一个各一组，或者 6个元素分三组（每组2个）、其余元素一个各一组。n4个元素一组、其余元素一个各一组 ：45个元素为选5个元素分两组（一组2个一组3个）、其余元素一个各一组：选分两组（一组2个一组3个）方案为 52n10,所以有10。53! 15,所以有n156选6个元素分三组（每组2个）、其余元素一个各一组：选 6个元素为 n ,分三组（每6， 人 6组2个）的方案为2223.21 （1 ）会议室中有2 n+ 1个座位，现摆成 少种摆法？解：3排，要求任意两排的座位都占大多数，求有多方法1 :如果没有附加限制则相当于把2 n +

8、1个相同的小球放到 3个不同的盒子里，有2n 1 3 13-1n+ 1个座位。这2n 3种方案，而不符合题意的摆法是有一排至少有 2相当于将n+ 1个座位先放到3排中的某一排，再将剩下的2n+1- ( n + 1 )=n个座位任意分到3排中，这样的摆法共有2n 1 (n 1) 3 1 23 n 2种方案，所以符合题意2的摆法有:2n 3 n 2 n 13222方法2 :设第一排座位有x1个，第二排座位有x2个,第三排座位有 x3个。x1 +x2+x3= 2n+1 ,且 xi+x 2 n +1)/2 ,3 n+1x2+x3n+ 1,令 yi =x1+x3(2 n + 1)/2,x2+x3(2 n

9、 + 1) /2,即 x1+x2 n+1, x 1+xx 1+x2-n 1,y2= x 1+x3-n- 1 ,y3= x2+x3-n 1,可知 y 1 + y2+y 3=2(2n+l) -3 (n + 1)=n-1且y i0 ,1m3。显然，x方程满足要求的解与y方程非负整数解一一对应，有n 1 3 1 n 1 种。3 12方法3 :要求每行非空如果没有附加限制则相当于把 2n + 1个相同的小球放到 3个不同的盒子里，不允许为空，有2n 1 1 2n种方案，而不符合题意的摆法是有一排至少有n+1个座位。这相当3-12于将n个座位先放到3排中的某一排，再将剩下的2 n+1 -n = n+1个座

10、位任意分到 3排中,每排不允许为空，这样的摆法共有32n 1n 13 n种方案，所以符合题意的摆法22有：2n n n 13222第四章4.13计算棋盘多项式r ( p)。=x * r( )+r(二*(1+3x+x2)+( 1 + x) *x +3x 2 + x+ ( 1 + x) x rx s + 3 x2+ x+(1+ x )x(1+ x )+ (1+ 4 x+ 2 x2) =5x3+1 2 x2+7x+1第五章2 3x 9x25.3 已知数列 ak的生成函数是a(x)1 3x，求 ak.22 3x 9x 2k ka(x) 3x 2 3kxk 3x1 3x 1 3x k o9 k 1akkk 2 3k k 15 .7一个1xn的方格图形用红、