组合数学中常见的计数方法

沈阳理工大学学士学位论文摘 要 组合数学是研究离散结构的存在、计数、分析和优化等问题的一门学科，它是计算机出现以后迅速发展起来的一门数学分支。近年来，组合数学不仅在软件技术中有着重要的应用价值，而且在企业管理，交通规划，战争指挥，金融分析等领域都有着重要的应用。组合数学在国外早已成为十分重要的学科，甚至可以说是计算机科学的基础。本文通过对几类常见组合数的整理归纳,主要介绍了Catalan数、第一类、第二类Stirling、Fine数、Plya计数等计数方法的历史起源、定义、基本性质等,研究组合数学及概率论有关知识，并根据组合计数和概率之间内在的联系，进而研究组合数学的组合意义在生活中某些领域的应用。组合数学所讨论的问题来源于实际。因此从内容来看确实丰富多彩,以至于很难用一句话来概括什么叫“组合数学”,本文只能就它所研究的若干问题进行介绍。关键词:组合数学;概率论;组合意义;应用 AbstractCombinatorial mathematics is a discipline contains the existence of discrete structures, counting, analysis and optimization, which is a branch of mathematics developed rapidly since the advent of the computer. In recent years, the combination of mathematics not only has important applications in software technology, but also has important applications in the field of business management, transportation planning, command of the war, and financial analysis. Combinatorial Mathematics in the countries has already become a very important subject, and can even be said to be the basis of computer science.This article summarized by the finishing of some common combinations of numbers, mainly Catalan numbers, the first category, the second Stirling Fine number, the Polya counting method, historical origins, definition, basic properties, research and combinatorial mathematics and probability of relevant knowledge, and according to the combination of count and an intrinsic link between the probability and then study a combination of mathematical meaning in some areas of the life.The issues discussed by the combination of mathematics from real and the content point of view is really colorful, so it is difficult to summarize in one sentence what is called Math, this paper can only be described a number of issues studies.Keywords: combinatorial mathematics; probability theory; combination of significance; application目 录1 绪论11.1组合数学的研究背景和意义11.2国内外研究现状12 Catalan数32.1 Catalan产生的历史32.2 Catalan数的定义52.3 关于Catalan数的几种求法62.3.1 引言62.3.2 组合模型及求法62.3.3 路径模型及求法72.3.4 生成函数法82.4 Catalan数的性质92.5 Catalan数的组合意义及应用102.5.1 Catalan数的组合意义102.5.2 Catalan数的应用123 Stirling数163.1 Stirling产生的历史163.2 第二类Stirling数163.2.1 定义163.2.2 几个计算公式173.2.3 性质183.3 第一类Stirling数183.3.1 定义183.3.2 几个计算公式193.3.3 性质203.4 第一类Stirling和第二类Stirling数的关系式203.5 Stirling数的组合意义及应用213.5.1 引言213.5.2 预备知识213.5.3 Stirling数的概率表示223.5.4 渐进与估计263.5.5 Stirling数的组合意义274 其他几种常见的组合数284.1 Fine数284.1.1引言284.1.2 Dyck格路与Catalan数284.1.3 Fine数的基本性质和概念294.1.4 Fine数的几个重要的恒等式304.1.5 Fine数的组合意义314.2 Plya计数314.2.1 Plya计数产生的历史314.2.2预备知识324.2.3 Plya计数定理334.2.4 Plya计数的例子与性质335 总结37致谢38参考文献39附录A 英文原文40附录B 中文翻译46IV1 绪 论1.1组合数学的研究背景和意义现代数学可以分为两大类：一类是研究连续对象的，如分析、方程等，另一类就是研究离散对象的组合数学。组合数学不仅在基础数学研究中具有极其重要的地位，在其它的学科中也有重要的应用，如计算机科学、编码和密码学、物理、化学、生物等学科中均有重要应用。微积分和近代数学的发展为近代的工业革命奠定了基础。而组合数学的发展则是奠定了本世纪的计算机革命的基础。计算机之所以可以被称为电脑，就是因为计算机被人编写了程序，而程序就是算法，在绝大多数情况下，计算机的算法是针对离散的对象，而不是在作数值计算。正是因为有了组合算法才使人感到，计算机好像是有思维的。组合数学不仅在软件技术中有重要的应用价值，在企业管理，交通规划，战争指挥，金融分析等领域都有重要的应用。在美国有一家用组合数学命名的公司，他们用组合数学的方法来提高企业管理的效益，这家公司办得非常成功。此外，试验设计也是具有很大应用价值的学科，它的数学原理就是组合设计。用组合设计的方法解决工业界中的试验设计问题，在美国已有专门的公司开发这方面的软件。1.2国内外研究现状组合数学在国外早已成为十分重要的学科，甚至可以说是计算机科学的基础。一些大公司，如IBM，AT&T都有全世界最强的组合研究中心。Microsoft 的Bill Gates近来也在提倡和支持计算机科学的基础研究。例如，Bell实验室的有关线性规划算法的实现，以及有关计算机网络的算法，由于有明显的商业价值，显然是没有对外公开的。美国已经有一种趋势，就是与新的算法有关的软件是可以申请专利的。如果照这种趋势发展，世界各国对组合数学和计算机算法的投入和竞争必然日趋激烈。美国政府也成立了离散数学及理论计算机科学中心DIMACS（与Princeton大学，Rutgers大学，AT&T 联合创办的，设在Rutgers大学），该中心已是组合数学理论计算机科学的重要研究阵地。美国国家数学科学研究所（Mathematical Sciences Research Institute，由陈省身先生创立）在1997年选择了组合数学作为研究专题，组织了为期一年的研究活动。日本的NEC公司还在美国的设立了研究中心，理论计算机科学和组合数学已是他们重要的研究课题，该中心主任R. Tarjan即是组合数学的权威。美国重要的国家实际室（Los Alamos国家实验室，以造出第一颗原子弹著称于世），从曼哈顿计划以来一直重视应用数学的研究，包括组合数学的研究。不仅如此，该实验室最近还在积极充实组合数学方面的研究实力。美国另外一个重要的国家实验室Sandia国家实验室有一个专门研究组合数学和计算机科学的机构，主要从事组合编码理论和密码学的研究，在美国政府以及国际学术界都具有很高的地位。由于生物学中的DNA的结构和生物现象与组合数学有密切的联系，各国对生物信息学的研究都很重视，这也是组合数学可以发挥作用的一个重要领域。由于DNA就是组合数学中的一个序列结构，美国科学院院士，近代组合数学的奠基人Rota教授预言，生物学中的组合问题将成为组合数学的一个前沿领域。传统的计算机算法可以分为两大类，一类是组合算法，一类是数值算法（包括计算数学和与处理各种信息数据有关的信息学）。近年来计算机算法又多了一类：那就是符号计算算法。吴文俊院士开创的机器证明方法就属于符号计算，引起了国际上的高度评价，被称为吴方法。而国际上还有专门的符号计算杂志。符号算法和吴方法跟代数组合学也有十分密切的联系。组合数学，数值计算（包括计算数学，科学计算，非线性科学，和与处理各种信息数据有关的信息学）和统计学可能是应用最广的数学分支，而组合数学的价值甚至不亚于统计学和数值计算。由于数学机械化近年来的发展和在计算机科学中的重要性，把数学机械化，科学计算和组合数学组合起来，就可以说是中国信息产业的基础。组合数学家H. Wilf和D. Zeilberger1998因为在组合恒等式的机械化证明方面的成果，获得1998年美国数学会的Steele奖。Thomson Science公司创刊的一份电子刊物离散数学和理论计算机科学即是一个很好的说明。它的内容涉及离散数学和计算机科学的众多方面。由于计算机软件的促进和需求，组合数学已成为一门既广博又深奥的学科，需要很深的数学基础，逐渐成为了数学的主流分支。除上述以外，欧洲也在积极发展组合数学，英国、法国、德国、荷兰、丹麦、奥地利、瑞典、意大利、西班牙等国家都建立了各种形式的组合数学研究中心。近几年，南美国家也在积极推动组合数学的研究。澳大利亚，新西兰也组建了很强的组合数学研究机构。值得一提的是亚洲的发达国家也十分重视组合数学的研究。日本有组合数学研究中心，并且从美国引进人才，不仅支持日本国内的研究，还出资支持美国的有关课题的研究，这样使日本的组合数学这几年的发展极为迅速。台湾、香港两地也从美国引进人才，大力发展组合数学。新加坡，韩国，马来西亚也在积极推动组合数学的研究和人才培养。台湾的数学研究中心也正在考虑把组合数学作为重点方向来发展。2 Catalan数2.1 Catalan产生的历史Catalan数:1,1,2,5,14,42,132,是组合数学中应用广泛的重要计数函数,本文记作。比利时数学家E.C.Catalan(1814-1894),在1838年发表的一篇论文中讨论了尔后所称的Catalan问题:n个不同因子间连续作乘法,如何确定不同的求积方法数?他获得Catalan数的计数公式:,. (2.1)它表示算数三角形“中垂线”上的数递次除以自然数后所得的数列。现代组合数对Catalan数的深入研究,发现了许多具有组合意义的应用实例,有人估计不少于50种。其中,特别是许多西方数学家不了解中国历史上对Catalan数的研究成果,清代数学家明安图(约1692?-1763?)是Catalan数的首创者,现在已逐步被国内外数学界承认.明安图之后,还有几位清代数学家对此也有研究,均在1838年之前,大多鲜为人知。经典Catalan数的产生Newton二项式定理。 (2.2) 当指数时,Newton二项式定理展开式必然可以表示成Catalan数作系数的幂级数。但是,Newton并没有把系数写成Catalan数的形式。明安图是Catalan数的首创者最早发现Catalan数的是我国清代数学家明安图。17世纪30年代他在研究无穷级数时得到该数的3种算法,并多次将它应用于运算中.其中,两种算法公式是现今组合数学书籍、论文中都未知的.他的有关成果详载于遗著割圆密率捷法中,由后人整理出版。Catalan数的卷积型递推公式,.明安图在计算无穷级数时首先发现了这一规律,并在计算中两次运用。明安图一项重要的工作是获得了Catalan数的组合递推公式 ,。 (2.3)初始条件是C=1,C=1。此式为世界首创,区别于西方在历史上和现代求Catalan数的所有方法。除了他的算法之外,迄今没有现代的证明。式(2.3)当时有C=C=2,C=2C=2,。明安图在研究无穷级数展开式过程中多次用到式(2.3),说明可表示为它前边若干项与算数三角形中第n条斜线上若干组合数乘积的代数和。明安图建立了3个几何模型,通过复杂的几何、代数、级数运算,从其中两个获得式(2.3),一个获得式(2.5),(2.6) 。后者是从原文中经抽象建起的一个奇特的计数结构。设以下的算法步骤为, (2.4) (2.5)这种算法相当于建立了一种生成函数,英国数学家P.J.Larcombe给出了一个现代证明。明安图应用中国传统数学方法割圆连比例法得到二倍角正弦的无穷级数展开式: (2.6)它的系数是Catalan数。式(2.6)为世界数学史上首创,其正确性可由二项式定理得到证明。他进而研究了四倍角正弦的无穷级数展开式,它的系数同样可表示为Catalan数的函数: (2.7)Larcombe已把上述结果推广到的情况。L.Euler(1707-1783)的创造性工作用n-1条不相交的对角线将一个凸n+2边形分割为n个三角形的数学方法数为。由于此例在几何或组合数学中经常遇到,具有典型性,这个结果曾多次被发现。当Catalan数成为组合数学家关注的课题时,人们才从Euler的著作中得知,他在1758-1759年的一篇论文中早已提出这个问题,并予以解决。在西方为首创,要比Catalan早80年。清代数学家董佑诚(1791-1823)的工作董佑诚受明安图的影响,在割圆连比例法图解中获得 (2.8)当m=2时,式(2.9)就成为式(2.7),比较它们的系数,知有, (2.9) , (2.10) E.C.Catalan的工作上已述及,Catalan于1838年提出并解决了n个不同的因子间连续作乘法时不同的方法数为的问题,他同时获得了式(2.1),(2.3) 。虽然,他不是最早的发现者,但他的工作产生了较大的影响,引起数学家的注意,也丰富了组合数学的内容。J.Binet的生成函数 (2.11)展开式可以用Newton二项式定理得到证明。其中的系数是Catalan数。2.2 Catalan数的定义Catalan数是为纪念比利时数学家Catalan(1814-1894)而以他的名字命名的。Catalan数的定义有很多种,下面我们先看一个源于Catalan数研究的实例,给出Catalan数的一种定义。例1 将凸n+1边形用不相交的对角线对进行三角剖分,求所有不同的三角剖分方案数。所谓凸n边形,即n边形内任意两点的连线线段都在该n边形内。例如,正五边形有如图2.1所示的5种三角剖分方案,即。图2.1 我们把满足递推关系 的序列 (n=1,2,3,)称为Catalan序列,其中称为第n个Catalan数,前几个Catalan数为1,1,2,5,14,42,132,429,1430,4862,2.3 关于Catalan数的几种求法2.3.1 引言Catalan数首先是由Euler在精确计算凸多边形的不同的对三角形剖分的个数问题时得到的。这个问题是:在一个凸n+1边形中,通过插入内部不相交的对角线形将其分成一些三角形区域的不同分法数。令h(n)表示一个n+1条边的凸多边形为三角形的方法数,且规定h(1)=1,则h(n)满足下列递推关系式: (2.12)满足(2.12)的h(n)称为Catalan数。由(2.12)可以利用递推关系得到.但计算过程比较复杂,下面我们通过其他模型得到递推关系式(2.12),而用另外的方法确定Catalan数。2.3.2 组合模型及求法假定X是一具有乘法运算的代数系统,乘法不满足结合律,如果,而且这n个元素依上面列出的顺序所能做出的一切可能的积彼此不同,其个数记为。如果在的某些字母之间加上括号,但不改变字母间的相对位置关系,使得n个字母间的乘法可以按所加括号指明运算方式进行运算,那么就是加括号的方法的个数。最外层的两对括号形如当k=1或n-1时,记。在前一个括号有,后一个括号中又有种加括号的方法,从而可得满足以下递推关系式: (2.13) 即就是是Catalan数。2.3.3 路径模型及求法考虑如下问题:从平面上(0,0)点出发到(n,n)点的除端点外不接触直线y=x,且在直线y=x下方的路径数g(n),显然g(n)即就是从点(0,0)到点(n,n)的满足条件的路径数关于k的和,即g(n)满足: (2.14)即g(n)就是Catalan数。上述路径数可以看成是从(0,0)点出发,每一次向上或向右游动一个单位,且在直线y=x下方,最终到达点(n,n)的路径数,即为从(1,0)出发到达(n,n-1)点的路径数。也就是在2n-2次游动中向上和向右游动n-1次,因而可能结果总数为。因此组合数中包含有接触直线y=x的情形,对其中任一条接触对角线的路径,就可把它从最后离开y=x的点A关于直线y=x作个反射,由反射原理可知:从A到B的路径中触到或者穿过y=x直线的路径的个数等于从到B的路径的个数。证 考虑一个从A到B且在y=x直线上有一个或一个以上的顶点的路径。为了表述方便现把直线y=x设为一个新的坐标轴t,令t为第一个这样的顶点的横坐标(参见图2.2) 。也就是说:选取t,使得。因此,是引导到B的路径,而且T=(t,0)是它在t轴上的第一个顶点。折线AT和T互为反射,从而所有从A到B的有一个顶点在t轴上的路径与全部从到B的路径之间存在一个一一对应。BAT图2.2 反射原理的示意图即得从(0,1)出发经过点A到(n,n-1)的路径数,其总数为。因而从(1,0)点出发到点(n,n-1)且在y=x下方的路径数为。从而可得从(0,0)点出发到(n,n)点不接触直线y=x,且在y=x下方的路径数为:2.3.4 生成函数法下面利用生成函数来确定Catalan数由(2.13)有 (2.15)令带入(2.15)式有:又由于 从而可得:解之可得:由定义有,从而只能取: 由牛顿二项式定理有代入有:,所以的的系数为:2.4 Catalan数的性质性质1 性质2 性质3 性质4 性质5 性质6 性质7 性质8 性质9 设m是任一正整数,当时,有:i)ii) iii)当时,有: 性质10 ,这个是Catalan数的增长趋势.2.5 Catalan数的组合意义及应用2.5.1 Catalan数的组合意义 经典Catalan数具有许多组合应用背景,除了以上所引几何、代数、三角问题外,不少是组合学或图论问题的实例。我们依据文献13,查阅若干相关著作,又补充若干新例,得到以下20种,有的具有典型性,有的可以看作组合模型,有的形式有别,实质相同。1)不同构的有n条边的种植树(planted tree)的棵树是Catalan数。2)有n片树叶的有序三度树根的个数是Catalan数。3)n个顶点的不同二元树的个数是Catalan数二元树的定义:空集或一组有限个顶点,满足:有一个特定的点称作“根点”;去掉这个根点后,余下的顶点组成两支子二元树:左子树与右子树。4)从点(0,0)到点(n+1,n+1),除端点外与对角线不相交的(在在对角线一侧的)非降路径数是Catalan数。5)循环序列满足递推关系:, 是Catalan数。由此可知:。6)2n个均匀分布在一个圆周上,用n条不相交的弦将这2n个点配对成n对,则不同的配对方式数是C=,(n0) 。7)序列(x,x,x),其中x=+1或-1,(i=1,2,2n)满足条件,对于每个k=1,2, ,2n-1,2n,则满足上述条件的数是Catalan数。8)n个1和n个0组成一2n位的二进制数,要求从左到右扫描,1的累计数不小于0的累计数,满足这一条件的2n位的二进制数的个数是Catalan数。9)在两个候选人A和B的投票选举中,共有2n个人投票,最终结果是支持A的票数和B票数都是n票。在开票过程中始终使A的票数不少于B的票数的投票方案数是Catalan数。10)有2n个人在剧院票房门前准备买票入场。每张票价是50美分,而且此时票房售票员没有零钱。这2n人恰好有n个人有50美分的钱,其余n个人只有1美分的钱。如果在任何时候售票员都能找开零钱的2n个人的排列方法数是Catalan数。11)有2n个高低不同的人,排成两行,使得第一排n个人都比第二排n个人高的排列方法是Catalan数。12)设是n个正整数不同排列的集合数,且满足下列条件: , (对任意的kn),则是Catalan数。13)设为整数,且满足下列条件:,则满足上述条件的序列的个数是Catalan数。14)设与是两个完全不同的序列,则把这两个序列融合在一起组成一个新的序列,使得后一个序列与前一个序列相对应的数始终排在前一个序列数后面的排列的个数是Catalan数。15)设与是两个完全不同的序列, 则把这两个序列融合在一起组成一个新的序列。一个逆序是指排在的后面(i=1,2,n),则这两个序列融合在一起恰有k个逆序的排列数是Catalan数。16)设在上定义了一种非结构合、非交换的乘法运算,则由A的全体元素作成的乘积的方法数,其中为Catalan数。17)有2n个人围着桌子就坐,手臂不相交的握手的方法数是Catalan数。18)有一个凸的(2n-1)角形,将它们成对连接,并使得连接的线段在(2n-2)角形内不相交的方法数是Catalan数。19)由n个1,n个0组成到2n位二进制数,要求从左向右扫描前2n-1,位数为1的累计数大于0的累计数,则满足这样条件的数的个数是Catalan数。20)n个数相乘,不改变他们的位置,只用括号表示不同的相乘顺序,则构成不同的乘积的方法数是Catalan数。2.5.2 Catalan数的应用Catalan数列问题内涵丰富、应用广泛,对其进行真正意义上的科学研究并取得真正的进展需要很深的功力。下面我们针对Catalan数组合意义中的几类问题进行求解。在日常生活中,我们常常会遇到以下的一些问题:售票问题:一个售票亭前排着2n个人的队伍等候购票,假定他们都购买价值1元的同一种票,其中有n个人持1元币,n个人持2元币,而售票员开始售票时没有零钱,问有多少种排队方式,可使得售票员能依次顺利售票,而不出现找不出钱的局面? 城市线路问题:某城市的道路由若干条给定的相互垂直的街道组成,但由于各种地形、建筑的影响,有些地形并非完整.问从任意指定地点到另一地点共有多少种不同的最短路线?唱票问题:2(n-1)张选票投给甲、乙两个候选人,每人均各得n-1张,要求唱票时任一时刻甲所得票数乙所得票数,问这样的唱票方式有多少种?以上三个以及其他一些问题看似毫不相干,可是却奇迹般地建立在同一个数学基础之上,它就是我们要探究的主题:Catalan数列。数列成为Catalan数列,若满足递推式: () (2.16)Catalan数列中的数称为Catalan数。Catalan数列的通项公式为并给出如下结论:结论1 设是n个实数,则在乘积中添加圆括号的不同方式数。结论2 已知平面上的点O(0,0),A(n,n),则在对角线OA之上从O至A的非经路径(即行走方向向上或向右)的条数。1、售票问题现在分两步解决问题。第一步,将持1元币的n个人彼此之间看作没有区别,均设为1,持2元币的n个人彼此之间也看作没有差异,均设为2。在此种假定条件下求符合条件的排队方式种数为。建立如图2.3的坐标系,则从O到A在OA之上非降路径与问题中在上述假定条件下排队方式之间是一一对应关系。其方法是从O开始向上走一格意味着排“1”,向右走一格意味着排“2” 。如图2.51中粗线所对应的一种排队方式是121122111222。因为从O至A在OA之上的每一条非降路径对应的一种排队方式,从前向后的每一个人前排“1”的均不少于票“2”的,故都是符合条件的排队方式。反之,符合条件的一种排队方式对应着从O到A在OA之上的一条非降路径。故由结论2, 。第二步,对第一步的每种排队方式,对n个“1”进行全排列,对n个“2”也进行全排列,各有n!种排法.所以由乘法原理,问题的答案:O2222221 111A图2.3 售票问题2、城市线路问题 “城市线路问题”是一类问题的总称,其中有些情形复杂,有些情形简单。根据各城市路线布局的不同,这类问题会有各式各样的变化,并且需要各种不同的技巧。下面让我们以一种较为简单的情形作为例子来探讨一下。(如图2.4)AB 图2.4 城市路线问题显然,在题中“最短路线”的限制下,最下面的一行、最左面的一列和顶部的两个小格是不能通过的,因此我们就可以把图2.4简化成图2.5的样子。A B图2.5 简化的城市路线问题在图2.5中,我们注意到,-和-这两条虚线是不能通过的,因此、这四个点就占有一定的特殊地位。 基于前面关于Catalan数阵的知识和简单的容斥原理,我们可以做出如下计算(用(XY)表示从点X到点Y的不同走法总数) 。AB=AB=AB=3、唱票问题若将甲、乙二人所得的选票分别记为1与0,则问题即是将n-1个1与n-1个0排成一列,求对任意的,使得前边k个数字中1的个数均不少于0的个数排列数。可认定。对于n=2,3,4,将2(n-1)个数的符合上述要求的排列方式展示如下(从而得到):10; 1100,1010; 111000,110100,110010,101100,101010。按照要求,此种唱票序列的首元必是1。前面通过Catalan数的组合意义我们知道: 2n个点均匀分布在一个圆周上,用n条不相交的弦将这2n个点配对成n对,则不同的配对方式数是,因此建立如下映射:唱票问题不相交连弦方式,即将唱票序列中(由前向后) 第一个出现的0与其前紧邻的1相配,然后划去此对0,1,再按如上做法继续,直到将唱票序列中配对点的序号两两连弦,即得到3)的一种不相交连弦。例如,n=6,唱票序列1011010010即对应于如下的不相交连弦(如图2.6),不难说明,这样定义的映射是一一映射,从而建立了关系(为不相交连弦的方式数)1110112101310111911111410101810151711161图2.6 唱票问题3 Stirling数3.1 Stirling产生的历史Stirling数有两种，第一类和第二类Stirling数，它们自18世纪以来一直吸引许多数学家的兴趣，如欧拉、柯西、西尔沃斯特和凯莱等。后来哥本哈根(Copenhagen)大学的尼尔森(Niels Nielsen，1865-1931)提出了Stirlingschen Zahlen erster Art 第一类Stirling数和Stirlingschen Zahlen zweiter Art 第二类Stirling数，首次把这两类数冠以Stirling数之名。因为苏格兰数学家斯特林(1692-1770)首次发现这些数并说明了它们的重要性。Stirling数的概念是由J. Stirling于1730年在他的著作Methodus Differentialis中首次提出。此后，许多学者对这方面做了大量的研究。1933年，Ch. Jordan在他的一篇论文中对Stirling数做了彻底的阐述，并给出了一些Stirling数重要的性质。3.2 第二类Stirling数3.2.1定义令,根据定理8.21和8.22,的差分表的第0条对角线有形式且 (3.1)如果p=0,则,它是一个常数,公式(3.21)化为特别地由于作为n的多项式有一个等于0的常数项,故若,也有 通过引入新的表达式改写成公式(3.1).令 我们注意,与相同,即n个不同物体的k-排列数(见文献113.2节),但是,现在希望用不太麻烦的记号.我们还注意到由于得到因此,公式(3.1)可以改写为现在我们引入数 则公式(3.1)变为 刚刚引入的数叫做第二类Stirling数。3.2.2 几个计算公式 定理3.2.1 如果,则定理3.2.2 第二类Stirling数是将p个元素的集合划分成k个不可辨别的非空盒的划分的个数。 引理3.23 时,时,时,3.2.3 性质性质1 性质2 ,性质3 3.3 第一类Stirling数3.3.1 定义第二类Stirling数指出如何利用写出.第一类Stirling数的作用则相反.它告诉我们如何用写出.由定义 (3.2)因此i) ii) ii) iv) v) 一般地,公式(3.2)右边的乘积有p个因子.如果将其乘开,就得到含有n的幂的多项式,其系数的符号正负相间;就是说,得到形如 (3.3)的表达式.第一类Stirling数就是出现在公式(3.3)中的系数 和 因此,第一类Stirling数满足与第二类Stirling一样的初始条件。但是,它们满足不同的递推关系。3.3.2几个计算公式定理3.3.1 如果,则定理3.3.2 第一类Stirling数是将p个物体排成k个非空的循环排列的方法数。定理3.3.3 时, ,定理3.3.4 时,3.3.3 性质性质1 性质2 性质3 3.4 第一类Stirling和第二类Stirling数的关系式 组合数学中的许多问题是数学中的精华,组合数学的应用也涉及到自然科学的许多领域,本文给出第一类Stirling数和第二类Stirling数的独立计算公式。定理3.4.1对于任意的正整数n,有, ,时, ,其中是矩阵的k阶主子式之和.特别地, ,时, 。定理3.4.2 对于任意的正整数,有, ,而当时,引理3.4.3 第一类Stirling数满足递归关系 , 。引理3.4.4 第二类Stirling数满足递归关系 , 。定理3.4.5 第一类Stirling数满足定理3.4.6 第二类Stirling数满足定理3.4.7 ,即3.5 Stirling数的组合意义及应用3.5.1 引言利用概率论的方法系统地研究组合问题,最早由Erdls和Spencer提出。但是,这一方向的研究成果不是很多,而且主要集中在概率论方法在Ramsey理论、随机图、组合优化等方面的应用,以及在经典组合问题中,用Monte Carlo方法处理组合计数的数值解.我们发现,许多组合数及组合多项式,以后称为组合变量,包括Stirling数,Bell数,Bernouli数,分拆数以及Bernouli多项式,Hermite多项式,Bessel多项式,Gegenbauer多项式等都和随机变量的矩有关。同时,符号运算中的伞变量(umbral operator)也与概率论有密切的联系。因此,概率的方法和技巧可以在一些经典组合问题中得到广泛应用。本文只讨论Stirling数,证明两类Stirling数是随机变量和的矩,对于类型的组合建立了一个统一的处理方法,我们或者能求出这种和式,或者至少也能得到一个恒等式。组合恒等式中的参数不应当仅仅看成一个常数,而应被视为一个随机变量(常数是随机变量的特例),这样我们就可以从一个简单的恒等式中推导出许多(甚至无穷多个)新的、有趣的恒等式.最后,利用中心极限定理,我们得到了k固定时,S(n,n-k)的渐进形式,它在时与精确公式完全吻合。3.5.2 预备知识本文所涉及的概率论知识,其中主要是矩和条件期望的概念。如果X是一个连续随机变量(下文简记为),它有密度函数f(x),满足.那么,对任何一个Borel可测函数,的矩定义为 (3.4)特别地, 1)时,(3.4)称为X的n阶矩; 2)时,(3.4)称为X的期望; 3)如果X,Y是两个,那么 是X关于事件Y=y的条件概率密度。称为X关于事件Y=y的条件期望,它是y的函数,记作,那么是一个,称为X关于Y的条件期望.我们将使用如下的全数学期望公式:来推导Stirling数的递推关系。本文中,只涉及到两种常见的的连续1)均匀分布,称为X服从上的均匀分布,密度函数为所以2)指数分布,称为X服从参数为的指数分布,密度函数为所以当X与Y独立时,它们乘积的矩等于矩的乘积: . (3.5)这个性质在本文中起着重要的作用,此外,我们沿用概率论常用的符号,当一列不仅是独立的,而且分布还相同,则记为3.5.3 Stirling数的概率表示定理3.5.1 如果随机变量V服从二项分布，则它的任意m阶原点矩为这里是第二类Stirling数,为降阶乘。证明 我们定义降阶乘为，则第二类Stirling数又常常被定义为： (3.6)注意到降阶乘的定义以及,因此V的降阶乘的数学期望为： ，把式中的x换为随机变量V再取数学期望，则得证。定理3.5.2 假设序列并且与独立,则时,1)第一类Stirling数s(n,k) (3.7) (3.8)规定。2)第二类Stirling数S(n,k)满足 (3.9) (3.10) (3.11)规定.证明 这里仅证明2)式(3.9) .证毕。式(3.7)、(3.9)和(3.10)是把两类Stirling数分别表示成某些随机变量和的矩,这种概率表示是对Stirling数的一种构造性描述,从而为研究Stirling提供了新的工具。主要结论如下:定理3.5.3 第二类Stirling数S(n,k)和第一类Stirling数s(n,k)有以下性质:(i),.(ii),其中为调和数。 证明 由(3.9)式,显然,由(3.10)式也可以得到相应的值。由(3.7)式,显然,文献9根据引理,运用概率技巧重新得到了有关两类Stirling数的递推公式和.另外我们还可以重新得到下面的递推公式:定理3.5.4 .下面简单给出该递推公式的推导过程:记,由(3.75)式此外我们还可以发现如下一些新的递推公式。定理3.5.5 第二类Stirling数S(n,k)和第一类Stirling数s(n,k)满足下列递推关系: 3.5.4 渐进与估计这一节我们利用概率论的技巧给出两类Stirling数的估计,首先介绍一个概率不等式.Minkowski 不等式 如果,则定理3.5.5 当, 证明 当时,的密度函数为.所以.因为与的独立性,由定理(3.5.2),.而由Minkowski不等式,即.利用定理3.5.2和中心极限定理,我们还能得到当k固定时,的渐近行式,为方便记,我们把化为的形式。定理3.5.6 任给固定的,当时,. 3.5.5 Stirling数的组合意义1)由k个轮换构成的n阶置换的个数为。2)恰可表示成k个互不相交的轮换乘积的n元置换共有(-1)个。3)把n件相异物分别放到k个相同盒中使得无一盒空的不同放法共有种。4)把n元集划分成k个非空子集的方法数为。5)n元集无序拆分为k个非空子集的方法数为。6) n个不同球,放入m个相同的盒中,盒非空,其放法数为。n个不同球,放入m个不同的盒中,盒非空,其放法数为。4 其他几种常见的组合数4.1 Fine数4.1.1引言由于Fine数和格路有着紧密的联系,所以在介紹Fine数之前,我们先来简单了解一些格路的相关知识。在平面直角坐标系中,横坐标和纵坐标都为整数的点称为平面格点,平面格路径是指在所有的平面格点中,从一点到另一点走格点的路,格路径的长度是指其所走的路的步数。我们这里研究的都是平面格路径,下面都简称为路径。一条长度为n的格路径也可以看做一个n维的向量,这里表示这条路径所走的步法之一。格路径是组合数学中非常重要的一个概念,因而有关格路径的研究在组合数学中一直占据着非常重要的位置,这是由于格路径不仅可以作为重要的模型来描述其他的组合统计量,像树,有禁排列,正交多项式,连分式等,也可以作为证明组合恒等式的重要工具,并且还在其他数学分支比如概率论,统计学,随机过程等有着广泛的应用.另外,格路径与生物信息学也有着很密切的联系。在计数组合数学的研究中,对格路径所走的步作不同的限制即得到不同类型的格路径。格路计数只要是研究这些不同类型的格路的数目和性质。Dyck格路是其中最典型的一类格路径,它与计数组合数学中的很多经典的序列有着很密切的联系, 下面我们先来介绍以下什么叫Dyck格路。4.1.2 Dyck格路与Catalan数定义4.1.1 一条2n长的Dyck格路是指在中,从原点(0,0)出发到(2n,0),由(1,1)方向的上升步和(1,-1)方向的下降步组成的,始终在x轴上方的一条路径.从(0,0)出发到(2n,0)的Dyck格路记做n-Dyck格路。为了更好地理解定义,我们画出n=2和n=3时所有的Dyck格路 图4.1两条长为4的Dyck格路 图4.2 五条长为6的Dyck格路我们把长度为2n的Dyck格路的集合记做。是由Catalan数来计数的,Catalan数的初值是1,1,2,5,14,42,132,429,1430,4862,并且Catalan数满足西面的递归关系式:命题4.1.2 ,其中命题4.1.3 命题4.1.4 4.1.3 Fine数的基本性质和概念本文主要研究Fine数的相关知识,在前面我们提到了Catalan数,对Catalan数有了一定的了解后,下面我们就来讨论Fine数的定义及其相关的性质。定义4.15 在中,一条2n长的Fine格路是一条不包含hill的2n长的Dyck格路。一个hill是由(1,1)方向的上升步和(1,-1)方向的下降步形成的高度为1的峰。从(0,0)出发到(2n,0)的Fine格路记做n-Fine格路。为了更好地理解定义,我们画出n=2, n=3和n=4时的所有的Fine格路图4.3一条长度为4的Fine格路4.4两条长度为6的Fine格路4.5 五条长度为8的Fine格路在这篇文章中,我们用u来表示上升步,用d来表示下降步。在一条格路中一对连续的ud步叫做峰,一个峰中所包含的d步叫做fall。格点指的是每一步的两个端点,我们把峰所包含的ud步中所有格点的纵坐标的最大值叫做峰的高度,一条格路的高度是所有峰的高度的最大值。 我们把长度为2n的Fine格路的集合记做。是由Fine数来计数,Fine数的初值是1,0,1,2,6,18,57,186,622,2120,Fine数的发生函数记做F(x),即。Fine数的发生函数和Catalan数的发生函数之间满足如下关系: 命题4.16 命题4.17 Fine数和Catalan数满足关系式:4.1.4 Fine数的几个重要的恒等式根据Fine数和Catalan数之间的关系,我们得到Fine数的若干性质如下:性质1 2(n+1)=(7n-5)+2(2n-1)性质2 ,其中性质3 性质4 4.1.5 Fine数的组合意义Fine数有很多组合解释,它和一些重要的组合对象,比如它和Dyck格路,Young表,分拆,平面树,Motzkin格路有比较紧密的联系。Deutsch和Shapiro在文献17中给出Fine数的一些组合解释,我们首先给出一个重要引理,下面的很多证明都是以此引理为基础。引理1 如果Dyck格路中第一峰的高度是k,那么它的发生函数是。性质2 从左向右看,满足第一个峰的高度是偶数的长度为2n的Dyck的格路计数是。性质3 具有型(n,n)且每列不出现形式的标准Young表的计数为。性质4 n的第一个块的长度是偶数的不变划分的计数是。性质 5 n的不包含可视的单点的不变划分的计数是。性质 6 n个结点的有序树中第一层上不包含叶子的有序树的计数是。性质 7 长度为n的2-Motzkin格路中x轴不包含水平步的计数是。4.2 Plya计数4.2.1 Plya计数产生的历史GPlya是美籍匈牙利数学家、教育家。他在数学的广泛领域里都有许多发现,又热心于教育,1980年被邀请担任第四次国际数学教育会议的名誉主席。他一生中发表过二百多篇论文和许多专著,其作品清晰优美,方法灵巧独特。被人们誉为“Plya的风格”、 “Plya的方法”。 Plya早在1937年就对树的计数和化合物的同分异构体的枚举问题进行研究,他巧妙地把发生函数、置换群和权函数三者结合起来,设计出一个枚举多项式,揭示了构形计数级数与构形群的循环指标和图形计数级数的关系,解决了许多计数问题。人们把这一方法叫做Plya计数定理。之后, Plya基本定理又有许多种推广形式,都有极为广泛的实际应用。4.2.2预备知识我们参照Plya原来的说法,把给定的两个有限集合D和R分别叫位置集和图形集。如dD就说有位置d,称rR是图形r。D到R的一个映射f叫做一个构形,由所有定义在D上取值于R中的构形作为一个集合叫构形集,并记作。若D是n元集,R是m元集,则有=n,=m,=m。把作用在n元集D上的一个n次置换群G叫做D的一个构形群。G中每一个置换g均可表为没有共同元的循环置换之积,若其中有b个长度为1的循环,b长度为2的循环等等,且,则说g是型的,并令称为置换群G的循环指标。我们说两个构形等价,当且仅当存在一,是对每个有。又把构形集的每一等价类叫做一个构形格式。给R的每个图形r指定一个权w,取值为k