《组合数学》 工学研究生 3.doc

西安电子科技大学研究生课程考试试题考试科目： 组 合 数 学 考试日期： 考试时间： 120 分考试方式： 闭卷 任课教师： 学生姓名： 学 号： 注意：请先阅读完题目后面的要求后再答题！一、 （10分）从集合中选出n个元素排成一列，其中要求所选的全部排在前面，b排在后面，且选出的诸按其下标由小到大进行排列，问共有多少种不同的排列情况。二、 （10分）求五元一次不定方程1010的解数，其中要求i1（i1，2，3，4，5）。三、 （10分）一个居民小区共居住了mn家业主（m、n均大于10），其中有m家是三口之家，有n家是4口之家。过年小区欲选出r个人组成演出队，每家最多选一人参加。设不同的选择方案有种：（1）请构造数列的普母函数G(x)（不要求将G(x)展开成母函数的标准形式）；（2）请计算当r3时，有多少种不同的选择结果。四、 （10分）用红、蓝、黄、绿、紫5种颜色对1n棋盘的小方块进行染色，每个方块染一种颜色，但希望有偶数个方块染红色，偶数个方块染绿色，试求不同的染色方案数。五、 （10分）求线性常系数递推关系的通解。六、 （10分）设n阶行列式的值为，试求满足的递推关系。其中ab0。七、 （10分）设集合S 1，2，n ，把SS的任一非空子集R称为S上的一个二元关系。若对S，有(i, i)R，则称R是自反的；如果(i, j)R，则必有(j, i)R，那么称R为对称的。问S上有多少个自反的或对称的二元关系。八、 （10分）5个单位互相之间进行干部交流。即从每个单位抽调出来一名干部，然后又把大家重新分配到各个单位去工作，每个单位恰好分配一名干部。但是，来自第1个单位的干部不能去第5个单位；来自第5个单位的干部也不能去第1个单位。问共有多少种合适的分配方案？九、 （10分）一个边长为1的正方形内至少需要选多少个点，就能保证在以这些点为顶点的所有三角形中，至少有一个三角形的面积不大于。十、 （10分）从具有6种颜色但大小相同的单色珍珠中选出5颗做成项链，那么，这些项链最多可以分成多少类？其中每条项链至少要用两种颜色的珍珠。要求：（1） 请在试题和试卷上写上学号和姓名；（2） 请给出每一个问题的具体解答过程；（3） 考试时允许携带计算器；（4） 所有的答案都要写在试卷上；（5） 请按题目的顺序书写答案；（6） 请将试题夹在自己的试卷中一并交回；（7） 对于计算题，当计算结果较大时，不要求计算出具体的数字，只要给出答案的表达式即可。如答案为15或20!38!等。2011秋“组合数学”试题 第3页 共3页一、 （10分）从集合中选出n个元素排成一列，其中要求所选的全部排在前面，b排在后面，且选出的诸按其下标由小到大进行排列，问共有多少种不同的排列情况。 分析问题：取k个和nk个b，有 种选法 4分对取定的k个和nk个b，其排列方式只有一种（k0, 1, 2, , n）。故选k个的排列方案共有种 所有排列情况总数为 4分 计算总的排列个数为 2分二、 （10分）求不定方程1010的解数，其中要求i1（i1，2，3，4，5）。 做变量代换化简原方程 3分令（即令，）。则原方程化为1000 问题转换 3分相当于将1000个相同的球放入5个不同的盒子，求不同的放法数。也就是从5种不同元素中可重复地选取1000个元素的组合数。 组合数为或 3分 答：方程的解数为42084793751 1分三、 （10分）一个居民小区共居住了mn家业主（m、n均大于10），其中有m家是三口之家，有n家是4口之家。过年小区欲选出r个人组成演出队，每家最多选一人参加。设不同的选择方案有种：（1）请构造数列的普母函数G(x)（不要求将G(x)展开成母函数的标准形式）；（2）请计算当r3时，有多少种不同的选择结果。 分析问题，构造母函数 3分每家的人都不同，母函数为G(x) 多项式展开 3分G(x) 计算 2分 回答问题 2分当r3时，有种不同的选择结果。或四、 （10分）用红、蓝、黄、绿、紫5种颜色对1n棋盘的小方块进行染色，每个方块染一种颜色，但希望有偶数个方块染红色，偶数个方块染绿色，试求不同的染色方案数。 由题意得母函数 3分 求和函数 3分 母函数展开 3分 答：染色方案数为 1分五、 （10分）求线性常系数递推关系的通解。 写特征方程0 3分 解方程得特征根xi，2（二重根） 3分 所以通解为 3分 说明：其中A、B、C、D为任意常数 1分【注】不要求写出求解过程六、 （10分）设n阶行列式的值为，试求满足的递推关系。其中ab0。 化简行列式 5分将行列式按第一行展开得 求初值： 3分 答:满足的递推关系为 2分【注】不要求写出求解过程七、 （10分）设集合S1，2，n，把SS的任一非空子集R称为S上的一个二元关系。若对S，有(i, i)R，则称R是自反的；如果(i, j)R，则必有(j, i)R，那么称R为对称的。问S上有多少个自反的或对称的二元关系。 分析问题，设A、B 3分设集合A是具有自反性的关系组成的集合，B是具有对称性的关系组成的集合，则AB是具有两种性质的关系组成的集合。 计算、和 4分由A的定义知，A中的关系R包含了所有的元素对(i, i)。故将问题分为两步：第一步选全部(i, i)，只有一种可能；第二步在其余的元素对(i, j)（ij）中任选k个，即可构成一个自反关系R。而其余的元素对共有2(12(n1)n(n1)个，故有种可能，从而；同理，由B的定义知，B中的关系R一定同时含有元素对(i, j)和(j, i)。故同样将问题分两步：第一步选k个元素对(i, j)（ij），有12nn(n1)/2个元素对可选，共有种选择；第二步，若(i, j)R，则将(j, i)也选入R中，只有一种可能，故；计算：先选全部(i, i)，只有一种可能；再选k对(i, j)（ij），有12(n1)n(n1)/2对(i, j)可选，即有种可能；最后选相应的(j, i)，只有1种可能。故。 算总数 3分由题意知，所求为。由容斥原理知八、 （10分）5个单位互相之间进行干部交流。即从每个单位抽调出来一名干部，然后又把大家重新分配到各个单位去工作，每个单位恰好分配一名干部。但是，来自第1个单位的干部不能去第5个单位；来自第5个单位的干部也不能去第1个单位。问共有多少种合适的分配方案？ 画图说明问题：相当于棋子布局问题（下图(a)）（阴影部分不能布棋子） 2分（a） （b） （c） 将禁区A分离为两个小棋盘（上图中的(b)与(c)） 2分 求禁区A的棋盘多项式（最好利用分离的小棋盘计算） 2分 套公式： 2分N(B)5!74! 173! 192! 101! 20!24 答：共有24种合适的分配方案 2分 九、 （10分）一个边长为1的正方形内至少需要选多少个点，就能保证在以这些点为顶点的所有三角形中，至少有一个三角形的面积不大于。 将边长为1的正方形的每条边三等分，将原正方形划分为9个边长为的小正方形 2分 若点数n19，则由抽屉原理知至少有一个小正方形中至少有3个点 2分 那么，此3个点构成的三角形的面积该小正方形的一半，即 2分 当点数n18时，不能保证至少有一个小正方形中至少有3个点 2分 答：最少需要选19个点 2分十、 （10分）从具有6种颜色但大小相同的单色珍珠中选出5颗做成项链，那么，这些项链最多可以分成多少类？其中每条项链至少要用两种颜色的珍珠。 写置换 4分(1)(2)(3)(4)(5)，(12345)（旋转72），(13524)（旋转144） , (14253)（旋转216），(15432)（旋