组合数学课后

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、巢原理知，起码有2个坐标的状况同样。又要想使中点的坐标也是整数，则其两点连线的坐标之和为偶数。因为奇数+奇数=偶数；偶数+偶数=偶数。所以只要找以上2个状况同样的点。而已证明：存在起码2个坐标的状况同样。证明建立。方法二：关于平面上的随意整数坐标的点而言，其坐标值对2取模后的可能取值只有4种状况，即：(0,0),(0,1),(1,0),(1,1)，依据鸽巢原理5个点中必有2个点的坐标对2取模后是同样种类的，那么这两点的连线中点也必为整数。2.4一次选秀活动，每一个人表演后可能获得的结果分别为“经过”、“裁减”和“待定”，起码有多少人参加才能保证必有100个人获得同样的结果？证明：依据推论，若将

3、3*（100-1）+1=298个人获得3种结果，必有100人获得同样结果。m12.9将一个矩形分红(m+1)行m1列的网格每个格子涂1种颜色，有m种颜色能够选择，证明：不论2怎么涂色，此中必有一个由格子组成的矩形的4个角上的格子被涂上同一种颜色。证明：（1）对每一列而言，有（m+1）行，m种颜色，有鸽巢原理，则必有两个单元格颜色同样。（2m1）每列中两个单元格的不一样地点组合有种，这样一列中两个同色单元格的地点组合共有2m1m种状况213）此刻有m1列，依据鸽巢原理，必有两列同样。证明结论建立。22.11证明：从S=1,3,5,599这300个奇数中随意选用101个数，在所选出的数中必定存在2

4、个数，它们之间最多差证明：4。将S区分为1,3,5，7,9,11同一组，即其差最多为4.,595,597,599共100组，由鸽巢原理知随意选用101个数中必存在2个数来自2.12证明：从1200中随意选用70个数，总有两个数的差是4，5或9。设从1200中随意选用的70个数组成一组，即第一组：a1,a2,a70；第二组：a14,a24,a704；第三组：a19,a29,a709；明显，这三组数均在1209之间，且共有3*70=210个数，依据鸽巢原理必定有两个数相等，又因为任取的这70个数均不同样，所以这2个相等的数必定来自不一样组，依据不一样组的散布议论以下：1）假如这两个数分别来自第一组

5、和第二组，则有ajai4；2）假如这两个数分别来自第一组和第三组，则有ajai9；3）假如这两个数分别来自第二组和第三组，则有ajai5；得证。习题三3.8确立多重集M3a,4b,5c的11-摆列数？3.9求方程x1x2x3x420，知足x12,x20,x35,x41的整数解的个数。3.10架上有20卷百科全书，从中选出4卷使得随意两本的卷号都不相邻的选法有多少种？nr12041172380解：n=20，r=4，r443.17一局乒乓球竞赛中，运动员甲以11:7战胜运动员乙，若在比胜过程中甲素来没有落伍过，求有多少种可能的比分记录？解：依据题意，相当于求从点(0,0)到点(11,7)且从下方不

6、穿过y=x的非降路径数，即为：3.211)会议室中有2n+1个座位，现摆成3排，要求随意两排的座位都占大部分，求有多少种摆法？解：(1)方法1：假如没有附带限制则相当于把2n+1个同样的小球放到3个不一样的盒子里，有2n1312n3n+1个座位。这相当于将n+1个座3-12种方案，而不切合题意的摆法是有一排起码有位先放到3排中的某一排，再将剩下的2n+1-(n+1)=n个座位随意分到3排中，这样的摆法共有32n1(n1)31n223种方案，所以切合题意的摆法有：2方法2：设第一排座位有x1个，第二排座位有x2个，第三排座位有x3个。x1+x2+x3=2n+1，且x1+x2(2n+1)/2，x1

7、+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方程非负整数解一一对应，有n131n1种。312方法3：要求每行非空假如没有附带限制则相当于把2n+1个同样的小球放到3个不一样的盒子里，不一样意为空，有2n112nn+1个座位。这相当于将n个座位先放到3-1种方案，而不切合题意的摆法是有一排起码有23排中的某一排，再将剩下的2n+1-n=n+1个座位随意

