2010级组合数学期末试卷-答案

装订线第1页共1页第页共1页学号：姓名：哈尔滨工程大学研究生试卷（答案）（2010年秋季学期）课程编号：063301课程名称：组合数学一．试叙述下列等式的组合含义nnknnk202证明:设有n个男学生和n名女学生，再要从中选n名学生组成一个社团，问有多少种不同的方案？（3分）则该问题是从2n位学生中选出n位学生的问题，即共有nn2种方案；（2分）该问题还可以看成是：先从n位女学生中选出k位，然后再从那位男学生中选出（n-k）位的不同方案，其中k=0，1，2，…,n,则共有（3分）nkknnkn0nkkn02（2分）故nnknnk202二．某人的电子邮箱密码是由p,h,w三个字母组成的长为n的字符串。在输入密码时，若字符串中有两个p连续出现，则网站直接提示“密码错，请重新输入”。现有黑客通过编程要对其密码进行解密，令na表示程序可以产生的长为n的字符串的个数，写出满足条件的na的递推关系，并对递推关系进行求解。解：an=2an-1+2an-2,a1=3,a2=8（2分）一般形式：an-2an-1-2an-2=0特征方程：m2–2m-2=0（2分）特征根：m1=1+3，m2=1-3通解：an=B1m1n+B2m2n（2分）常系数：B1=6323，B2=6323结果：an=6323(1+3)n+6323(1-3)n（4分）三．8个孩子面朝里围坐在一旋转木马上（如图所示），使每个孩子都面对另一孩子。问有多少种不同的改变方式使每个孩子面对的都与图示的不同？解：设一开始8位孩子如图所示坐在木马上，1A为1a与5a相对就坐的所有就坐方案的集合；2A为2a与6a相对就坐的所有就坐方案的集合；3A为3a与7a相对就坐的所有就坐方案的集合；4A为4a与8a相对就坐的所有就坐方案的集合；（4分）4,3,2,1,!6iAiji且,4,3,2,1,,2!4jiAAji，互不相等kj,i,且,4,3,2,1k,,,2!2A2kjiAAji,2!0AA34321AA（4分）所求问题为：43213212114321AAAA44AAA34-AA24A14-8！8AAAA3222！24-2！46！64-！7（2分）四．我院实验中心有5台超高级服务器，供m个学生通过远程登录去使用，要求使用第1台和第2台的人数均为3个，问有多少种分配方案？解：使用第1台为3人，方案数为C(m,3)；（3分）使用第2台为3人，方案数为C(m-3,3)；（3分）其他m-6个人，每个人都可以登陆剩余的3台服务器中的某一台，方案数为3m-6；（3分）因此，分配方案数为C(m,3)C(m-3,3)3m-6（1分）装订线第3页共4页第4页共4页五．设将n本相同的书放到3个不同的书架上，（书架上的书无序），若第一个书架和第二个书架上摆放相同数量的书，第三个书架上放的书数量不限，问有多少种不同的摆放方式？解：24211)(xxxxxg（4分）xx11112xxx111111412nnnxn132410（4分）所以：nnna13241（2分）六．用3个红色珠子与2个蓝色珠子镶成项链，问有多少种不同的项链？解：应用Burnside引理求解，故：10!2!3!5N；（2分）置换群可定义如下：G={p0,p1,p2,p3,p4,q1,q2,q3,q4,q5}；其中：p0,p1,p2,p3,p4表示旋转，q1,q2,q3,q4,q5表示翻转。0,104131211101pCpCpCpCpC25141312111qCqCqCqCqC（4分）所以，项链数2105210514131211101GqCqCqCqCqCpCl（4分）七．单链DNA可以看作是由符号A、G、C、T组成的n位字符序列，请给出G，C，T至少各出现一次的字符序列的数目解：令A1，A2，A3分别为n位字符序列中不出现G，C，T的集合。（2分）由于n位字符序列中每一位都可能取A、G、C、T四种字符中的一个，因此不允许出现G的n为字符序列的个数是3n，即|Ai|=3n，i=1,2,3；|AiAj|=2n，ij，i，j=1,2,3；|A1A2A3|=1G，C，T至少出现一次的n位字符序列集合即为A1A2A3（4分）A1A2A3=4n-（|A1|+|A2|+|A3|）+（|A1A2|+|A1A3|+|A2A3|）-|A1A2A3|=123334nnn（4分）八．求棋盘多项式（4分）（4分）（2分）九．在一个平面上画出一个圆和n条直线，每条直线都同其它直线交于该圆内部。如果没有三条直线交于一点，问这些直线把这个圆分成多少个区域？解：设n条直线将圆分成Dn个域，则第n条直线被其余的n-1条直线分割成n段，这n段正好是新增加的n个区域的边界。（3分）则：nDDnn1，初始值为21D（3分）所以，nnDDnn)1(2=...=nnD)1(...21=1211nn（4分）装订线第5页共1页第页共1页学号：姓名：十．一卖场中储有k1箱饼干，k2糖，k3箱鲜奶，k4箱食用油，k5箱苹果，k6箱芒果。如果搬运工m分钟能将一箱货物摆到货架上，问需要花费多长时间，肯定能使货架上至少新增n箱相同的货物？（假设k1n,k2n）解：利用鸽巢原理，（4分）为使货架上至少新增n箱相同的货物，则搬运工至少需搬运货物的数量为：14121nkk，而每搬运一件货物需花费m分钟，（4分）故总共需花费的时间至少为mnkk4121（分钟）（2分）（注：每题十分，卷面共计100分）装订线试卷存档说明一、出题出题时请标明每题分数、总分、课程编号及课程名称。二、试题印刷1．公共课：由研究生院负责。2．专业课：由开课院（系、部）教务办负责。三、答题册主考教师到本院（系、部）教务办领取标准统一答题册。四、评卷要求（一）试卷批阅原则1．教师评卷时必须按标准（或参考）答案严格掌握评分标准，贯彻公正、准确的原则，并做到宽严适度、始终如一。2．应先组织试评，掌握尺度以后，再分题到人，两名以上（含两名）授课教师的课程应实行集体阅卷评分制，集体流水作业，按题分工负责阅卷，阅卷人必须在试卷上签字负责。遇有疑难问题，可由评卷小组集体讨论，然后定分。3．考核成绩一般应符合正态分布规律，若优秀率偏高或不及格率偏高，任课教师应对此提交报告作出说明和解释，要维护试卷卷面成绩的严肃性。4．评卷人员发现试题命题有误，或答卷雷同等异常情况，如果是专业课应及时报告学院（系、部）主管领导，如果是公共课要及时报研究生院。5．在评卷过程中，各学院（系、部）应组织专人做好复查工作，确保评卷工作质量。对个别试卷评阅的错漏现象，以及登分、记分错误，复查后需要更改的，应填写《成绩更正审批表》，由评卷人、教研室主任、学院（系、部）主管领导联合签名，并说明理由，报研究生院批准方能更正。6．评卷人员要严守纪律，保守秘密，不得向外泄漏评卷情况。不得涂改考生答卷和成绩。（二）试卷批阅规范1．试卷评阅一律使用书写红色文字的钢笔或圆珠笔。2．记分数字的书写要准确、清晰、工整，如有更改，应有更改人签字。记分使用阿拉伯数字（如只记得分，不记扣除分；在得分前可不记“+”）同一试卷册的记分方式必须始终一致。3．评卷要严格执行标准（或参考）答案和评分标准，客观题的评阅，每道错误小题必须用“×”标注；主观题的评阅需按评分点逐个评分，并标注在相应位置，然后得出每小题得分。4．每大题要有一个总得分，标注在该大题的左上角位置，且须与试卷首页题号得分栏一致。在题号得分栏需评阅人签字，在总分位置需核分人签字。一袋试卷的评阅人或核分人如是同一人，可在每份试卷上签一个字即可，表明该教师对该试卷负责。五、成绩报送任课教师应尽快完成试卷批阅，并在考核结束后7日内（含节假日，对选课人数≥100人的课程可在考试结束后二周内）将成绩单送至教务办公室。六、试卷存档课程考试结束后，送交成绩时将试卷交本单位教务办存档。七、本页仅限存档，印制试题时请勿印刷。审批部门审批意见签字日期系（教研室）院（系）主管领导