当前位置:文档之家› 组合数学 试题及答案07

组合数学 试题及答案07

组合数学试题 共 4 页 ,第 1 页
电子科技大学研究生试卷 (考试时间: 19:30 至 21:30 ,共 2 小时)
课程名称 组合数学 教师 学时 40 学分 2 教学方式 讲授 考核日期 2007 年 11 月 27 日 成绩 考核方式: (学生填写)
一、填空题(每空3分,共27分) 1.将6本无区别的书放入3个无区别的箱子中的放法数为 7 ,又每个箱子都不为空的放法数为 3 。

2.将8个有区别的球放入6个无区别的盒子中,每个盒子不空的放法数为 266 ;将8个有区别的球放入7个无区别的盒子中, 每个盒子不空的放法数又为28 。

(注:将9个有区别的球放入7个无区别的盒子中, 每个盒子不空的放法数为462)。

3.现有4个女士6个男士围圆桌就坐,则其中女士两两不相邻的入座方式数有 5!·6·5·4·3= 43200 种; 所有女士坐在一起的方式数有 6!·4!= 17280 种。

4.将单词〝motorola 〞中的所有字母作排列,其排列方式数有 8!/3!=6720 种;其中所有〝o 〞均不相邻的排列方式数有 ⎪⎪⎭⎫ ⎝⎛⨯36!5=2400 种。

(两问均只要求给出解的表达式,不必算出最终结果)。

5. 方程⎩⎨⎧≥≥≥=+++0,1,2123214321x x x x x x x 的整数解的个数为 F(4,9)=220 。







……

……
……
…密
……
……







线



















……




……








效…


……
……

组合数学试题 共 4 页 ,第 2 页
二、(13 分) 给定重集B = {5·a , 3·b , 7·c ,∞·d }。

求B 的9-组合数。

解 令集合S 为{,,,}A B C D ∞⋅∞⋅∞⋅∞⋅的所有8-组合构成的集合。

则有 |S|=F(4,9) = 220。

令 A 1表示S 中至少含有6个a 的元素构成的集合, A 2表示S 中至少含有4个b 的元素构成的集合, A 3表示S 中至少含有8个c 的元素构成的集合, 于是 20)3,4(||1==F A ,56)5,4(||2==F A ,4)1,4(||3==F A 0||||||||321323121=⋂⋂=⋂=⋂=⋂A A A A A A A A A 由容斥原理,所求的9-组合数为 31231231i i j i i j A A A S A A A A A A =≠=-+-∑∑I I I I I =220 – (20+56+4)= 140 三、(12分) 从星期一至星期五安排5位教师A, B, C, D, E 上课,每位教师安排一天,每天安排一位教师。

但要求A 不安排在星期二,B 不安排在星期三和星期五,C 不安排在星期四,D 不安排在星期一,E 不安排在星期三和星期四。

问有多少种不同的安排方案? 解 原问题可模型化为一个5元有禁位的排列. 其禁区棋盘C 如下图的阴影部分。

由图,可得C 的棋盘多项式为 R(C)= = = 1+7x+17x 2+18x 3+8x 4+x 5 所以安排方案数为 5! - 7·4! + 17·3! - 18·2! + 8-1 = 25 即共有25种。

四、(12分)解下列递归关系 ⎩⎨⎧==-=----5,2)2(1451021a a a a a n n n n 解 对应的齐关系的特征方程 x 2-5x -14=0 有根 x 1 = 7,x 2 = -2。

故齐关系的通解为*n a =c 17n +c 2(-2)n 设特解 n a = An (-2)n ,代入原关系:An (-2)n -5A (n -1) (-2)n -1-14A (n -2) (-2)n -2 = (-2)n 学





……

……
……
…密
……
……







线



















……


















…………

A B C D E 1 2 3 4 5
组合数学试题 共 4 页 ,第 3 页
⇒ A = 92 ⇒ n a = 922n n )(- ∴ a n = *n a + n a = c 17n +c 2(-2)n + 922n n )(- 由初值得 ⎪⎩⎪⎨⎧=-=+5942722121-c c c c ⇒ ⎪⎪⎩⎪⎪⎨⎧==8177818521c c ∴ a n = 81857n +8177 (-2)n + 922n n )(- 五、(共11分)对下图中的9个小方格用红、橙、黄、绿四种颜色着色,问: 着红、橙和绿色的小方格的个数均不为3的着色方案数是多少 ?
解:取全集S 为用4种色对9个小方格的着色方案构成的集合。

设A1为S 中着红色的小方格的个数为3的着色方案的集合,A2为S 中着橙色的小方格的个数为3的着色方案的集合,A3为S 中着绿色的小方格的个数为3的着色方案的集合。

有 94=S i A = C(9,3)×36, i =1,2,3 j i A A I = C(9,3) ×C(6,3)×23 ,i, j ∈{1,2,3}, i > j ;321A A A I I = C(9,3) ×C(6,3) ∴ 所求数 = 321A A A I I =49 - 3×C(9,3)×36 + 3×C(9,3) ×C(6,3)×23-1=262144-183708+40320-1=117076。

六、(10分)用2种颜色对下图的棋格着色,证明必存在两列,其着色完全相同。

证明 因每个格子有2种颜色可选,故每列恰有8 种着色方案,现有9列,由鸽笼原理,知学 号 姓 名 学 院 ……………………密……………封……………线……………以……………内……………答……………题……………无……………效……………………
组合数学试题 共 4 页 ,第 4 页 必有两列着色相同.
七、(共15分) 设a n 为出现奇数个2的n 位十进制数的个数。

1.(5分)试建立{a n }的递归关系(不要求解出)。

2.(10分)用母函数法求出a n 。

解:1. ⎩⎨⎧=⨯-1
1098121a a a n n n -+=
2.设a n 是由0,1,……,9组成的满足“2出现奇数次”的长为n 的序列的个数,则a n 的指
数母函数为:
f e (x ) = 2
2)!22!11)(!3!1(810993x x x x x e e e e e x x x x --+-==++++ΛΛ = !)810(210n x n n n n ∑∞
=- 所以 a n = )n n 810(2
1- ,n ≥1 以0为首项的长为n 的序列有a n -1个,在上述序列中去掉以0为首项的长为n 的序列便可得到出现奇数个2的n 位十进制数的个数:
a n -a n -1=)--1187109(2
1n n ⨯-⨯。

相关主题