8、分到3排中，每排不一样意为空，这样的摆法共有32n1n1n3种方案，所以切合题意的摆法有：22(2)会议室中有2n个座位，现摆成3排，要求随意两排的座位都占大部分，求有多少种摆法？解：(2)方法1：假如没有附带限制则相当于把2n个同样的小球放到3个不一样的盒子里，有2n312n2n个座位。这相当于将n个座位先放2种方案，而不切合题意的摆法是有一排起码有2到3排中的某一排，再将剩下的2n-n=n个座位随意分到3排中，这样的摆法共有32nn31n2n3种情232种方案。需要注意的是，三排中假如随意两排都是个座位共有n22次，所以需要将重复减去的3次加上。所以切合题意的摆法况，这3种状况在3中被重复

9、计算了2有：方法2：设第一排座位有x1个，第二排座位有x个，第三排座位有x个。x123，且12n，+x3n+1，x23n+1，令y1+x+x=2nx1+x12-n-1，213-n-1，323-n-1123=2(2n)-3n-3=n-3且x+x=x+xy=x+xy=x+xy+y+yyi0，1i3。明显，x方程知足要求的解与y方程非负整数解一一对应，有n331n1312种。方法3：要求每行非空假如没有附带限制则相当于把2n个同样的小球放到3个不一样的盒子里，不一样意为空，有2n12n1n个座位。这相当于将n-1个座位先放到322种方案，而不切合题意的摆法是有一排起码有排中的某一排，再将剩下的2n-

10、(n-1)=n+1个座位随意分到3排中，每排不一样意为空，这样的摆法共有32n(n1)1n23种方案，所以切合题意的摆法有：23.24n(n2)个不一样的球分给甲、乙、丙3人，使得甲起码分得两个球，有多少种不一样的分法？n解：3n2nn2n1i22nii3.2524个同样的球分堆，使得每堆的球许多于5，有多少种不一样的分堆方法？方法1：每堆去掉4个球，节余球分堆的方法数此中习题四4.3一项关于A,B,C三个频道的收视检查表示，有C，8%的用户收看A和B，5%的用户收看20%的用户收看A，16%的用户收看B，14%的用户收看A和C，4%的用户收看B和C，2%的用户都看。求不收看A,B,C任何频道

11、的用户百分比？解：设性质P1是收看A频道的用户百分比；P2是收看B频道的用户百分比；P3是收看C频道的用户百分比；Ai=x|xSx拥有性质Pi，i=1,2,3。S是受检查的所实用户的会合。|S|1；依据定理，有65A9632627BC4.4某杂志对100名大学重生的喜好进行检查，结果发现他们喜爱看球赛和电影、戏剧。此中58人喜爱看球赛，38人喜爱看戏剧，52人喜爱看电影，既喜爱看球赛又喜爱看戏剧的有18人，既喜爱看电影又喜爱看戏剧的有16人，三种都喜爱看的有12人，求有多少人只喜爱看电影？解：方法1：设性质P1喜爱看球赛；P2喜爱看戏剧；P3喜爱看电影。Ai=x|xSx拥有性质Pi，i=1,2

12、,3。S是100名大学重生的会合。由题意可得，这100名大学生中每人起码有三种兴趣中的一种，所以可得既喜爱看球赛有喜爱看电影的人有所以只喜爱看电影的人有=52-(26+16)+12=22人方法2：方法3：设只喜爱看球赛的人数为x；设只喜爱看电影的人数为y；喜爱看球赛和电影但不喜爱看戏剧的人数为z，则解得y=22，所以22人只喜爱看电影。球赛261461222416电影戏剧4.5某人有六位朋友，他跟这些朋友每一个都一同吃过晚饭意三位一同吃过4次晚饭，和随意四位一同吃过12次，跟他们中任二位一同吃过6次晚饭，和任3次晚饭，随意五位一同吃过2次晚饭，跟六位朋友所有一同吃过一次晚饭，此外，他自己在外吃

13、过餐?8次晚饭而没遇见任何一位朋友，问他共在外面吃过几次晚解：设n为在外面共吃过晚饭的次数，性质Pi(1i6)表示他和第i位朋友吃过晚饭，Ai(1i6)表示他和第i位朋友吃过晚饭的次数。明显知足对称筛公式，此中由题可得方程：|A1A2A3A4A5A6|nC6112C626C634C643C652C6618解得吃饭次数为C6112C626C634C643C652C6618364.13计算棋盘多项式R()。解：R()=x*R()+R()=x*(1+3x+x2)+(1+x)*R()=x3+3x2+x+(1+x)xR()+R()322324.14A,B,C,D,E五种型号的轿车，用红、白、蓝、绿、黑五

