母函数在组合计数问题方面的应用.doc

母函数在组合计数问题方面的应用摘 要法国数学家最早在概率的分析理论中明确提出母函数，母函数的理论由此基本建立，成为组合数学中尤其是计数方面的一个重要理论和工具。有些组合计数问题在深刻理解定义以及灵活运用加法乘法法则的基础上就能够解决，但是有些问题这些方法就显得无能为力了，母函数法作为一种既简单又适用的方法，这时就体现出了它的强大性。本文先用实例引出相关概念，讨论了母函数的一些性质，并结合实例说明了母函数在组合恒等式、求解递推关系、以及求解特殊要求的分配问题中的应用，本文还介绍了母函数形式的定理在染色问题和图的计数问题上的应用，最后对母函数进行了拓展，介绍了一些简单应用。关键词：组合计数；母函数；重集；整数拆分；广义母函数The application of generating function to combinatorics enumerativeAbstractFrench mathematician first clearly put forward generating function in the "probability theory", thereby the theory of generating function set up, a combination of mathematics, in particular, an important theory in mathematics and tools .Some combination of problems with the definition of addition and multiplication rule can solve, but some of the problems of these methods becomes powerless, and the generating function as a simple and applicable method, then an expression of the power of its. This leads to the first instance of the concepts used to discuss some properties of generating functions, and illustrated with an example of the generating function in combinatorial identities, solving recurrence relations, and special requirements for solving the allocation of application, the paper also describes the form of generating function theorem in graph coloring problem and the application of the counting problem, and finally the expansion of the generating functions, introduces some simple applications, and the prospect of a simple narrative.Keywords: combinatorial enumeration；generating function；re-set；integers split；generalized generating function 目 录 论文总页数：14页1、引言11.1、课题背景11.2、组合数学国内外研究现状11.3、课题研究意义11.4、课题研究方法12、相关概念22.1、母函数引例22.2、母函数定义23、母函数的性质34、母函数在组合计数中的几种应用34.1、母函数在证明组合恒等式中的应用34.2、母函数在求解递推关系中的应用44.3、母函数在特殊要求的分配问题中的应用54.4、母函数在整数拆分中的应用64.5、母函数形式的定理的应用74.5.1、定理的给出74.5.2、母函数形式的定理在染色问题上的应用84.5.3母函数形式的定理在图的计数的应用85、母函数的推广及简单应用9结 论10补充说明10参考文献10致 谢11声 明12附 录131、引言1.1、课题背景公元1666年，数学家莱布尼茨首次提出 “组合学”一词，并预言了这一数学分支的诞生。组合数学所研究的对象是离散构形问题,主要包括存在性问题、构造性问题，计数问题以及最优化问题。20世纪电子计算机的出现为组合数学的发展提供了广阔的舞台，组合计数理论作为组合数学的主要研究方向之一，在这个契机之下也得到迅猛发展。为了研究组合计数理论，人们提出各种方法：从最初的两个“计数法则”，到后来出现的各种排列组合算法。当然，在研究组合计数的时候，还有一种很重要的方法，那就是用母函数的方法。母函数是解决排列组合计数问题的重要工具,在组合问题中的应用既灵活又具有一定的广泛性,在不同的领域应用时都显出它独特的便捷与巧妙. 当今，许多人都在用母函数去研究组合计数，并且取得很好的结果，进一步推进了计算机的发展。1.2、组合数学国内外研究现状欧洲在积极发展组合数学，英国、法国、德国、荷兰、丹麦、奥地利、瑞典、意大利、西班牙等国家都建立了各种形式的组合数学研究中心。近几年，南美国家也在积极推动组合数学的研究。澳大利亚，新西兰也组建了很强的组合数学研究机构。值得一提的是亚洲的发达国家也十分重视组合数学的研究。1.3、课题研究意义组合数学在国外早已成为十分重要的学科，甚至可以说是计算机科学的基础。今后的计算机要向更加智能化的方向发展，其出路仍然是数学的算法，和数学的机械化。另外的一个有说服力的现象是，组合数学家总是可以在大学的计算机系或者在计算机公司找到很好的工作，一个优秀的组合数学家自然就是一个优秀的计算机科学家。组合数学不仅在软件技术中有重要的应用价值，在企业管理，交通规划，战争指挥，金融分析等领域都有重要的应用。当代信息科学快速发展，也促使我们研究组合数学，母函数做为组合数学中的一种重要工具越来越受欢迎，也是很有研究必要，可以说没有组合数学就没有计算机科学，没有计算机软件。1.4、课题研究方法1、由具体的例子给出母函数的定义及母函数所涉及到的相关概念。2、给出母函数的若干性质并简要分析，有性质得出一些结论，然后具体应用。2、相关概念2.1、母函数引例 引例：由此可见项的系数：；项的系数：；项的系数：。项的系数包含了从个元素中取出一个的组合全体，即；项的系数包含了从个元素中取出两个的组合全体，即；。令则，。所以，显然令得，这是组合数学中常见的一个等式。由此我们还可以推出其它的等式。2.2、母函数定义可见形如的式子在研究序列时很有价值，它对其它序列同样有用，由此，给出母函数的定义：定义2.1 对于序列构造一函数称为序列的母函数。例如函数就是序列的母函数。我们把定义2.1的母函数叫做普通型母函数，还有指数型母函数，定义如下定义2.2 对于序列构造一函数称为序列的指数型母函数。3、母函数的性质假设序列 母函数为，序列母函数为。性质1、若，则；性质2、若，则；性质3、若，则；性质4、若，则，其中；性质5、若，则。当然还有其它的一些性质，以上性质的证明都比较简单，现只对性质4做简单的证明，其它的见附录：证明：由以上性质我们推出一些常用的序列的母函数1、 2、4、母函数在组合计数中的几种应用4.1、母函数在证明组合恒等式中的应用组合恒等式的证明有时十分的困难，当我们合理的利用母函数，问题将会化繁为简。例1、若是任意的非负整数，证证明：由于 是1，1，1，的母函数，即，因为：，所以 (1)另一方面： (2)比较（1）、（2）的系数得：。4.2、母函数在求解递推关系中的应用例2、本月有雌雄小兔子一对，假定过两月后便可每月繁殖雌雄各一的一对小兔子。假设兔子都不会死，问过了n个月后共有多少对兔子？解：为第个月的兔子数，由题目很容易得到下面子式： 设，则所以：算得，令，得所以。4.3、母函数在特殊要求的分配问题中的应用例3、证明从个不同物体中允许重复的选取个物体的方式数为证明：该问题等价于证明重集的r组合数为，设表示从个物体中允许重复选取个物体的方式数，序列的母函数为：所以。该题中x的指数表示取一个物体重复的次数。例4、个有标志的球放入个有区别的盒子，无一空盒，问有多少种不同方案？解：该题相当于将个有标志的字符取个作允许重复的的排列，其排列数为，序列的指数型母函数为：所以例5、由这4个符号取5个进行排列，要求出现的次数不超2次，但不能不出现；出现的次数不超过1次，出现的次数不超过3次，可以不出现，出现的次数为偶数。求满足上述条件排列的个数。解： 设满足上述条件的排列的个数为个，序列 的指数型母函数为： 故所求排列的个数为2154.4、母函数在整数拆分中的应用定义4.1、将正整数n分解为若干个正整数的和，不考虑其求和的顺序，称作整数的拆分。例6、有1克、2克、3克、4克、5克的砝码各一枚，问能称出多少重量，并各有几种称法？解：利用母函数法计算：式子中x的指数表示可以称出的重量，前面的系数表示方案数，由此可见可以称出1到15克的重量，大于15克就不能称出。例7、 若有1克的砝码3枚，2克的4枚，4克的2枚。问能称出哪些重量？各有几种方案？解：利用母函数法计算：式子中x的指数表示可以称出的重量，前面的系数表示方案数，由此可见可以称出1到19克的重量，大于19克就不能称出。4.5、母函数形式的定理的应用4.5.1、定理的给出设是个对象上的置换群，用种颜色对这个对象着色，若在的作用下，对个元素的一种着色可转变成另一种着色，则认为这两种着色是同格式的。其不同的格式，对着色问题而言，即是不同的着色放案数：，其中表示置换分解成不相交轮换的积中轮换的个数。这就是定理。定理主要用于计数，当把它推广到母函数形式时，还可对状态进行例举，例如用两种颜色（用和来表示）来对两个球（和）染色，则所有可能的颜色组态为，展开式中各项表示着色方案，系数表示该着色方案的数目。把这种方法推广，可以推导出母函数形式的定理。母函数形式的定理：设是个对象上的置换群，用种颜色对这个对象着色，对于置换的长轮换，其中的各对象用同一颜色染次，故不同的着色方案数为，式中用代替得：，其中，表示置换中不变元的个数4.5.2、母函数形式的定理在染色问题上的应用例8、在一个有7匹木马的旋转木马上着色，求使成为三蓝、两红、两黄的方案数？解：先给出置换群的元素， 。我们可以看出格式有6个，有一个。所以方案数为：，展开式中的系数为30，所以给木马着成三蓝、两红、两黄的方案的方案数为304.5.3母函数形式的定理在图的计数的应用个顶点的简单图的个数，相当于个顶点的完全图的边，用两种颜色（和）着色，着色的边不要。由此我们可以用母函数形式的定理来对图进行计数。例9、三个顶点的有向图（如图）中，有两条边的图有多少个？e6e5e4e3e2e1123解： 给出置换群的元素，在的作用下，边的变化为：所以格式有1个，有3个，有两个，根据母函数形式的定理有：由上式的展开式可知的系数为：，三个顶点的有向图中，有两条边的图有4种。5、母函数的推广及简单应用定义5.1、称遵循一定的数量关系，形如，由变量的幂与二项式的乘积序列和组成的函数为广义母函数。例10、证明恒等式：证明：令母函数比较以上等式两端系数，很容易得到：。例11、证明恒等式证明：等式右端表示从个元素中取个，而左端表示从个中取个，所缺少的个由表示。所以：比较等式两端的展开项的系数显然成立。结 论 母函数作为组合数学中一种重要的工具，当许多传统的方法不能解决问题时，母函数法往往能够取得事半功倍的效果，从本文可以看出，母函数的应用十分广泛，在解决相关问题的时候，用母函数是很方便的。补充说明 母函数在递推关系的求解时只以数列为例，对于非齐次的情形没有进行说明。参考文献1 卢开澄,卢华明.组合数学M. 北京：清华大学出版社,2006.42-76,167-200. 2 孙世新.组合原理及其应用M.国防工业出版社,2006.3 李凡长.组合理论及其应用M. 北京： 清华大学出版社,2006.4 布鲁迪（Richard A.Brualdi）美著.组合数学M.冯舜玺等译.北京：机械工业出版社，2005.5 钟五一.广义母函数的设立及其应用J.广东教育学报.2006,6第26卷第3期 26-28 6 肖启明.利用母函数法证明组合恒等式J.宜春学院学报(自然科学) 2007,4 第29卷第2期 37-39 7 田秋成.组合数学M. 北京：电子工业出版社,2006,11.10-60.8 林翠琴.组合学与图论M. 北京：清华大学出版社,2009,4.9 石生明.近世代数初步M.高等教育出版社,2002,7.10-60.致 谢本论文的工作是 2010年4月至2009年6月在成都信息工程学院数学学院完成的。文中除了特别加以标注地方外，不包含他人已经发表或撰写过的研究成果，也不包含为获得成都信息工程学院或其他教学机构的学位或证书而使用过的材料。除非另有说明，本文的工作是原始性工作。本文是在杨英老师的热情关心和指导下完成的，她渊博的知识和严谨的治学作风使我受益匪浅，对顺利完成本课题起到了极大的作用。在此向他表示我最衷心的感谢！最后向在百忙之中评审本文的各位专家、老师表示衷心的感谢！作者简介：姓 名： 性别：男出生年月：1986.11 民族：汉E-mail：695569269声 明关于学位论文使用权和研究成果知识产权的说明：本人完全了解成都信息工程学院有关保管使用学位论文的规定，其中包括：（1）学校有权保管并向有关部门递交学位论文的原件与复印件。（2）学校可以采用影印、缩印或其他复制方式保存学位论文。（3）学校可以学术交流为目的复制、赠送和交换学位论文。（4）学校可允许学位论文被查阅或借阅。（5）学校可以公布学位论文的全部或部分内容（保密学位论文在解密后遵守此规定）。除非另有科研合同和其他法律文书的制约，本论文的科研成果属于成都信息工程学院。特此声明！作者签名： 2010年5月27日附 录1、母函数性质的证明：性质1：证明：性质2：证明：性质3：证明： 性质5：证明：得证。2、母函数形式的定理需要的相关代数学知识群：给定集合和集合上的二元运算，并且满足以下四个条件： （1）封闭性。 （2）结合律。 （3）存在单位元。中存在一元，对于中任何元，满足。 （4）存在逆元。中任何元，都有中的一元，满足。置换：集合上的双射函数称为集合上的一个置换。置换群：设集合是由一个集合的置换所组成的集合，如果在置换的乘法下构成一个群，则称是的一个置换群。轮换：一个轮换是列在圆括号中的一排数，这些数用逗号隔开，轮换表示把1送给2,2送给3,3送给1等价类：对于给定的关于的置换群，若存在置换使变为，则存在使变为，。单位元素使变为。若存在使变为，又存在使变为，则存在置换使变为，。即则 由，可知，作用在上形成一个封闭的类。故中的数，若存在置换使之变成，则称和属于同一个等价类。因而到的整数可按群的置换分成若干个等价类，数所属的等价类记以。也可以看作是在作用下的“轨迹”。