2010组合数学复习题

2010-2011学年《组合数学》复习题一、填空题1、将2n个人分成n组，每组两个人，共有种不同的分组方法；2、从1至100的整数中不重复地选取两个数组成有序对(x，y)，使得x与y的乘积xy不能被3整除，共可组成对有序对；3、整除88200的正整数有个；4、整除510510的正奇数有个；5、有个能被3整除而又不含数字6的三位数；6、一个抽屉里有20件衬衫，其中4件是蓝的，7件是灰的，9件是红的，则应从中随意取件才能保证有4件是同颜色的；7、由2个0、3个1和3个2作成的八位数共有个；8、万位数字不是5，个位数字不是2且各位数字相异的五位数共有个；9、在m×n棋盘中选取两个相邻的方格(即有一条公共边的两个方格),共有个；10、1）从1至1000的整数中，有个整数能被5整除但不能被6整除。2）从1至1000的整数中能被14或21整除的整数个数为；11、外事部门计划安排8位外宾参观4所中学和4所小学，每人参观一所学校，但外宾甲和乙要求参观中学，外宾丙要求参观小学，共有种不同的安排方案。12、错误!未找到引用源。展开式中错误!未找到引用源。的系数是。13、由n个相异元素错误!未找到引用源。,错误!未找到引用源。,错误!未找到引用源。作成的错误!未找到引用源。与错误!未找到引用源。错误!未找到引用源。,之间有且只有一个元素的全排列数为。14、10个节目中有6个演唱、4个舞蹈。今编写节目单，要求任意两个舞蹈之间至少有1个演唱，问可编写出种不同的演出节目单。15、由3只绿球、2只红球、2只白球和3只黄球作成的没有2只黄球相邻的全排列数是。16、方程1544321xxxx的非负整数解的个数是。17、一张币值为二角的人民币兑换为一分、二分或五分的硬币，有种兑换方法。18、⑴小于10000的含数字1的正整数共有个；⑵小于10000的含数字0的正整数共有个；19、6位男宾，5位女宾围坐一圆桌，则1）女宾不相邻的就坐方案有种；2）所有女宾坐在一起的方案有种；3）某一女宾A和两位男宾相邻而坐的方案有种；20、已知01221nnnaaa，)2(,26,310naa，则na=；二、计算题1、确定由数集{2,4,6,8}所形成的全部互异整数的总和。2、由数集{0,1,2…9}中的数可以构造出多少个不同的四位偶数？3、学校有100名学生和3个宿舍A,B和C，它们分别能容纳25，35和40人。1)为学生安排宿舍有多少种方法？2)设100名学生中有50名男生和50名女生，而宿舍A是全男生宿舍，宿舍B是全女生宿舍，宿舍C男女生兼收。有多少种方法可为学生安排宿舍？4、15个人围坐一桌，如果B拒绝挨着A坐，有多少种围坐方式？如果B只拒绝坐在A的右侧，又有多少种围坐方式？5、从1到300间任取3个不同的数，使得这3个数之和正好被3整除，试问有多少种不同方案？6、求5位数中至少出现一个数字6，而且被3整除的数的个数。7、1)确定多重集S=}5,4,3{cba的11-排列个数;（或确定多重集}3,4,1{cbaM的6-排列的个数；）2)列出多重集S=}3,1,2{cba的所有3-组合和4-组合。3)确定多重集S=}5,4,3,4{dcba的12-组合的个数。8、⑴方程304321xxxx有多少满足条件：1x≥2,2x≥0,3x≥-5,and4x≥8的整数解？⑵方程184321xxxx有多少满足条件：1≤1x≤5,-2≤2x≤4,0≤3x≤5,3≤4x≤9的整数解？9、⑴求500,......3,2,1U中能被2，3和5整除的数的个数；⑵从1至2000的整数中，至少能被2，3，5中的两个数整除的整数有多少？10、⑴现有A,B,C和D四种材料分配于生产1，2，3和4四种产品。假设A不宜于产品1，B不宜于产品3和4，C不宜于产品1和3，D不宜于产品4。试问有多少分配方案，使得每种产品有一种其适宜的材料？⑵现有5间房，要安排5个人住宿，每人住一间房间，其中甲不住5号房间，乙不住4、5号房间，丙不住3号房间，丁不住2号房间，戊不住1、2号房间，请用棋盘多项式方法求解满足题设要求的住宿安排方法总数。11、现要安排6个人值夜班，从星期一至星期六每人值一晚，但甲不安排在星期一，乙不安排在星期二，丙不安排在星期三，共有多少种不同的安排值班的方法？12、由a,b,c,d,e这五个字符，从中取6个按字典顺序构成字符串，要求：⑴第1个和第6个字符必为辅音字符b,c,d；⑵每一字符串必有两个元音字符a或e，且两个元音字符不相邻；⑶相邻的两个字符必不相同。求字符串的总数目。13、求由{1，3，5，7}组成的不重复出现的整数的总和。14、⑴n个完全相同的球放到m（m≤n）个有标志的盒子，不允许空盒，问共有多少种不同的方案？⑵求1，3，5，7，9这5个数组成的n位数的个数，要求其中3和7出现的次数为偶数，其它数字出现的次数无限制。⑶如果要把棋盘上偶数个方格涂成红色，是确定用红色、白色和蓝色对1行n列棋盘的方格涂色的方法数。（解题要求：利用生成函数方法分析）15、一部由1楼上升到10楼的电梯内共有n个乘客，该电梯从5楼开始每层楼都停，以便让乘客决定是否离开电梯。（1）求n个乘客离开电梯的不同方法种数。（2）求每层楼都有人离开电梯的不同方法的种数。16、设有n(n≥3)个箱子A1,A2,…,An，每个箱子Ai（i=1，2，…，n）都安上一把锁，n把锁各不相同。今把n把锁的钥匙随意地放回这n个箱子中，每个箱子放一把钥匙。锁上全部箱子之后撬开A1和A2，然后取出A1和A2箱子内的钥匙去开别的箱子。如果能开出别的箱子，则把箱子内的钥匙拿出来再去开另外的箱子。如果最终能把箱子全部打开，则称这n把钥匙的放法是一种好放法。求n把钥匙的好放法的种数错误!未找到引用源。.三、论述题1、结合本学期学习《组合数学》课程心得体会和你的研究方向，谈谈组合计数理论与方法可如何在计算机应用或软件工程领域发挥作用。答：1、解决工业界中的试验设计问题；2、网络可靠性问题；3、栈排序问题；4、最短路径问题；本次课程的主要内容包括：鸽巢原理和Ramsey定理；组合数学基本计数法（排列与组合、生成排列和组合、二项式系数、特殊计数序列）、容斥原理及应用个人的心得：从开始学习数学的过程中，我们就在接触数学，在高中数学课本中我们就对数学归纳法有所了解，而组合数学主要的研究对象是离散数据，数学归纳法是学习组合数学的主要工具，对于如何学好组合数学在课堂的第二节课，老师已有所指，我很喜欢那句话，不过感觉好熟悉，“你解决的问题越多，能够解决下一个问题的可能性越大。”2、选择一个具体案例，结合案例分析组合计数理论与方法在计算机应用或软件工程领域的应用前景、应用特点和典型应用案例。答：组合数学与计算机软件随着计算机网络的发展，计算机的使用已经影响到了人们的工作，生活，学习，社会活动以及商业活动，而计算机的应用根本上是通过软件来实现的。我在美国听到过一种说法，将来一个国家的经济实力可以直接从软件产业反映出来。我国在软件上的落后，要说出根本的原因可能并不是很简单的事，除了技术和科学上的原因外，可能还跟我们的文化，管理水平，教育水平，思想素质等诸多因素有关。除去这些人文因素以外，一个最根本的原因就是我国的信息技术的数学基础十分薄弱，这个问题不解决，我们就难成为软件强国。然而问题决不是这么简单，信息技术的发展已经涉及到了很深的数学知识，而数学本身也已经发展到了很深、很广的程度并不是单凭几个聪明的头脑去想想就行了，而更重要的是需要集体的合作和力量，就象软件的开发需要多方面的人员的合作。美国的软件之所以能领先，其关键就在于在数学基础上他们有很强的实力，有很多杰出的人才。一般人可能会认为数学是一门纯粹的基础科学，1+1的解决可能不会有任何实际的意义。如果真是这样，一门纯粹学科的发展落后几年，甚至十年，关系也不大。然而中国的软件产业的发展已向数学基础提出了急切的需求：网络算法和分析，信息压缩，网络安全，编码技术，系统软件，并行算法，数学机械化和计算机推理，等等。此外，与实际应用有关的还有许多许多需要数学基础的算法，如运筹规划，金融工程，计算机辅助设计等。如果我们的软件产业还是把眼光一直盯在应用软件和第二次开发，那么我们在应用软件这个领域也会让国外的企业抢去很大的市场。如果我们现在在信息技术的数学基础上，大力支持和投入，那将是亡羊补牢，犹未为晚；只要我们能抢回信息技术的数学基地，那么我们还有可能在软件产业的竞争中，扭转局面，甚至反败为胜。吴文俊院士开创和领导的数学机械化研究，为中国在信息技术领域占领了一个重要的阵地，有了雄厚的数学基础，自然就有了软件开发的竞争力。这样的阵地多几个，我们的软件产业就会产生新的局面。值得注意的是，印度有很好的统计和组合数学基础，这可能也是印度的软件产业近几年有很大发展的原因。计算机之所以可以被称为电脑，就是因为计算机被人编写了程序，而程序就是算法，在绝大多数情况下，计算机的算法是针对离散的对象，而不是在作数值计算。正是因为有了组合算法才使人感到，计算机好象是有思维的。应用问题：栈排序问题；最短路径问题；本次课程的主要内容包括：鸽巢原理和Ramsey定理；组合数学基本计数法（排列与组合、生成排列和组合、二项式系数、特殊计数序列）、容斥原理及应用心得体会：