14、种颜色进行涂装。要求车不可以涂成红色和白色；C型车不可以涂成白色和绿色；D型车不可以涂绿色和蓝色；A型车不可以涂成黑色；B型E型号车不可以涂成蓝色，求有多少种涂装方案？解：ABCDE红白蓝绿黑ABCDE蓝绿白红黑ABCDE红白绿蓝黑1.若未规定不一样车型一定涂不一样颜色，则：涂装方案433344322.若不一样车型一定涂不一样颜色，则：禁区的棋盘多项式为：R()=R()R()=(1+x)(xR()+R()=(1+x)(xR()R()+R()R()=(1+x)(x(1+2x)2+(1+3x+x2)2)=1+8x+22x2+25x3+11x4+x5所以：N=5!-r14!+r23!r32!+r41

15、!-r50!=5！-8*4！+22*3！-25*2！+11*1！-1=20习题五5.1求以下数列的生成函数。（1）ak(1)k(k1)；（2）ak(1)kk2k；（3）akk6；（4）akk(k2)；（5）aknk（6）akkk；3；解：5.3已知数列ak的生成函数是A(x)23x9x2，求ak.13x5.15知数列ak的指数生成函数是Gx(x)x25ex，求ak。6.5平面上有n条直线，它们两两订交且沿有三线交于一点，设这n条直线把平面分红f(n)个地区，求f(n)的递推关系并求解.解：设n-1条直线把平面分红f(n-1)个地区，则第n条直线与前n-1条直线都有一个交点，即在第n条直线上有n

16、-1个交点，并将其分红n段，这n段又把其所在的地区一分为二。6.6一个1n的方格图形用红、蓝两色涂色每个方格，假如每个方格只好涂一种颜色，且不一样意两个红格相邻，设f(n)有种涂色方案，求f(n)的递推关系并求解.解：设f(n)为1n的方格图形的涂色方案。当n=1时，f(1)=2，即一个方格有红、蓝两种涂色方案。当n=2时，f(2)=3，即两个方格有（红、蓝），（蓝、红）、（蓝、蓝）三种涂色方案。因为不一样意两个红格相邻，所以不存在（红、红）的状况。当n2时，假如第一个格子涂为蓝色，则节余n-1个格子的涂色方案数为f(n-1)；假如第一个格子涂为红色，因为不一样意两个红格相邻，所以第二个格子必

17、为蓝色，则节余n-2个格子的涂色方案数为f(n-2)。于是，当n2时涂色方案数为f(n)=f(n-1)+f(n-2)。先求解这个递推关系的通解，它的特点方程为解这个方程，得所以，通解为代入初值来确立c1和c2，得求解这个方程组，得所以，原递推关系的解为（n0,1,2,）.6.7核反响堆中有和两种粒子，每秒钟内1个粒子可反响产生出3个粒子，而1个粒子又可反响产生出1个粒子和2个粒子.若在t=0s时刻反响堆中只有1个粒子，求t=100s时刻反响堆里将有多少个粒子和粒子.解：设t时刻反响堆中粒子数为f(t)，粒子数为g(t)在t-1时刻在t时刻6.8求以下n阶队列式的值dn解：当n=1时，d122当n=2时，d221132当n2时，dn2dn-1dn-2先求解这个递推关系的通解，它的特点方程为解这个方程，得所以，通解为代入初值来确立c1和c2，得求解这个方程组，得所以，原递推关系的解为f(n)n1（n0,1,2,）.6.9设h(n)表示n+2条边的凸多边形为它的对角线区分所得的地区数，此中假定没有二条对角线在凸多边形内有一公共点。定义h(0)=0，对n=l，2，证明证明：以下图，在凸n+2边形中，划出以随意两相邻边为边的三角形，比如ABC。则余下的是n+1的凸多边形，它的对角线区分所得的地区数为h(n-1)。由A点引出的对角线共有n-1条，分ABC为下边我们计算一下由