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

装 订 线 第 1 页 共 2 页第 2 页 共 2 页 学号： 姓名： 哈尔滨工程大学研究生试卷答案哈尔滨工程大学研究生试卷答案 （ 2012 年 秋 季学期） 课程编号： 063301 课程名称： 组合数学 一 （10 分）证明组合等式 二 （10 分）证明任取 11 个整数，求证其中至少有两个数，它们的差是 10 的 倍数。 证明：整数的个位只有 0，1，2，3，4，5，6，7，8，9，只有 10 种可能性，由 鸽巢原理可知， 11 个整数中至少有两个数的个位相同，它们相减就一定是 10 的 倍数。 三 （10 分）在平面上有一个正方形及 n 条直线，每条直线与正方形的两条边相 交且每条直线与其他直线在正方形内均相交，若没有三条以上的直线交于一 点，求这些直线将正方形内部分成的区域的数目 递推关系如下： an=an-1+n a1=2 步骤： (1) 求齐次递推关系的通解求齐次递推关系的通解 an - an-1 =0 m-1=0 m=1（b=1 是是 1 重特征根）重特征根） an=B1 1 n (2) 求非齐次递推关系的特解求非齐次递推关系的特解 an - an-1 =2n-2 且且 1 是是 1 重特征根重特征根 an * = n1(A1 n1+A0) = A1 n2+A0 n 代入得：代入得：A1 n2+A0 n (A1 (n-1)2+A0 (n-1) = n A1=1/2; A0=1/2 an * = 1/2(n2+n) (3) 列出非齐次递推关系的通解形式列出非齐次递推关系的通解形式 a a a n n n * = 1/2(n2+n) + B1 1n (4) 根据初始条件确定待定系数根据初始条件确定待定系数 a1 = B1 = 1 an=1/2(n2+n) + 1 四 （10 分）学校在某学期开设了 54321 C,C,C,C,C 五门不同的课程供五个不 同学院 54321 S,S,S,S,S学生选修，由于条件限制，假设每门课只能为一个学院开 设且每个学院只能也必须选修一门课程，已知 2 S学院的学生不可选修课程 43 C,C； 3 S学院的学生不可选修课程 432 C,C,C； 4 S学院的学生不可选修课程 32 C,C 。问这五个学院的学生可能的选课方案有多少种？ 解：这是一个求解带禁位的排列计数问题 。 = x（）+（） =x)241 ( 2 xx +)31 ( 2 xxx+（） 32 372xxx+ 2 451xx 32 31171xxx 装 订 线 第 3 页共 4 页第 4 页共 4 页 31171 3210 r ,r ,r ,r 则所求的排列方案数为： 123525155 321 !r!r!r!N 五 （10 分）由 9 种颜色珠子组成的长度为 n 的珠串中，要求其中的红色和蓝色 珠子出现的个数之和为偶数。求有多少种这样的珠串？ 解：有题可知，分为两种情况： （1）红色为偶数，且蓝色为偶数； （2）红色为奇数，且蓝色为奇数； G(x)=(1+x 2/2!+x3/3!+.)2(1+x/1!+x2/2!+.)7 +(x+x 3/3!+x5/5!+.)2(1+x/1!+x2/2!+.)7 最后答案： （9 n+5n）/2 六 （10 分）求多重集 S=4a,4b,3c,3d 的 7-组合的个数。 解: 2342232 ( )(1) (1)G xxxxxxxx 出展开式中 7 x前的系数等于 60，即为题目所求之解。 七 （10 分）有n个不同的整数，从中取出两组数来，要求第一组里的最小数大 于第二组里的最大数，问有多少种不同的方案？（要求结果只能用n及常数表示） 解：从n个数中先任取m个数，则有 m n 种取法，将取出的m个数由大到小排 序 ， 设 为 m a ,a ,a 21 ， 再 将 其 分 为 两 组 ， k a ,a 1 ， mk a ,a 1 121m,k，则第一组中的最小数一定大于第二组中的 最大数。故题目所求为： 1 2 m m n n m n m n mm n m n m 22 1 11 n m n n m n m n m n m nnn nn 122 122 1 n n 八 （10 分）某专业运动员在大赛前的 100 天集训中，每天要抽出 1 小时或 2 小 时进行技术理论学习。已知他在任意连续的 10 天内用于理论学习的时间不超过 16 小时。试证明至少存在i和 jij ，使得该运动员在第i天到第 j 天之间刚 好进行了 39 小时的技术理论学习。 证明：设 10021 d ,d ,d为第 1 天，第 2 天， , 第 100 天用于学习的时间, 即 21ord ,k k 由题意可知：对于k ， 911k ，有 16 91 kkk ddd 令 11 dS ， 212 ddS ， 10021100 dddS 分别表示截至第1 天， , 第 100 天该运动员共计用于技术理论学习的时间总和， 由题意可知： 10021 SSS , 且 10029912021111021100 dddddddddS 1601016 100 S 序列 10021 S ,S ,S，393939 10021 S ,S ,S 共计 200项，19939 100 S 即该序列中的数介于 1199 之间。 根据鸽巢原理，其中必有两项相等，但序列中前 100 项为单增，后 100 项也为 单增的。故存在i和j，设ij ，使得： 39 ij SS 装 订 线 第 5 页 共 2 页第 2 页 共 2 页 学号： 姓名： 39 ij SS 即：39 21 jii ddd 九 （10 分）求方程的正整数解的个数。 十 （10 分）使用红、绿、蓝三种颜色对正四面体的四个面进行着色，试问有多 少种不同的着色方案？ 解： 由题可知： （1） 绕如 v1v2 和 v3v4 中点的连线旋转 180 度，所得置换如下： P1=(v1)(v2)(v3)(v4), P2=(v1 v2)(v3 v4), P3=(v1 v3)(v2 v4), P4=(v2 v3)(v1 v4), （2） 绕每一个顶点的中心线旋转 120 度，240 度，所得置换如下： P5=(v1)(v2 v3 v4), P6=(v1)(v2 v4 v3), P7=(v2)(v1 v3 v4), P8=(v2)(v1 v4 v3), P9=(v3)(v1 v2 v4), P10=(v3)(v1 v4 v2), P11=(v4)(v1 v2 v3), P12=(v4)(v1 v3 v2), 由 Polya 定理可知： 不同方案数=（11*32+34）/12=15 装 订 线 第 7 页 共 8 页 第 8 页 共 8 页 试试 卷卷 存存 档档 说说 明明 一、出题 出题时请标明每题分数、总分、课程编号及课程名称。 二、试题印刷 1 公共课：由研究生院负责。 2 专业课：由开课院（系、部）教务办负责。 三、答题册 主考教师到本院（系、部）教务办领取标准统一答题册。 四、评卷要求 （一）试卷批阅原则 1教师评卷时必须按标准（或参考）答案严格掌握评分标准，贯彻公正、准确的原则，并做 到宽严适度、始终如一。 2应先组织试评，掌握尺度以后，再分题到人，两名以上（含两名）授课教师的课程应实行 集体阅卷评分制，集体流水作业，按题分工负责阅卷，阅卷人必须在试卷上签字负责。遇有疑难 问题，可由评卷小组集体讨论，然后定分。 3考核成绩一般应符合正态分布规律，若优秀率偏高或不及格率偏高，任课教师应对此提交 报告作出说明和解释，要维护试卷卷面成绩的严肃性。 4 评卷人员发现试题命题有误， 或答卷雷同等异常情况， 如果是专业课应及时报告学院 （系、 部）主管领导，如果是公共课要及时报研究生院。 5在评卷过程中，各学院（系、部）应组织专人做好复查工作，确保评卷工作质量。对个别 试卷评阅的错漏现象，以及登分、记分错误，复查后需要更改的，应填写成绩更正审批表 ，由 评卷人、教研室主任、学院（系、部）主管领导联合签名，并说明理由，报研究生院批准方能更 正。 6评卷人员要严守纪律，保守秘密，不得向外泄漏评卷情况。不得涂改考生答卷和成绩。 （二）试卷批阅规范 1试卷评阅一律使用书写红色文字的钢笔或圆珠笔。 2记分数字的书写要准确、清晰、工整，如有更改，应有更改人签字。记分使用阿拉伯数字 （如只记得分，不记扣除分；在得分前可不记“+” ）同一试卷册的记分方式必须始终一致。 3 评卷要严格执行标准 （或参考） 答案和评分标准， 客观题的评阅， 每道错误小题必须用 “” 标注；主观题的评阅需按评分点逐个评分，并标注在相应位置，然后得出每小题得分。 4每大题要有一个总得分，标注在该大题的左上角位置，且须与试卷首页题号得分栏一致。 在题号得分栏需评阅人签字，在总分位置需核分人签字。一袋试卷的评阅人或核分人如是同一人， 可在每份试卷上签一个字即可，表