组合数学期末试卷及答案.pdf

《组合数学期末试卷及答案.pdf》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、步骤：(1)求齐次递推关系的通解哈尔滨工程大学研究生试卷答案an-an-1=0m-1=0m=1（b=1是1重特征根）（2012年秋季学期）nan=B11课程编号：063301课程名称：组合数学(2)求非齐次递推关系的特解an-an-1=2n-2且1是1重特征根一．（10分）证明组合等式*=n1(A12an1n+A0)=A1n+A0n22代入得：A1n+A0n–(A1(n-1)+A0(n-1))=nA1=1/2;A0=1/2*2an=1/2(n+n)：(3)列出非齐次递推关系的通解形式

2、*2n姓名anaan=1/2(n+n)+B11n(4)根据初始条件确定待定系数装a1=B1=12订an=1/2(n+n)+1二．（10分）证明任取11个整数，求证其中至少有两个数，它们的差是10的四．（10分）学校在某学期开设了C,C,C,C,C五门不同的课程供五个不线12345倍数。同学院S,S,S,S,S学生选修，由于条件限制，假设每门课只能为一个学院开12345设且每个学院只能也必须选修一门课程，已知S学院的学生不可选修课程2证明：整数的个位只有0，1，2，3，4，5，6，7，8，9，只

3、有10种可能性，由C,C；S学院的学生不可选修课程C,C,C；S学院的学生不可选修课程3432344鸽巢原理可知，11个整数中至少有两个数的个位相同，它们相减就一定是10的C,C。问这五个学院的学生可能的选课方案有多少种？23倍数。解：这是一个求解带禁位的排列计数问题。三．（10分）在平面上有一个正方形及n条直线，每条直线与正方形的两条边相：交且每条直线与其他直线在正方形内均相交，若没有三条以上的直线交于一==x（）+（）学号点，求这些直线将正方形内部分成的区域的数目=x(14x2x2)+x(1

4、3xx2)+（）2x7x23x3+15x4x2递推关系如下：an=an-1+na1=217x11x23x3第1页共2页第2页共2页r1,r7,r11,r3nn0123m1m2m则所求的排列方案数为：nnnnN5!r51!r52!r53!12m123m2mm2mnnnnmnn1五．（10分）由9种颜色珠子

5、组成的长度为n的珠串中，要求其中的红色和蓝色m1mm1mnnn2n21n珠子出现的个数之和为偶数。求有多少种这样的珠串？n1n221解：有题可知，分为两种情况：（1）红色为偶数，且蓝色为偶数；（2）红色为奇数，且蓝色为奇数；八．（10分）某专业运动员在大赛前的100天集训中，每天要抽出1小时或2小时进行技术理论学习。已知他在任意连续的10天内用于理论学习的时间不超过23227G(x)=(1+x/2!+x/3!+..)(1+x/1!+x/2!+..

6、)jjij16小时。试证明至少存在i和，使得该运动员在第i天到第天之间刚35227好进行了39小时的技术理论学习。+(x+x/3!+x/5!+..)(1+x/1!+x/2!+..)nn证明：设d1,d2,,d100为第1天，第2天，…,第100天用于学习的时间,即装最后答案：（9+5）/2k,d1or2k六．（10分）求多重集S={4a,4b,3c,3d}的7-组合的个数。由题意可知：对于k，1k91，有ddd16订kk1k92342232解:Gx()(1xx

7、xx)(1xxx)令Sd，Sdd，Sddd1121210012100线分别表示截至第1天，…,第100天该运动员共计用于技术理论学习的时间总和，7出展开式中x前的系数等于60，即为题目所求之解。由题意可知：SSS,12100且Sddddddddd10012101121209129100七．（10分）有n个不同的整数，从中取出两组数来，要求第一组里的最小数大于第二组里的最大数，问有多少种不同的方案？（要求结果只能用n及常数表示

8、）S1001610160n序列S,S,,S，S39,S39,,S39共计200项，S391991210012100100解：从n个数中先任取m个数，则有种取法，将取出的m个数由大到小排m即该序列中的数介于1~199之间。序，设为a,a,,a，再将其分为两组，a,,a，12m1k根据鸽巢原理，其中必有两项相等，但序列中前100项为单增，后100项也为ak1,,amk1,2,,m1，则第一组中的最小数一定大于