组合数学

组合数学论文现代数学可以分为两大类：一类是研究连续对象的，如分析、方程等，另一类就是研究离散对象的组合数学。组合数学不仅在基础数学研究中具有极其重要的地位，在其它的学科中也有重要的应用，如计算机科学、编码和密码学、物理、化学、生物等学科中均有重要应用。微积分和近代数学的发展为近代的工业革命奠定了基础。而组合数学的发展则是奠定了本世纪的计算机革命的基础。计算机之所以可以被称为电脑，就是因为计算机被人编写了程序，而程序就是算法，在绝大多数情况下，计算机的算法是针对离散的对象，而不是在作数值计算。正是因为有了组合算法才使人感到，计算机好像是有思维的。组合数学不仅在软件技术中有重要的应用价值，在企业管理，交通规划，战争指挥，金融分析等领域都有重要的应用。在美国有一家用组合数学命名的公司，他们用组合数学的方法来提高企业管理的效益，这家公司办得非常成功。此外，试验设计也是具有很大应用价值的学科，它的数学原理就是组合设计。用组合设计的方法解决工业界中的试验设计问题，在美国已有专门的公司开发这方面的软件。广义的组合数学就是离散数学，离散数学是狭义的组合数学和图论、代数结构、数理逻辑等的总称。但这只是不同学者在叫法上的区别。总之，组合数学是一门研究离散对象的科学。随着计算机科学的日益发展，组合数学的重要性也日渐凸显，因为计算机科学的核心内容是使用算法处理离散数据。狭义的组合数学主要研究满足一定条件的组态（也称组合模型）的存在、计数以及构造等方面的问题。组合数学的主要内容有组合计数、组合设计、组合矩阵、组合优化等。组合数学中有几个著名的问题：地图着色问题：对世界地图着色，每一个国家使用一种颜色。如果要求相邻国家的颜色相异，是否总共只需四种颜色？这是图论的问题。船夫过河问题：船夫要把一匹狼、一只羊和一棵白菜运过河。只要船夫不在场，羊就会吃白菜、狼就会吃羊。船夫的船每次只能运送一种东西。怎样把所有东西都运过河？这是线性规划的问题。中国邮差问题：由中国组合数学家管梅谷教授提出。邮递员要穿过城市的每一条路至少一次，怎样行走走过的路程最短？这不是一个NP完全问题，存在多项式复杂度算法：先求出度为奇数的点，用匹配算法算出这些点间的连接方式，然后再用欧拉路径算法求解。这也是图论的问题。货郎问题：一个货郎要去若干城镇卖货，然后会到出发地，给定各个城镇之间的旅行时间，应怎么样计划他的路线，使他可以去每个城镇而且所用的时间最短。这个问题至今都没有有效的算法。这几个问题将组合数学研究的问题具体表现出来，同时也可以看出他在我们生活中有着很重要的地位。组合数学中主要可以分成以下几个部分：排列组合与容斥原理、二项式定理、递推关系与生成函数、polya定理。下面我将以这四个部分分别介绍组合数学的各方面问题。1、排列组合与容斥原理：排列组合里面的4个重要的基本原理：加法原理、乘法原理、减法原理、除法原理前面两个最为基本，后面两个是根据前两个派生出来的。乘法原理有的时候的应用很巧妙，可以作为一种打开思路的办法。基本的排列组合之后，接下来引出了多重集。多重集的排列组合是一个很经典的问题，总结如下：多重集的排列：全排列的话只需应用除法原理就可以了。n个元素的多重集的r排列需要利用指数生成函数来做。多重集的组合：n个元素的多重集的r组合，如果r小于等于任何一个元素可选的个数，那么就归结为经典的不定方程的解数问题，可以利用“隔板法”来做。结果就是一个组合数。如果r大于某些元素的可选个数，那么一种方法是利用容斥原理，一种方法还是要依靠生成函数（编程序的时候可以用动归做）。如果是一个环形的排列组合，那么问题就困难许多，要利用置换群和polya定理。单纯的依靠四项基本原理来计数，有的时候会显得力不从心，这个时候就需要容斥原理的帮助。容斥原理特别适合解决若干限制条件的交、并问题，也是打开思路的一种方法。利用容斥原理解决的经典问题有：错排问题，带禁止位置的排列。禁位排列总觉得用容斥原理解决的不够优美，不知道有没有可以编程的数学方法。跟排列组合相关的还有就是生成排列和组合。生成排列利用那个什么字典序法好像足够了，编程好实现。生成组合方法类似。计算不具有某几个属性物体个数：公式：=|S|-∑R-1+∑R-2-∑R-3...+(-1)^mR-m---------一种情况的化简情况：各R-i组合个数相同(k个i组合计数相同)=a0-C(m,1)a1+C(m,2)a2-C(m,3)a3+...+(-1)^kC(m,k)ak+...+(-1)^mam计算至少具有某几个属性之一的物体个数公式：=∑R-1-∑R-2+∑R-3...+(-1)^(m+1)R-m情况：n个不同元素，k种，非无限，没种限制为r1...rk。在n种元素中取r组合。解决方法：按无限多重组合运算共C(n+k-1)种按1组合到k组合计算每种组合的补集的无限多重组合计数(1组合|A1|,|A2|,2组合|A1&A2|...)其中|Ai|=C(r-ri-1+k-1,r-ri+i)(备注：r-ri-1为先取ai达到ri+1个后，进行无限多重组合计数的总位数)公式：按容斥原理=[C(n+k-1)-1组合+2组合+。。。+(-1)^kk组合计数]错位排列问题：记Ai表示数字i恰好排在第i个位置的排列集合，|Ai|=card(Ai)表示集合中元素个数；€Ai表示Ai的余集（补集）现在求的是∩€Ai，即任意i都不会出现在第i个位置的排列集合；根据容斥原理得|∩€Ai|=|€∪Ai|=n!-|∪Ai|而|∪Ai|=∑C(n,k)(-1)^(k+1)(n-k)!（这里k从1到n）从而|∩€Ai|=n!-|∪Ai|=n!+∑(-1)^k*C(n,k)(n-k)!发现k=0恰好(-1)^k*C(n,k)(n-k)!=n!所以结果可以改写为∑(-1)^k*C(n,k)(n-k)!（这里k从0到n）C(n,k)(n-k)!的意义表示其中指定某k个数字排在它对应的位置，其他的n-k个数字可以任意排列的个数为(n-k)!个，而指定k个可以有C(n,k)种指定方式。2、组合数学中的二项式定理有很多公式，用的时候可以现查。终于知道了三角形数原来跟排列组合有关，而且是一个很简洁的公式。很多公式的推导用的思想很妙。有一个很好的思想就是把(1+x)^n利用二项式定理展开，然后求导、求积分，居然可以导出很多的公式。还有一个很重要的定理就是pascal定理，pascal递推式很有用（展开后有两种形式，一种是上下限均不定，一种是下限不定），可以解决很多组合数的求和问题。另外一个重要的定理就是牛顿二项式定理，在生成函数中应用广泛，可就是推导起来有点繁。抽屉原理：桌上有十个苹果，要把这十个苹果放到九个抽屉里，无论怎样放，我们会发现至少会有一个抽屉里面放两个苹果。这一现象就是我们所说的“抽屉原理”。抽屉原理的一般含义为：“如果每个抽屉代表一个集合，每一个苹果就可以代表一个元素，假如有n＋1或多于n＋1个元素放到n个集合中去，其中必定至少有一个集合里有两个元素。”抽屉原理有时也被称为鸽巢原理（“如果有五个鸽子笼，养鸽人养了6只鸽子，那么当鸽子飞回笼中后，至少有一个笼子中装有2只鸽子”）。它是组合数学中一个重要的原理。原理1：把多于n个的物体放到n个抽屉里，则至少有一个抽屉里的东西不少于两件；[证明]（反证法）：如果每个抽屉至多只能放进一个物体，那么物体的总数至多是n，而不是题设的n+k(k≥1)，这不可能.原理2把多于mn(m乘以n)个的物体放到n个抽屉里，则至少有一个抽屉里有不少于m+1的物体。[证明]（反证法）：若每个抽屉至多放进m个物体,那么n个抽屉至多放进mn个物体,与题设不符，故不可能原理3把无穷多件物体放入n个抽屉，则至少有一个抽屉里有无穷个物体。.原理123都是第一抽屉原理的表述原理2：把（mn－1）个物体放入n个抽屉中，其中必有一个抽屉中至多有（mn—1）个物体。[证明]（反证法）：若每个抽屉都有不少于m个物体，则总共至少有mn个物体，与题设矛盾，故不可能3、递推关系与生成函数：许多组合数学计数问题依赖于一个整数参数n，这个整数参数n常常表示问题中某个基本集（笛卡尔集）或多重集的大小、组合的大小、排列中的位置数等等。因此一个计数问题常常不是一个孤立的问题，而是一系列单个问题的综合。本章中，我们将讨论涉及一个整数参数的某些计数问题的代数求解方法。这些方法类似于上一章所介绍的棋盘多项式方法一样，通过引入一个函数（称为生成函数，它实质上是一个幂级数，其各项系数对应于相应计数问题的解）结合递推关系来求解相应的计数问题。求解线性递推关系的特征方程的方法还是有一定价值的，但是编程不适用。n解线性齐次递推方程有矩阵解法。稍微复杂点的递推关系（非线性），特征方程就不够用了，必须祭出生成函数这个有力的武器。感觉生成函数实在是太优美、太强大了。生成函数的关键就是要把多项式拆分成(1-rx)^n这种形式，这样就可以利用牛顿二项式定理展开了。在特殊计数序列里面提到了盒装球问题。将p个不同的球放入k个相同的盒子（每个盒子非空）的方法数是第二类Stirling数S(p,k)；将p个相同的球放入k个相同的盒子（每个盒子非空）的方法数是分拆数，可以归结为整数划分问题，用动态规划求解；将p个不同的盒子放入不同的k个盒子并且每个非空的方法数为k!*S(p,k)。有几个很经典的递推关系：斐波那契数列、Catalan数（几种经典的形式：三角剖分数、二叉生成树个数、+1-1序列、加括号序列等等）、Stirling数（两种，第二种比较常用）、汉诺塔、n个圆切割平面数、n条直线k个交点切割平面数等等。此外，格路径中提到的平移、反射和一一对应这三种分析问题的方法也很值得借鉴。例1.确定平面一般位置上的n个互相交叠的圆所形成的区域数。（互相交叠是指每两个圆相交在不同的两个点上；一般位置是指没有同心圆）例2.年初把性别相反的一对新生兔子放进围栏，从第二个月开始每月生出一对性别相反的兔子，每对新兔也从第二个月开始每月生出一对性别相反的兔子，问一年后围栏内共有多少对兔子。定义1：设f0=0,f1=1,那么满足递推关系fn=fn-1+fn-2,的序列叫斐波那契（Fibonacci）序列。结论：Fibonacci序列的部分和为sn=f0+f1+…+fn=fn+2-1.沿Pascal三角形左边向上对角线上的二项式系数和是Fibonacci数,即fn=01n+12n+…+1kkn,其中:k=21n.定义1:令h0,h1,h2,…,hn,…是一个数列,若存在量a1,a2,…,ak和bn(ak≠0,每个量是常数或依赖于n的数)使得:hn=a1hn-1+a2hn-2+…+akhn-k+bn(n≥k)则称序列满足k阶线性递推关系.若bn=0,称齐次的;若a1,a2,…,ak取常数,称常系数的.令q为一个非零数,则hn=qn是常系数线性齐次递推关系hn=a1hn-1+a2hn-2+…+akhn-k(ak≠0,n≥k)(1)的解,当且仅当q是多项式方程xk-a1xk-1-a2xk-2-…-ak=0(2)的一个根.若多项式方程有k个不同的根q1,q2,…,qk,则hn=c1q1n+c2q2n+…+ckqkn(3)是下述意义下(1)的一般解:无论给定h0,h1,…,hk-1什么初始值,都存在c1,c2,…,ck使得(3)式是满足(1)式和初始条件的唯一的序列.令q1,q2,…,qt为常系数线性齐次递推关系:hn=a1hn-1+a2hn-2+…+akhn-k(n≥k)的特征方程的互异的根,此时,如果qi是si的重根,则该递推关系对qi的部分一般解为:Hn(i)=c1qin+c2nqin+…+csinsi-1qin递推关系的一般解为:hn=Hn(1)+Hn(2)+…+Hn(t)递归和生成函数令h0,h1,h2,…,hn,…为满足k阶常系数线性齐次递推关系:hn=c1hn-1+c2hn-2+…+ckhn-k(ck≠0,n≥k)(1)的数列,则它的生成函数g(x)形如:g(x)=)()(x