《组合数学期末结业作业》由会员分享，可在线阅读，更多相关《组合数学期末结业作业（11页珍藏版）》请在金锄头文库上搜索。
1、 理学院 组合数学课程设计 学号：2011113127 专业：信息与计算科学 姓名：易继荣 主讲教师：杨丽宏 2013 年 12 月 哈尔滨工程大学理学院信息与计算科学专业易继荣整理（EDITED By JIRONG YI） 2 一、问题的提出 1. 要从 7 名女子和 4 名男子的集合中选出 k 个人组建一个委员会。对于下面各情况，有多 少种方法组建这个委员会？ (a) 该委员会是由 3 名女子和 2 名男子组成的； (b) 该委员会的人数不限，但男女人数必须相等，且至少各有一人； (c) 该委员会有 4 人，而且其中之一必须是赵先生； (d) 该委员会有 4 人，而且至少有两名女子； (e
2、) 该委员会有 4 人，男女各有两人，赵先生夫妇不能同时在这个委员会中。 2. 利用组合意义证明： ( )( ) + ( 1)( 1 1 ) + ( 2)( 2 n 2 ) + + ( n)( 0 ) = 2( n) 3. 构造 8 阶幻方。 4. 10 个数字（0 到 9）和 4 个 四则运算符（，）组成的 14 个元素。求由其中 的 n 个元素的排列构成的算术表达式的个数。 5. 投掷一次色子，出现点数 1,2，3，4，5，6 的概率是 1/6.问连续投掷 10 次，出现点数之 和为 30 的概率是多少？ 6. 一个抽屉里有 20 件衬衫，其中 4 件是蓝色的，7 件是灰色的，9 件是红色
3、的。问应从中 随意取多少件能保证有 4 件是同色的。又应取多少件保证为 5,6,7,8,9 件是同颜色的？ 7. 证明，能够由数 1,2，2n 构造满足 11 12 1 21 22 2 1=2) 例如：h(2)=h(0)*h(1)+h(1)*h(0)=1*1+1*1=2 h(3)=h(0)*h(2)+h(1)*h(1)+h(2)*h(0)=1*2+1*1+2*1=5 另类递推式 2： h(n)=h(n-1)*(4*n-2)/(n+1); 递推关系的解为： h(n)=C(2n,n)/(n+1) (n=0,1,2,.) 递推关系的另类解为： h(n)=c(2n,n)-c(2n,n+1)(n=0,1
4、,2,.) 依据题意，不妨按照所给条件选出 n 个数排在第一行，剩余的数自然排在第二行。现用 1,0 表示第一行的数，用2表示第二行的数，再将这 2n 个数按照从小到大的顺序排 列成一行， 那么对于第二行中某个数2而言必然有其同列的1在其左边或上边， 即将这 2n 个数按照从小到大排列之后，对于第二行中任意元素2前的原排列中位于弟一行的数的个 数大于第二行的数的个数。现用 0 表示弟一行的数，1 表示第二行的数，那么这 2n 个数的 排列数可以化为 n 个 0 和 n 个 1 排成一行，对于每个 1 之前 0 的个数大于 1 的个数的排列 数，自然我们可以得到其排列数为(2 ) ( 2 n +
5、 1) 哈尔滨工程大学理学院信息与计算科学专业易继荣整理（EDITED By JIRONG YI） 8 8. 事实上主要而又核心的方法分别有两大计数原理、生成函数方法、递推关系方法、容斥 原理， 其余的方法都是在此四大方法上发展而来， 故而只需将此四大方法介绍清楚并分别举 例即可解决。 三、问题的求解 1 由题意知 (a).当k=5时， 我们对于男的选取有(4 2)， 对于女的选取有( 7 3)， 故而总的选择有N=( 4 2)( 7 3)=210. (b).此时 k 满足k *2,4,6,8+,同时男女的数目为相同的，从而得到总的选择有 N = (7 i )(4 i) = 329 4 =1
6、(c).此时 k=4，男的选取数只能是 14，即总的选择为 N = ( 7 3 i)( 3 i ) = 120 3 =0 (d).此时 k=4，我们不妨先考虑其对立面即女子最多为两名，再用总的选择数减去即可得到 合乎要求的选择为 N = (11 4 ) (7 i )( 4 4 i)302 1 =0 (e).此时 k=4，我们不妨先考虑该对夫妇均入选的选择数，再用总的可选择数减去其即可得 到合乎要求的选择为 N = (7 2)( 4 2) ( 6 1)( 3 1) = 108 2. 参见分析部分。 3. 根据分析得到的幻方如下 哈尔滨工程大学理学院信息与计算科学专业易继荣整理（EDITED By
7、 JIRONG YI） 9 16 2 3 13 64 50 51 61 5 11 10 8 53 59 58 56 57 55 54 60 9 7 6 12 52 62 63 49 4 14 15 1 48 34 35 45 32 18 19 29 37 43 42 40 21 27 26 24 25 23 22 28 41 39 38 44 20 30 31 17 36 46 47 33 4. 见分析部分,知答案为 = 1 465 *(15 + 65)(5 + 65) (15 65)(5 65) + 5. 根据分析知道 1 610 (20 + 10 1 20 )即为所求概率。 6. 根据分析
8、并且结合鸽巢原理知道，为了保证分别有 4、5、6、7、8、9 件衣服同色，必 须要选取的衣服的件数分别为 10、13、15、17、19、20 件。 7. 参见分析部分。 8. 方法一、两大计数原理 分类计数原理：完成一件事有几类办法，各类办法相互独立，每类办法中又有 多种不同的办法，则完成这件事的不同办法数是各类不同方法种数的和。 例如： 哈尔滨工程大学理学院信息与计算科学专业易继荣整理（EDITED By JIRONG YI） 10 对于 i 个集合， 集合 j 中元素为个， 现在要选 n( ,对于一切的均成立)个 并且在同一集合中的元素，那么此时有 () = ( ) 0 =1 分步计数原理
9、：完成一件事，需要分成几个步骤，每一步的完成有多种不同的 方法，则完成这件事的不同方法种数是各种不同的方法数的乘积。 例如： 对于 i 个集合，集合 j 中元素为个，现在要在每个集合中选 n( ,对于一切的均成立)个元素，那么此时有 () = ( ) 0 =1 方法二、生成函数法 生成函数的应用简单来说在于研究未知（通项）数列规律，用这种方法在给出递推式的 情况下求出数列的通项，生成函数是推导 Fibonacci 数列的通项公式方法之一，另外组合数 学中的 Catalan 数也可以通过生成函数的方法得到。在此我们仅考虑普通的生成函数。 其定义为对于任意数列 a0,a1,a2.an 即用如下方法
10、与一个函数联系起来： G(x) = a0 + a1x + a2x2 + a3x3 +.+ anxn. 则称 G(x)是数列的生成函数(generating function)。 例如：将 n 个苹果分到 10 个箱子里面，每个箱子不能为空，此时我们有 g() = (1+ 2+ 3+ 4+ 5+ 6+ )10 其中的的系数为方法数即为 () = ( 10 + 10 1 10 ) 方法三、递推关系法 其定义为设(0,1,2,)是一个序列， 把序列中德任意一项与其前的任意多 项连接起来的方称叫做一个递推关系。 例如：带有 n 个环的汉诺塔问题中方法数 d 的递推关系为 () = = 21+ 1 方法
11、四、容斥原理 其基本内容为 也可表示为 设 S 为有限集, 哈尔滨工程大学理学院信息与计算科学专业易继荣整理（EDITED By JIRONG YI） 11 则 两个集合的容斥关系公式：AB = A+B - AB (：重合的部分） 三个集合的容斥关系公式：ABC = A+B+C - AB - BC - CA +ABC 例如：现在有 n 个集合，对应集合的元素数为,求出其并集中的元素数，此时 对应为 () = (1 2 3 4 ) = + 四、问题的反思 上述问题都属于常规类问题，只需要把握好以下几点 （1） 问题求解的两大切入点：正面入手或者对立面入手。 （2） 问题求解的四大方法：两大计数原理、生成函数、递推关系、容斥原理 （3） 问题证明的两大思路：直接从题目本身出发，进行纯数学的推导或者借助实际模型 进行理解再进行证明。 （4） 鸽巢原理问题的求解关键在于构建出鸽子与巢，同时如何把问题分析过程用适当的 形式表达出来也是很重要的。
