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

课程编号：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种选择。

152121211132863解法二：任选3个数有C(15,3)种方案。取两个相邻数有14种选择，另一个与已取出两数不同有13种选择。每三个相邻的数在前一步被计数了两次，需要补回一次。

151413132863解法三：先放12个0排成一排。再在13 个空挡中放3个1，有C(13,3)种方法。在12个0和3个1形成的排列中，数1所在的位置abc，即得到3个不相邻的1到15中的数。

132863解法四：令3个数从小到大排列为a,b,d，满足a+1132863二. (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分) 将多重集{4a,8b}中的12个元素沿圆周均匀排列，求方案数。 解法一：

{4a,8b}的线排列有12!/(4!8!)=495个 {2a,4b}的线排列有6!/(2!4!)=15个 {1a,2b}的线排列有3!/(1!2!)=3个

{4a,8b}的线排列有周期3,6,12共三种。{4a,8b}的周期3线排列有3个，周期6线排列有15-3=12个，周期12线排列有495-15=480个。 {4a,8b}的圆排列有3/3+12/6+480/12=43个。 解法二：

旋转变换群是G={120, 121,…, 1211}。

有1个循环节的变换有121, 125, 127, 1211, 这些变换C(12k)=0 有2个循环节的变换有122, 1210, 这些变换C(12k)=0

有3个循环节的变换有123, 129, 其中1个循环节放入a，这些变换C(12k)=C(3,1)=3 有4个循环节的变换有124, 128,这些变换C(12k)=0

有6个循环节的变换是126, 其中2个循环节放入a, C(126)=C(6,2)=15 有12个循环节的变换是120, 其中4个循环节放入a, C(120)=C(12,4)=495

总圆排列个数是(23+15+495)/12=43 五. (10分) 构造两个正交的4阶拉丁方。

解：答案不唯一。取4阶有限域GF(4)=<{0,1,, 1+}, + mod 2,  mod 2>是域.其中为方程x2+x+1 =0的根。令b0,b1,b2,b3分别是0,1,, 1+, 令aij(k)=bibk+bj, k=1,2, i,j=0,1,2,3。

(2)

则A1=(aij(1))i,j=0,1,2,3, A2=(a ij )i,j=0,1,2,3是两个正交拉丁方

011101101110011110110110六.(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, |E∪F|=C(11-5-7+3,3)=0。总方案数为364-84-35+0=245。 七. (10分) 求非齐次递推关系 an - 6an-1 +9an-2 = 23n (n > 1) 的满足a0 = 1, a1 =3的解。 解：递推关系的齐次部分为an - 6an-1 +9an-2 = 0， 特征方程为x2-6x+9=0, 特征根为3(二重根) rndn=3n×2,

.

r = 3, 是齐次部分的二重根，m=2

dn=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 = 1

3s + 3t + 3 = 3

解方程组得到s=1, t=-1，所以原方程的解为an = (1-n+n2)3n (n0). 八.(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种颜色给1n(n1)棋盘染色，其中红色必须有奇数格，黄色必须有偶数格，且至少有一格染蓝色。求方案数。

解：令1n(n1)棋盘染色方案数是hn，则(hn)n>0指数生成函数为

322xxxxx   )( 1   )(    ) ( 1!3!2!1!2! xeexexex(ex1) 2 2

1(e3xe2xexe2x)4  n 132n(1)n(2)nnx 4n!n0所以对n0，方案数为(3n-2n-(-1)n+(-2)n)/4

十. (10分) 任取两个正整数p,q ( p < q )，做整数带余除法： 10p = a1  q + r1， ( 0  r1 < q ) 10r1 = a2  q + r2， ( 0  r2 < q ) 10r2 = a3  q + r3， ( 0  r3 < q ) …

其中ai,ri都是非负整数，如此一直继续(可能出现0)，那么有理数p/q的十进表示是0.a1a2a3…。

(1) 求3/14的十进制展开。举例说明ai =aj(i(3) 用鸽巢原理证明有理数的十进制表示一定会最终周期(最终全0也是最终周期)。

.

证明：

(1) 3/14=0.a1a2a3…, 其中a1a2a3a4a5a6a7=2142857, 而且ai=ai+6, 对任意i>1。其中a2=a4，但是a3a6。

(2) 对相同的整数作带余除法会得到相同的商和余数，所以若有ii，an=an+j-i，即十进制表示最终周期。

(3) 因为r1, r2, …, rq是取值于0到q-1之间的整数，其中一定有两个相同的。再根据(2)，有理数的十进制展开一定会最终周期。

.