组合数学北京理工期末真题2013答案.doc

课程编号：MTH07065 北京理工大学2012 2013学年第二学期计算机科学与技术专业组合数学试题 A卷班级 学号 姓名 成绩 题号一二三四五六七八九十总分成绩一. (10分) 从数集1,2,15中取3个数的子集，要求子集中没有相邻数，有多少种取法。解法一：任选3个数有C(15,3)种方案。两数相邻另一个分离：1,2和14,15这两个相邻数对，各对应另一不相邻数有12种选择；2,3到13,14共12种相邻数对，各对应另一不相邻数有11种选择。三数相邻有13种选择。解法二：任选3个数有C(15,3)种方案。取两个相邻数有14种选择，另一个与已取出两数不同有13种选择。每三个相邻的数在前一步被计数了两次，需要补回一次。解法三：先放12个0排成一排。再在13 个空挡中放3个1，有C(13,3)种方法。在12个0和3个1形成的排列中，数1所在的位置abc，即得到3个不相邻的1到15中的数。解法四：令3个数从小到大排列为a,b,d，满足a+1b，b+1d。令B=b-1,D=d-1，则aBD为从1到13中的数，且无不相邻限制。二. (10分) (1) 求7阶反射Gray码1010111的前驱和后继。(2) 在7阶反射Gray码中，序号是1和2的码是0000000和0000001，求1010111的序号。(1) 1010111的前驱是1010110，后继是1010101。(2) 令b=1100101，则1010111的序号是(b)2+1=102三. (10分) 设有4堆硬币，各堆的硬币数分别是17,25,37,50。游戏人I和II轮流取硬币，游戏人I先取。每次取硬币任选一堆，至少从该取一枚硬币，至多取走该堆的所有硬币。当各堆硬币都取完后游戏结束，最后取硬币的人胜。(1) 证明这个游戏是不平衡的。(2) 游戏人I的第一次取子有哪些取子方式必胜?解：17=(010001)2, 25=(011001)2, 37=(100101)2, 50=(110010)2, (1) 第5位是非平衡位，所以游戏人I有必胜策略。 (2) 17取3，或25取19，或50取5。四. (10分) 将多重集4a,8b中的12个元素沿圆周均匀排列，求方案数。解法一：4a,8b的线排列有12!/(4!8!)=495个2a,4b的线排列有6!/(2!4!)=15个1a,2b的线排列有3!/(1!2!)=3个4a,8b的线排列有周期3,6,12共三种。4a,8b的周期3线排列有3个，周期6线排列有15-3=12个，周期12线排列有495-15=480个。4a,8b的圆排列有3/3+12/6+480/12=43个。解法二：旋转变换群是G=r120, r121, r1211。有1个循环节的变换有r121, r125, r127, r1211, 这些变换C(r12k)=0有2个循环节的变换有r122, r1210, 这些变换C(r12k)=0有3个循环节的变换有r123, r129, 其中1个循环节放入a，这些变换C(r12k)=C(3,1)=3有4个循环节的变换有r124, r128,这些变换C(r12k)=0有6个循环节的变换是r126, 其中2个循环节放入a, C(r126)=C(6,2)=15有12个循环节的变换是r120, 其中4个循环节放入a, C(r120)=C(12,4)=495总圆排列个数是(23+15+495)/12=43五. (10分) 构造两个正交的4阶拉丁方。解：答案不唯一。取4阶有限域GF(4)=是域.其中g为方程x2+x+1 =0的根。令b0,b1,b2,b3分别是0,1,g, 1+g, 令aij(k)=bibk+bj, k=1,2, i,j=0,1,2,3。则A1=(aij(1)i,j=0,1,2,3, A2=(aij(2)i,j=0,1,2,3是两个正交拉丁方 六. (10分) 稻香村生产A,B,C,D共4种不同糕点。一个稻香村礼盒可以装15块糕点，每种糕点至少一块。为控制成本其中C最多可以放5块，D最多可以放7块。有多少种不同的稻香村礼盒？解：每种糕点各一块，还剩11块需要放。令U=4种共11块, E=C放5块以上, 4种共11块, F=D放7块以上, 4种共11块。|U|=C(11+3,3)=364, |E|=C(11-5+3,3)=84, |F|=C(11-7+3,3)=35, |EF|=C(11-5-7+3,3)=0。总方案数为364-84-35+0=245。七. (10分) 求非齐次递推关系 an - 6an-1 +9an-2 = 23n (n 1) 的满足a0 = 1, a1 =3的解。解：递推关系的齐次部分为an - 6an-1 +9an-2 = 0，特征方程为x2-6x+9=0, 特征根为3(二重根)rndn=3n2, r = 3, 是齐次部分的二重根，m=2dn=2, 是0次多项式，q=0特解的形式为c n2 3n, 带入递推关系即 c n2 3n - 6c (n-1)2 3n-1 + 9c (n-2)2 3n-2 = 2 3n，比较系数的c = 1, 得到特解 n2 3n。设递推关系的解为an = s 3n + t n 3n + n2 3n, 带入a0,a1有s = 13s + 3t + 3 = 3解方程组得到s=1, t=-1，所以原方程的解为an = (1-n+n2)3n (n0).八. (4+3+3=10分) 二分图G如右图，M=x1, y1,x3, y2,x4, y4,x5, y5是G的一个匹配，(1) 找一条M-交错路径。(2) 找一个G的最大匹配。(3) 找一个G的最小覆盖。答案不唯一。(1) M-交错链 x6, y5, x5, y4, x4, y6(2) x1,y1, x3,y2, x4,y6, x5,y4, x6,y5(3) x3,y1,y4,y5,y6九. (10分)用红黄蓝3种颜色给1n(n1)棋盘染色，其中红色必须有奇数格，黄色必须有偶数格，且至少有一格染蓝色。求方案数。解：令1n(n1)棋盘染色方案数是hn，则(hn)n0指数生成函数为 所以对n0，方案数为(3n-2n-(-1)n+(-2)n)/4 十. (10分) 任取两个正整数p,q ( p q )，做整数带余除法：10p = a1 q + r1， ( 0 r1 q )10r1 = a2 q + r2， ( 0 r2 q )10r2 = a3 q + r3， ( 0 r3 q ) 其中ai,ri都是非负整数，如此一直继续(可能出现0)，那么有理数p/q的十进表示是0.a1a2a3。(1) 求3/14的十进制展开。举例说明ai =aj(ij)不蕴含ai+1=aj+1。(2)