《组合数学课后答案.doc》由会员分享，可在线阅读，更多相关《组合数学课后答案.doc（14页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
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、根据推论2.2.1，若将3*（100-1）+1=298个人得到3种结果，必有100人得到相同结果。2.9将一个矩形分成(m+1)行列的网格每个格子涂1种颜色，有m种颜色可以选择，证明：无论怎么涂色，其中必有一个由格子构成的矩形的4个角上的格子被涂上同一种颜色。证明： （1）对每一列而言，有（m+1）行，m种颜色，有鸽巢原理，则必有两个单元格颜色相同。 （2）每列中两个单元格的不同位置组合有种，这样一列中两个同色单元格的位置组合共有 种情况 （3）现在有列，根据鸽巢原理，必有两列相同。证明结论成立。2.11证明：从S=1,3,5,599这300个奇数中任意选取101个数，在所选出的数中一定存在2
4、个数，它们之间最多差4。证明： 将S划分为1,3,5，7,9,11, 595,597,599共100组，由鸽巢原理知任意选取101个数中必存在2个数来自同一组，即其差最多为4.2.12证明：从1200中任意选取70个数，总有两个数的差是4，5或9。设从1200中任意选取的70个数构成一组，即第一组： ；第二组： ；第三组：；显然，这三组数均在1209之间，且共有3*70=210个数，根据鸽巢原理一定有两个数相等，又因为任取的这70个数均不相同，所以这2个相等的数一定来自不同组，根据不同组的分布讨论如下：1） 如果这两个数分别来自第一组和第二组，则有；2） 如果这两个数分别来自第一组和第三组，则
5、有；3） 如果这两个数分别来自第二组和第三组，则有；得证。习题三3.8 确定多重集的11-排列数？3.9 求方程，满足的整数解的个数。3.10 架上有20卷百科全书，从中选出4卷使得任意两本的卷号都不相邻的选法有多少种？解：n=20，r=4，3.17 一局乒乓球比赛中，运动员甲以11:7战胜运动员乙，若在比赛过程中甲从来没有落后过，求有多少种可能的比分记录？解：根据题意，相当于求从点(0,0)到点(11,7)且从下方不穿过y=x的非降路径数，即为：3.21 1)会议室中有2n+1个座位，现摆成3排，要求任意两排的座位都占大多数，求有多少种摆法？解：(1)方法1：如果没有附加限制则相当于把2n+
6、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)-
7、3(n+1)=n-1且yi0，1i3。显然，x方程满足要求的解与y方程非负整数解一一对应，有种。方法3：要求每行非空如果没有附加限制则相当于把2n+1个相同的小球放到3个不同的盒子里，不允许为空，有种方案，而不符合题意的摆法是有一排至少有n+1个座位。这相当于将n个座位先放到3排中的某一排，再将剩下的2n+1-n=n+1个座位任意分到3排中，每排不允许为空，这样的摆法共有种方案，所以符合题意的摆法有：(2)会议室中有2n个座位，现摆成3排，要求任意两排的座位都占大多数，求有多少种摆法？解：(2)方法1：如果没有附加限制则相当于把2n个相同的小球放到3个不同的盒子里，有种方案，而不符合题意的摆法
8、是有一排至少有n个座位。这相当于将n个座位先放到3排中的某一排，再将剩下的2n-n=n个座位任意分到3排中，这样的摆法共有种方案。需要注意的是，三排中如果任意两排都是n个座位共有3种情况，这3种情况在中被重复计算了2次，因此需要将重复减去的3次加上。所以符合题意的摆法有：方法2：设第一排座位有x1个，第二排座位有x2个，第三排座位有x3个。x1+x2+x3=2n，且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)-3n-3=n-3且yi0，1i3。显然，x方程满足要求的解与y方
9、程非负整数解一一对应，有种。方法3：要求每行非空如果没有附加限制则相当于把2n个相同的小球放到3个不同的盒子里，不允许为空，有种方案，而不符合题意的摆法是有一排至少有n个座位。这相当于将n-1个座位先放到3排中的某一排，再将剩下的2n-(n-1)=n+1个座位任意分到3排中，每排不允许为空，这样的摆法共有种方案，所以符合题意的摆法有：3.24 n(n2)个不同的球分给甲、乙、丙3人，使得甲至少分得两个球，有多少种不同的分法？解：3.25 24个相同的球分堆，使得每堆的球不少于5，有多少种不同的分堆方法？方法1： 每堆去掉4个球，剩余球分堆的方法数其中习题四4.3 一项对于A,B,C三个频道的收
10、视调查表明，有20%的用户收看A，16%的用户收看B，14%的用户收看C，8%的用户收看A和B，5%的用户收看A和C，4%的用户收看B和C，2%的用户都看。求不收看A,B,C任何频道的用户百分比？解：设性质P1是收看A频道的用户百分比；P2是收看B频道的用户百分比；P3是收看C频道的用户百分比；Ai=x|xSx具有性质Pi，i=1,2,3。S是受调查的所有用户的集合。；根据定理4.1.1，有ACB2327696654.4 某杂志对100名大学新生的爱好进行调查，结果发现他们喜欢看球赛和电影、戏剧。其中58人喜欢看球赛，38人喜欢看戏剧，52人喜欢看电影，既喜欢看球赛又喜欢看戏剧的有18人，既喜
11、欢看电影又喜欢看戏剧的有16人，三种都喜欢看的有12人，求有多少人只喜欢看电影？解：方法1：设性质P1喜欢看球赛；P2喜欢看戏剧；P3喜欢看电影。Ai=x|xSx具有性质Pi，i=1,2,3。S是100名大学新生的集合。由题意可得，这100名大学生中每人至少有三种兴趣中的一种，所以可得既喜欢看球赛有喜欢看电影的人有 因此只喜欢看电影的人有=52-(26+16)+12=22人方法2：方法3：设只喜欢看球赛的人数为x；设只喜欢看电影的人数为y；喜欢看球赛和电影但不喜欢看戏剧的人数为z，则解得y=22，所以22人只喜欢看电影。球赛戏剧电影1264161426224.5 某人有六位朋友，他跟这些朋友每
12、一个都一起吃过晚餐12次，跟他们中任二位一起吃过6次晚餐，和任意三位一起吃过4次晚餐，和任意四位一起吃过3次晚餐，任意五位一起吃过2次晚餐，跟六位朋友全部一起吃过一次晚餐，另外，他自己在外吃过8次晚餐而没碰见任何一位朋友，问他共在外面吃过几次晚餐?解：设n为在外面共吃过晚餐的次数，性质Pi(1i6)表示他和第i位朋友吃过晚餐，Ai(1i6)表示他和第i位朋友吃过晚餐的次数。显然满足对称筛公式，其中由题可得方程：解得吃饭次数为4.13计算棋盘多项式R()。解：R() = x*R()+R() =x*(1+3x+x2)+(1+x)*R( ) = x3+3x2+x+(1+x)xR()+R() = x3
13、+3x2+x+(1+x)x(1+x)+(1+4x+2x2) = 5x3+12x2+7x+14.14 A,B,C,D,E五种型号的轿车，用红、白、蓝、绿、黑五种颜色进行涂装。要求A型车不能涂成黑色；B型车不能涂成红色和白色；C型车不能涂成白色和绿色；D型车不能涂绿色和蓝色；E型号车不能涂成蓝色，求有多少种涂装方案？解：ABCDE红白蓝绿黑ABCDE蓝绿白红黑ABCDE红白绿蓝黑1.若未规定不同车型必须涂不同颜色，则：涂装方案2.若不同车型必须涂不同颜色，则：禁区的棋盘多项式为：R()=R()R()=(1+x)(xR()+R()=(1+x)(xR()R()+R()R()=(1+x)(x(1+2x)
14、 2+(1+3x+x2)2)=1+8x+22x2+25x3+11x4+x5 所以： N =5!-r14!+r23!r32!+r41!- r50! =5！-8*4！+22*3！-25*2！+11*1！-1=20习题五5.1 求如下数列的生成函数。（1）；（2）；（3）； （4）；（5）； （6）；解：5.3 已知数列的生成函数是，求.5.15 知数列的指数生成函数是，求。6.5 平面上有n条直线，它们两两相交且沿有三线交于一点，设这n条直线把平面分成个区域，求的递推关系并求解.解：设n-1条直线把平面分成个区域，则第n条直线与前n-1条直线都有一个交点，即在第n条直线上有n-1个交点，并将其分成
15、n段，这n段又把其所在的区域一分为二。6.6 一个的方格图形用红、蓝两色涂色每个方格，如果每个方格只能涂一种颜色，且不允许两个红格相邻，设有种涂色方案，求的递推关系并求解.解：设f(n)为的方格图形的涂色方案。当n=1时，f(1)=2，即一个方格有红、蓝两种涂色方案。当n=2时，f(2)=3，即两个方格有（红、蓝），（蓝、红）、（蓝、蓝）三种涂色方案。由于不允许两个红格相邻，所以不存在（红、红）的情况。当n2时，如果第一个格子涂为蓝色，则剩余n-1个格子的涂色方案数为f(n-1)；如果第一个格子涂为红色，由于不允许两个红格相邻，所以第二个格子必为蓝色，则剩余n-2个格子的涂色方案数为f(n-2
16、)。于是，当n2时涂色方案数为f(n)= f(n-1)+ f(n-2)。先求解这个递推关系的通解，它的特征方程为解这个方程，得所以，通解为代入初值来确定和，得 求解这个方程组，得 所以，原递推关系的解为 （）.6.7 核反应堆中有和两种粒子，每秒钟内1个粒子可反应产生出3个粒子，而1个粒子又可反应产生出1个粒子和2个粒子.若在t=0s时刻反应堆中只有1个粒子，求t=100s时刻反应堆里将有多少个粒子和粒子.解：设t时刻反应堆中粒子数为，粒子数为在t-1时刻在t时刻 6.8 求下列n阶行列式的值解：当n=1时，当n=2时，当n2时，先求解这个递推关系的通解，它的特征方程为解这个方程，得所以，通解
17、为代入初值来确定和，得 求解这个方程组，得 所以，原递推关系的解为 （）.6.9设h(n)表示n+2条边的凸多边形为它的对角线划分所得的区域数，其中假定没有二条对角线在凸多边形内有一公共点。定义h(0)=0，对n=l，2，证明证明： 如图所示，在凸n+2边形中，划出以任意两相邻边为边的三角形，例如ABC。则余下的是n+1个顶点的凸多边形，它的对角线划分所得的区域数为h(n-1)。由A点引出的对角线共有n-1条，分ABC为n块。下面我们计算一下由A点引出的对角线对n+1条边的凸多边形划分所增加的区域数。 在n+1个顶点中仟取三个，不妨设为D，F，H，其中必有一个顶点(这里是F)使得对角线AF把D和H分在两边。所以对角线DH必与对角线AF相交。又由题意知，这个交点不会有其它对角线通过。这说明每新增加一个交点必与n+1个顶点中的三个顶点相对应。故新增加的交点数为C(n+1,3)个。另外，从A引出的每一条对角线上的交点数正好与这条对角线在凸n+1边形内截成的线段数相同，而每一线段恰好把n+1边形内某一区域分为两个，故新增加区域数为C(n+1,3)个。所以有这是一个线性常系数非齐次递推关系，可以求得