组合数学 工学研究生 2

1、西安电子科技大学研究生课程考试试题考试科目： 组 合 数 学 考试日期：考试方式： 闭卷 任课教师： 学生姓名： 学 号： 注意：请先阅读完题目后面的要求后再答题！一、 （10分）设盒子中有3n个球，其中有n个样子相同的红球和n个样子相同的篮球，而其余的n个球的颜色互相都不一样，且都不是红色或蓝色。现从中随机取出n个球（不考虑取出来的球的次序），且要求红球和篮球一样多。那么，当n为偶数时，可能有多少种不同的选取结果？此题不允许用母函数方法求解。二、 （10分）请利用二项式展开的方法求被13除所得的余数。三、 （10分）将n元面值为1元的人民币分给四名同学，且要求同学甲与乙分得的钱一样多，同学丙

2、与丁一样多，同时还要求甲同学至少分得2元钱。问共有多少种不同的分法？四、 （10分）设集合S1, 1, 1, 2, 2, 2, 3, 3, 3, 3，试问由集合S的10个基本数字可构成多少个不同的四位数？五、 （10分）由a、b、c、d、e五个基本符号组成n位符号串，其中希望相邻的两个字母不能同时为a，请问满足条件的串共有多少个？六、 （10分）平面上有两两相交，但无3线共点的n条直线，试求这n条直线把平面分成多少个区域？七、 （10分）现有t种不同颜色的球，其中第i种颜色的球有个（i1, 2, , t）。要把这些球放入m个不同的盒子中，且使每个盒子至少放入一个球，问共有多少种不同的放法？八、

3、 （10分）某班每天放学后都要打扫卫生，其项目有扫地、整理桌椅、擦窗子和擦黑板共4项工作，故每天留下4名同学打扫卫生，每人恰好完成其中的一项。而今天留下的4名同学中，甲愿意整理桌椅或擦窗子，乙则不愿意擦窗子，丙不愿意整理桌椅，丁同学对每一项工作都不挑剔。那么，能给出多少种安排打扫卫生的方案，使得每个同学都不用干自己不愿意干的工作？九、 （10分）设n是大于1的奇数，证明在整数，中必有一个数能被n整除。十、 （10分）桌子上放着一些大小一样的等边三角形木框，且每个木框的每条边都被染成了彩色。经统计，所用的颜色共有10种。那么，如果按照木框的边的颜色异同对其进行分类，请问这些木框最多可以分成多少类

4、。要求：（1） 请在试题和试卷上写上学号和姓名；（2） 请给出每一个问题的具体解答过程；（3） 考试时允许携带计算器；（4） 所有的答案都要写在试卷上；（5） 请按题目的顺序书写答案；（6） 请将试题夹在自己的试卷中一并交回；（7） 对于计算题，当计算结果较大时，不要求计算出具体的数字，只要给出答案的表达式即可。如答案为15或20!3×8!等。一、 （10分）设盒子中有3n个球，其中有n个样子相同的红球和n个样子相同的篮球，而其余的n个球的颜色互相都不一样，且都不是红色或蓝色。现从中随机取出n个球（不考虑取出来的球的次序），且要求红球和篮球一样多。那么，当n为偶数时，可能有多少种不同

5、的选取结果？ 分析问题 4分设红球选k个，则篮球必选k个，从而其它球应选n2k个，此时有种不同的选取结果（k0, 1, 2, , n/2）。 总的选取结果数为 4分 计算总的选取结果数为 2分二、 （10分）请利用二项式展开的方法求被13除所得的余数。 展开 3分 展开 3分 展开 3分 答：余数为3 1分三、 （10分）将n元面值为1元的人民币分给四名同学，且要求同学甲与乙分得的钱一样多，同学丙与丁一样多，同时还要求甲同学至少分得2元钱。问共有多少种不同的分法？ 分析问题，化为经典问题 2分相当于将n个相同的球放入4个不同的盒子，且甲盒与乙盒的球一样多，丙盒与丁盒的球一样多，同时甲盒至少放2

6、个球。 进一步转换为两个盒子的问题 2分相当于将n个相同的球放入2个大盒子A和B，每个盒子放偶数个球，且A盒至少放4个球。 写母函数 2分 求的系数 2分 答：分法总数为 2分四、 （10分）设集合S1, 1, 1, 2, 2, 2, 3, 3, 3, 3，试问由集合S的10个基本数字可构成多少个不同的四位数？ 【方法1】用母函数 分析问题，写相应的（指）母函数 4分 母函数展开 4分 答：共有79种分法 2分【方法2】直接算排列组合 集合的4排列有81种 4分 不符合要求的排列有“1111”和“2222”2个 4分 故构成的四位数有81279个 2分五、 （10分）由a、b、c、d、e五个基

7、本符号组成n位符号串，其中希望相邻的两个字母不能同时为a，请问满足条件的串共有多少个？ 设满足要求的串有个，分析问题 3分首字母不是a的串有4个；若首字母为a，则次字母一定不是a，这样的串有个 建立递推关系 3分 解得 3分 答：满足要求的串有个 1分六、 （10分）平面上有两两相交，但无3线共点的n条直线，试求这n条直线把平面分成多少个区域？ 设把平面划分为个区域，分析问题 3分第n条直线被原来的n1条直线分为n段，而每一段又把所在的区域一分为二，即增加一条直线，增加n个新的区域。 建立递推关系 3分 解得 4分七、 （10分）现有t种不同颜色的球，其中第i种颜色的球有个（i1, 2, ,

8、t）。要把这些球放入m个不同的盒子中，且使每个盒子至少放入一个球，问共有多少种不同的放法？ 分析问题，设全集S和子集（i1,2, , n） 3分设每个盒子不要求至少一个球的全部分配方案组成集合S，其中第i个盒子为空的所有分配方案构成集合（i=1, 2, , m）。其次，将个相同的球放入m个不同的盒子的方案数为（即可重复组合数） 计算 4分， （k=1, 2, , m） 由逐步淘汰原理计算结果 3分八、 （10分）某班每天放学后都要打扫卫生，其项目有扫地、整理桌椅、擦窗子和擦黑板共4项工作，故每天留下4名同学打扫卫生，每人恰好完成其中的一项。而今天留下的4名同学中，甲愿意整理桌椅或擦窗子，乙则不

9、愿意擦窗子，丙不愿意整理桌椅，丁同学对每一项工作都不挑剔。那么，能给出多少种安排打扫卫生的方案，使得每个同学都不用干自己不愿意干的工作？ 方法I 分析问题，对应为如下的棋盘布局问题 3分 求禁区A的棋盘多项式 2分或分离为2个小棋盘， 套公式： 3分 答案：4!4×3!5×2!2×1!0×0!8 2分九、 （10分）设n是大于1的奇数，证明在，中必有一个数能被n整除。 构造n个正整数 4分 令，则由n为奇数知令，即（i=1,2,n） 6分 由抽屉原理知必有2个相等，设且j<k 6分 由此知n整除 6分 但n为奇数，故n不能整除，从而n必整除（1kjn1） 6分另法：张国良，刘晓东十、 （10分）桌子上放着一些大小一样的等边三角形木框，且每个木框的每条边都被染成了彩色。经统计，所用的颜色共有10种。那么，如果按照木框的边的颜色异同对其进行分类，请问这些木框最多