沈阳理工大学学士学位论文
摘 要
组合数学是研究离散结构的存在、计数、分析和优化等问题的一门学科，它是计算机出现以后迅速发展起来的一门数学分支。近年来，组合数学不仅在软件技术中有着重要的应用价值，而且在企业管理，交通规划，战争指挥，金融分析等领域都有着重要的应用。组合数学在国外早已成为十分重要的学科，甚至可以说是计算机科学的基础。 本文通过对几类常见组合数的整理归纳,主要介绍了Catalan数、第一类、第二类Stirling、Fine数、Pólya计数等计数方法的历史起源、定义、基本性质等,研究组合数学及概率论有关知识，并根据组合计数和概率之间内在的联系，进而研究组合数学的组合意义在生活中某些领域的应用。组合数学所讨论的问题来源于实际。因此从内容来看确实丰富多彩,以至于很难用一句话来概括什么叫“组合数学”,本文只能就它所研究的若干问题进行介绍。
关键词:组合数学;概率论;组合意义;应用
I
沈阳理工大学学士学位论文
Abstract
Combinatorial 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 \this paper can only be described a number of issues’ studies.
Keywords: combinatorial mathematics; probability theory; combination of significance; application
II
沈阳理工大学学士学位论文
目 录
1 绪论 ........................................................................................................................................ 1
1.1组合数学的研究背景和意义 ....................................................................................... 1 1.2国内外研究现状 ........................................................................................................... 1 2 Catalan数 ............................................................................................................................. 3
2.1 Catalan产生的历史 ..................................................................................................... 3 2.2 Catalan数的定义 .......................................................................................................... 5 2.3 关于Catalan数的几种求法 ........................................................................................ 6
2.3.1 引言 .................................................................................................................... 6 2.3.2 组合模型及求法 ................................................................................................ 6 2.3.3 路径模型及求法 ................................................................................................ 7 2.3.4 生成函数法 ........................................................................................................ 8 2.4 Catalan数的性质 ......................................................................................................... 9 2.5 Catalan数的组合意义及应用 .................................................................................... 10
2.5.1 Catalan数的组合意义 ..................................................................................... 10 2.5.2 Catalan数的应用 ............................................................................................. 12
3 Stirling数 ......................................................................................................................... 16
3.1 Stirling产生的历史 .................................................................................................... 16 3.2 第二类Stirling数 ...................................................................................................... 16
3.2.1 定义 .................................................................................................................. 16 3.2.2 几个计算公式 .................................................................................................. 17 3.2.3 性质 .................................................................................................................. 18 3.3 第一类Stirling数 ...................................................................................................... 18
3.3.1 定义 .................................................................................................................. 18 3.3.2 几个计算公式 .................................................................................................. 19 3.3.3 性质 .................................................................................................................. 20 3.4 第一类Stirling和第二类Stirling数的关系式 ........................................................ 20 3.5 Stirling数的组合意义及应用 .................................................................................... 21
3.5.1 引言 .................................................................................................................. 21 3.5.2 预备知识 .......................................................................................................... 21 3.5.3 Stirling数的概率表示 ...................................................................................... 22 3.5.4 渐进与估计 ...................................................................................................... 26 3.5.5 Stirling数的组合意义 ..................................................................................... 27
4 其他几种常见的组合数 ...................................................................................................... 28
4.1 Fine数 ......................................................................................................................... 28
4.1.1引言 ................................................................................................................... 28 4.1.2 Dyck格路与Catalan数 ................................................................................... 28 4.1.3 Fine数的基本性质和概念 ............................................................................... 29 4.1.4 Fine数的几个重要的恒等式 ........................................................................... 30 4.1.5 Fine数的组合意义 ........................................................................................... 31 4.2 Pólya计数 ................................................................................................................... 31
III
沈阳理工大学学士学位论文
4.2.1 Pólya计数产生的历史 ..................................................................................... 31 4.2.2预备知识 ........................................................................................................... 32 4.2.3 Pólya计数定理 ................................................................................................. 33 4.2.4 Pólya计数的例子与性质 ................................................................................ 33
5 总结 ...................................................................................................................................... 37 致谢 .......................................................................................................................................... 38 参考文献 .................................................................................................................................. 39 附录A 英文原文 .................................................................................................................... 40 附录B 中文翻译 .................................................................................................................... 46
IV
沈阳理工大学学士学位论文
1 绪 论
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国家实验室，以造出第一颗原子弹著称于世），从曼哈顿计划以来一直重视应用数学的研究，
1
沈阳理工大学学士学位论文
包括组合数学的研究。不仅如此，该实验室最近还在积极充实组合数学方面的研究实力。美国另外一个重要的国家实验室Sandia国家实验室有一个专门研究组合数学和计算机科学的机构，主要从事组合编码理论和密码学的研究，在美国政府以及国际学术界都具有很高的地位。
由于生物学中的DNA的结构和生物现象与组合数学有密切的联系，各国对生物信息学的研究都很重视，这也是组合数学可以发挥作用的一个重要领域。由于DNA就是组合数学中的一个序列结构，美国科学院院士，近代组合数学的奠基人Rota教授预言，生物学中的组合问题将成为组合数学的一个前沿领域。
传统的计算机算法可以分为两大类，一类是组合算法，一类是数值算法（包括计算数学和与处理各种信息数据有关的信息学）。近年来计算机算法又多了一类：那就是符号计算算法。吴文俊院士开创的机器证明方法就属于符号计算，引起了国际上的高度评价，被称为吴方法。而国际上还有专门的符号计算杂志。符号算法和吴方法跟代数组合学也有十分密切的联系。组合数学，数值计算（包括计算数学，科学计算，非线性科学，和与处理各种信息数据有关的信息学）和统计学可能是应用最广的数学分支，而组合数学的价值甚至不亚于统计学和数值计算。由于数学机械化近年来的发展和在计算机科学中的重要性，把数学机械化，科学计算和组合数学组合起来，就可以说是中国信息产业的基础。组合数学家H. Wilf和D. Zeilberger1998因为在组合恒等式的机械化证明方面的成果，获得1998年美国数学会的Steele奖。
Thomson Science公司创刊的一份电子刊物《离散数学和理论计算机科学》即是一个很好的说明。它的内容涉及离散数学和计算机科学的众多方面。由于计算机软件的促进和需求，组合数学已成为一门既广博又深奥的学科，需要很深的数学基础，逐渐成为了数学的主流分支。
除上述以外，欧洲也在积极发展组合数学，英国、法国、德国、荷兰、丹麦、奥地利、瑞典、意大利、西班牙等国家都建立了各种形式的组合数学研究中心。近几年，南美国家也在积极推动组合数学的研究。澳大利亚，新西兰也组建了很强的组合数学研究机构。值得一提的是亚洲的发达国家也十分重视组合数学的研究。日本有组合数学研究中心，并且从美国引进人才，不仅支持日本国内的研究，还出资支持美国的有关课题的研究，这样使日本的组合数学这几年的发展极为迅速。台湾、香港两地也从美国引进人才，大力发展组合数学。新加坡，韩国，马来西亚也在积极推动组合数学的研究和人才培养。台湾的数学研究中心也正在考虑把组合数学作为重点方向来发展。
2
沈阳理工大学学士学位论文
2 Catalan数
2.1 Catalan产生的历史
Catalan数:1,1,2,5,14,42,132,…是组合数学中应用广泛的重要计数函数,本文记作
Cn。比利时数学家E.C.Catalan(1814-1894),在1838年发表的一篇论文中讨论了尔后所称的Catalan问题:n个不同因子间连续作乘法,如何确定不同的求积方法数?他获得Catalan数的计数公式:
Cn?1?2n???,(n?0). (2.1) ??n?1?n?它表示算数三角形“中垂线”上的数递次除以自然数后所得的数列。
现代组合数对Catalan数的深入研究,发现了许多具有组合意义的应用实例,有人估计不少于50种。
其中,特别是许多西方数学家不了解中国历史上对Catalan数的研究成果,清代数学家明安图(约1692?-1763?)是Catalan数的首创者,现在已逐步被国内外数学界承认.明安图之后,还有几位清代数学家对此也有研究,均在1838年之前,大多鲜为人知。
经典Catalan数的产生 Newton二项式定理
k?1??1?k(?1)2?z?1??2k?1Ck?1Zk(Z?1)。 (2.2) (1?z)?????K?0?k?K?1212?当指数??1时,Newton二项式定理展开式必然可以表示成Catalan数作系数的幂
2级数。但是,Newton并没有把系数写成Catalan数的形式。
明安图是Catalan数的首创者
最早发现Catalan数的是我国清代数学家明安图。17世纪30年代他在研究无穷级数时得到该数的3种算法,并多次将它应用于运算中.其中,两种算法公式是现今组合数学书籍、论文中都未知的.他的有关成果详载于遗著《割圆密率捷法》中,由后人整理出版。
Catalan数的卷积型递推公式Cn??Cn?kCk,(n?2).明安图在计算无穷级数时首
k?1n?1先发现了这一规律,并在计算中两次运用。
明安图一项重要的工作是获得了Catalan数的组合递推公式
3
沈阳理工大学学士学位论文
Cn?1?n?k???(?1)??k?1??Cn?k,(n?2)。 (2.3) k?0??k初始条件是C1=1,C2=1。此式为世界首创,区别于西方在历史上和现代求Catalan数的所有方法。除了他的算法之外,迄今没有现代的证明。式(2.3)当n?5时有C2=C1=2,C3=2C2=2,
?3??2??C4??C??1?3??2??C2?5, ?????4??3??C5??C??1?4??2??C3?14, ?????5??4??3????C6??C?C??1?5?2?4??3??C3?42。 ??????明安图在研究无穷级数展开式过程中多次用到式(2.3),说明Cn?1可表示为它前边若干项与算数三角形中第n条斜线上若干组合数乘积的代数和。
明安图建立了3个几何模型,通过复杂的几何、代数、级数运算,从其中两个获得式(2.3),一个获得式(2.5),(2.6) 。后者是从原文中经抽象建起的一个奇特的计数结构。
设M1?(1),M2?(0,1);以下的算法步骤为
M3?(2M1?M2)M2?[2(1)?(0,1)](0,1)?(2,1)(0,1)?(0,0,2,1), M4?[2(M1?M2)?M3]M3?(2,2,2,1)(0,0,2,1)?(0,0,0,4,6,6,4,1),
M5?[2(M1?M2?M3)?M4]M4?(0,0,0,8,20,40,68,94,114,116,94,60,28,8,1)
Mn?1?(2?Mk?Mn)Mn (2.4) MCn??Mk?(1,1,2,5,14,42,132,?,Cn) (2.5)
k?1nk?1n-1这种算法相当于建立了一种生成函数,英国数学家P.J.Larcombe给出了一个现代证明。
明安图应用中国传统数学方法—割圆连比例法得到二倍角正弦的无穷级数展开式:
sin2α?2sinα??Cnsin2n?1?/4n-1 (2.6)
n?1?它的系数是Catalan数。式(2.6)为世界数学史上首创,其正确性可由二项式定理得到证明。他进而研究了四倍角正弦的无穷级数展开式,它的系数同样可表示为Catalan数的
4
沈阳理工大学学士学位论文
函数:
sin4α?4sinα?10sinα??(16Cn?2Cn?1)sin2n?3α (2.7)
3n?1?Larcombe已把上述结果推广到2kα的情况。 L.Euler(1707-1783)的创造性工作
用n-1条不相交的对角线将一个凸n+2边形分割为n个三角形的数学方法数为Cn。由于此例在几何或组合数学中经常遇到,具有典型性,这个结果曾多次被发现。当Catalan数成为组合数学家关注的课题时,人们才从Euler的著作中得知,他在1758-1759年的一篇论文中早已提出这个问题,并予以解决。在西方为首创,要比Catalan早80年。
清代数学家董佑诚(1791-1823)的工作
董佑诚受明安图的影响,在《割圆连比例法图解》中获得
m(m2?1)3m(m2?1)(m2?32)5sinmα?msinα?sinα?sinα?… (2.8)
3!5!当m=2时,式(2.9)就成为式(2.7),比较它们的系数,知有
22n?1nC1?1,Cn???(2k?1)(2k?3),(n?2) (2.9)
(2n?1)!k?13 C1?1,Cn?2Cn?1(2?),(n?2) (2.10)
n E.C.Catalan的工作
上已述及,Catalan于1838年提出并解决了n个不同的因子间连续作乘法时不同的方法数为Cn的问题,他同时获得了式(2.1),(2.3) 。虽然,他不是最早的发现者,但他的工作产生了较大的影响,引起数学家的注意,也丰富了组合数学的内容。
J.Binet的生成函数
?1111?4x??Cnxn(x?) (2.11) ?224n?1展开式可以用Newton二项式定理得到证明。其中的系数是Catalan数。
2.2 Catalan数的定义
Catalan数是为纪念比利时数学家Catalan(1814-1894)而以他的名字命名的。Catalan数的定义有很多种,下面我们先看一个源于Catalan数研究的实例,给出Catalan数的一种定义。
5
沈阳理工大学学士学位论文
例1 将凸n+1边形用不相交的对角线对进行三角剖分,求所有不同的三角剖分方案数Cn。所谓凸n边形,即n边形内任意两点的连线线段都在该n边形内。例如,正五边形有如图2.1所示的5种三角剖分方案,即C4?5。
图2.1
我们把满足递推关系
?C?C1Cn-1?C2Cn-2???Cn-1C1 ?n
C1?1?的序列Cn (n=1,2,3,…)称为Catalan序列,其中Cn?1n-1C2n-2n?1,2,3,?)称为第n个Catalann数,前几个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)满足下列递推关系式:
n?1??h(n)??h(k)h(n?k) (2.12) ?k?1?h(1)?1?满足(2.12)的h(n)称为Catalan数。由(2.12)可以利用递推关系得到h(n)?1?2n-2???. ??n?n-1?但计算过程比较复杂,下面我们通过其他模型得到递推关系式(2.12),而用另外的方法确定Catalan数。 2.3.2 组合模型及求法
假定X是一具有乘法运算的代数系统,乘法不满足结合律,如果x1,x2,?,xn?X,而且这n个元素依上面列出的顺序所能做出的一切可能的积彼此不同,其个数记为f(n)。
6
沈阳理工大学学士学位论文
如果在x1,x2,?,xn的某些字母之间加上括号,但不改变字母间的相对位置关系,使得n个字母间的乘法可以按所加括号指明运算方式进行运算,那么f?n?就是加括号的方法的个数。最外层的两对括号形如(x1x2?xk)(xk?1?xn)(1?k?n?1)当k=1或n-1时,记
x1(x2?xn)?(x1x3?xn),(x1?xn?1)?(x1?xn?1)(xn)。在前一个括号有f?k?,后一个括号
中又有f(n-k)种加括号的方法,从而可得f(n)满足以下递推关系式:
n?1??f(n)??f(k)f(n?k),n?1 (2.13) ?k?1?f(1)?1?即就是f(n)是Catalan数。 2.3.3 路径模型及求法
考虑如下问题:从平面上(0,0)点出发到(n,n)点的除端点外不接触直线y=x,且在直线y=x下方的路径数g(n),显然g(n)即就是从点(0,0)到点(n,n)的满足条件的路径数关于k的和,即g(n)满足:
n?1??g(n)??g(k)g(n?k) (2.14) ?k?1?g(1)?1?即g(n)就是Catalan数。
上述路径数可以看成是从(0,0)点出发,每一次向上或向右游动一个单位,且在直线y=x下方,最终到达点(n,n)的路径数,即为从(1,0)出发到达(n,n-1)点的路径数。也就是在
?2n-2?2n-2次游动中向上和向右游动n-1次,因而可能结果总数为??n-1??。因此组合数中包含
??有接触直线y=x的情形,对其中任一条接触对角线的路径,就可把它从最后离开y=x的点A关于直线y=x作个反射,由反射原理[12]可知:从A到B的路径中触到或者穿过y=x直线的路径的个数等于从A'到B的路径的个数。
证 考虑一个从A到B且在y=x直线上有一个或一个以上的顶点的路径
?sa??,sa?1,?,sb???。为了表述方便现把直线y=x设为一个新的坐标轴t,令t为第一个
这样的顶点的横坐标(参见图2.2) 。也就是说:选取t,使得sa?0,?,st-1?0,st?0。因此,?-sa,-sa?1,?,-st-1,st?0,st?1,st?2,?,sb?是引导A'到B的路径,而且T=(t,0)是它在t轴上
7
沈阳理工大学学士学位论文
的第一个顶点。折线AT和A'T互为反射,从而所有从A到B的有一个顶点在t轴上的路径与全部从A'到B的路径之间存在一个一一对应。
图2.2 反射原理的示意图
B A T A' ?2n-2?即得从(0,1)出发经过点A到(n,n-1)的路径数,其总数为??n??。因而从(1,0)点出发到点
???2n-2??2n-2?1?2n-2?(n,n-1)且在y=x下方的路径数为??n-1??-??n???n??n-1??。从而可得从(0,0)点出发到
??????(n,n)点不接触直线y=x,且在y=x下方的路径数为:
g(n)?2.3.4 生成函数法
下面利用生成函数来确定Catalan数 由(2.13)有
1?2n-2???? n-1n??? f(n)?f(1)f(n-1)?f(2)f(n-2)???f(n-1)f(1) (2.15) 令S(x)??f(n)xn带入(2.15)式有:
n?1?s(x)?f(1)x???f(1)f(n?1)?f(2)f(n?2)???f(n?1)f(1)?xn
n?2?又由于
s(x)?(?f(n)x)?(?f(n)xn)
2nn?1n?1??8
沈阳理工大学学士学位论文
???f(1)f(n?1)?f(2)f(n?2)???f(n?1)f(1)?xn
n?2?从而可得:s(x)?x?s2(x)
11解之可得:s(x)?(1?1?4x)或s(x)?(1?1?4x)
221由s(x)定义有s(0)?0,从而只能取:s(x)?(1?1?4x)
2 由牛顿二项式定理有
111(?1)?(?n?1)?2?2n-2?nnn2221?4x?1??(?4)x?1??(?)??n-1??x n!nn?1n?1????11?2n-2?nnx?s(x)代入s(x)?(1?1?4x)有:s(x)???,所以的的系数f(n)为: x??2n?1n?n-1?1?2n-2??f(n)??? n-1n???2.4 Catalan数的性质
性质1 Cn?1?性质2 Cn?14n-2Cn n?1n?2n?CkCn?k,n?3 ?2(n?3)k?2?n?k?性质3 Cn?1??(?1)k??k?1??Cn?k
k?0????n?k?1??n?k???性质4 Cn??(?1)k?1???k????k?1???Cn?k,n?3
k?1???????2n??2n?性质5 Cn???n?????n?1??,n?0
????性质6 C0?1,Cn?1?2(2n?1)Cn n?221n?n?性质7 Cn???i?? n?1i?0???性质8 C0?1,Cn?1??CiCn?i,n?0
i?0n9
沈阳理工大学学士学位论文
性质9 设m是任一正整数,当n?m时,有: i)
k!!k?n?m???CC?C?(-1)??a1a2am?k?2m-nn!(k-2n)!!;
a1?a2???am?nk?0??mnmii)
a1?a2????n?C2a1-1C2a1-1?C2am-1???(-1)j?0k?0k?1-j?m?(m-k)!!k!!???k?22(m-n)?1j!(2n-j-1)!(m-k-2j)!!(k?2j?2-4n)!! ??m2nm-kkiii)当n?2m时,有:
k?l?p?m??m-k??k??CC?C?(-1)?????2a12a22am?k????l????j??
a1?a2???am?nk?0p?0l?0j?0??????
(m-k)!!k!!
22(m-n)p!(2n-p)!(l-2p)!!(l?p-2n)!!性质10 Cn~4nn32,这个是Catalan数的增长趋势.
?2.5 Catalan数的组合意义及应用
2.5.1 Catalan数的组合意义
经典Catalan数具有许多组合应用背景,除了以上所引几何、代数、三角问题外,不少是组合学或图论问题的实例。我们依据文献[13],查阅若干相关著作,又补充若干新例,得到以下20种,有的具有典型性,有的可以看作组合模型,有的形式有别,实质相同。 1)不同构的有n条边的种植树(planted tree)的棵树是Catalan数Cn2)有n片树叶的有序三度树根的个数是Catalan数Cn-1?1?。
3)n个顶点的不同二元树的个数是Catalan数Cn0二元树的定义:空集或一组有限个顶点,满足:①有一个特定的点称作“根点”;②去掉这个根点后,余下的顶点组成两支子二元树:左子树与右子树?1?。
4)从点(0,0)到点(n+1,n+1),除端点外与对角线不相交的(在在对角线一侧的)非降路径数是Catalan数Cn?1??1?。
。
5)循环序列满足递推关系:C0?1,(n?2)Cn?1?(4n?2)Cn,(n?0), Cn是Catalan数。由此
6可知:C0?1,Cn?(4-)Cn-1?1?。
n6)2n个均匀分布在一个圆周上,用n条不相交的弦将这2n个点配对成n对,则不同的配对
10
沈阳理工大学学士学位论文
方式数是Cn=
1?2n??1?,(n0) 。 ?????n?1?n?7)序列(x1,x2,…x2n),其中xi=+1或-1,(i=1,2,…,2n)
?x?x2???xk?0满足条件?1 ,对于每个k=1,2, …,2n-1,2n,则满足上述条件
x?x???x?022n?1的数是Catalan数?1?。
8)n个1和n个0组成一2n位的二进制数,要求从左到右扫描,1的累计数不小于0的累计数,满足这一条件的2n位的二进制数的个数是Catalan数?1?。
9)在两个候选人A和B的投票选举中,共有2n个人投票,最终结果是支持A的票数和B票数都是n票。在开票过程中始终使A的票数不少于B的票数的投票方案数是Catalan数Cn?1?。
10)有2n个人在剧院票房门前准备买票入场。每张票价是50美分,而且此时票房售票员没有零钱。这2n人恰好有n个人有50美分的钱,其余n个人只有1美分的钱。如果在任何时候售票员都能找开零钱的2n个人的排列方法数是Catalan数Cn是Catalan数Cn?1??1?。
11)有2n个高低不同的人,排成两行,使得第一排n个人都比第二排n个人高的排列方法
。
12)设Sn是n个正整数a1,a2,?,an不同排列的集合数,且a1,a2,?,an满足下列条件: ① a1?a2??an?n,② a1?a2??ak?k (对任意的k a1?1,a2?2,?,an?n,则a1,a2,?,an满足上述条件的序列的个数是Catalan数?1?。 14)设a1,a2,?,an与b1,b2,?,bn是两个完全不同的序列,则把这两个序列融合在一起组成一个新的序列,使得后一个序列与前一个序列相对应的数始终排在前一个序列数后面的排列的个数是Catalan数?1?。 15)设a1,a2,?,an与b1,b2,?,bn是两个完全不同的序列, 则把这两个序列融合在一起组成一个新的序列。一个逆序是指ai排在bi的后面(i=1,2,…,n),则这两个序列融合在一起恰有k个逆序的排列数是Catalan数?1?。 16)设在E?{e1,e2,?,en}上定义了一种非结构合、非交换的乘法运算,则由A的全体元素作成的乘积的方法数Un-1?n!Cn-1,其中Cn-1为Catalan数?1?。 17)有2n个人围着桌子就坐,手臂不相交的握手的方法数是Catalan数Cn?1?。 11 沈阳理工大学学士学位论文 18)有一个凸的(2n-1)角形A1,A2,?,A2n-2,将它们成对连接,并使得连接的线段在(2n-2)角形内不相交的方法数是Catalan数Cn-1?1?。 19)由n个1,n个0组成到2n位二进制数,要求从左向右扫描前2n-1,位数为1的累计数大于0的累计数,则满足这样条件的数的个数是Catalan数Cn-1?1?。 20)n个数相乘,不改变他们的位置,只用括号表示不同的相乘顺序,则构成不同的乘积的方法数是Catalan数Cn-1?1?。 2.5.2 Catalan数的应用 Catalan数列问题内涵丰富、应用广泛,对其进行真正意义上的科学研究并取得真正的进展需要很深的功力。下面我们针对Catalan数组合意义中的几类问题进行求解。 在日常生活中,我们常常会遇到以下的一些问题: ①售票问题:一个售票亭前排着2n个人的队伍等候购票,假定他们都购买价值1元的同一种票,其中有n个人持1元币,n个人持2元币,而售票员开始售票时没有零钱,问有多少种排队方式,可使得售票员能依次顺利售票,而不出现找不出钱的局面? ②城市线路问题:某城市的道路由若干条给定的相互垂直的街道组成,但由于各种地形、建筑的影响,有些地形并非完整.问从任意指定地点到另一地点共有多少种不同的最短路线? ③唱票问题:2(n-1)张选票投给甲、乙两个候选人,每人均各得n-1张,要求唱票时任一时刻甲所得票数?乙所得票数,问这样的唱票方式有多少种? 以上三个以及其他一些问题看似毫不相干,可是却奇迹般地建立在同一个数学基础之上,它就是我们要探究的主题:Catalan数列。 数列k1,k2,?,kn,?成为Catalan数列,若满足递推式: ?kn?k1kn-1?k2kn-2???kn-1k1 (n?2) (2.16) ?k?k?112?Catalan数列中的数称为Catalan数。Catalan数列的通项公式为 kn?1n-1(2n-2)!C2n-2? nn[(n-1)!]2并给出如下结论: 结论1 设x1,x2,?,xn是n个实数,则在乘积x1x2?xn中添加圆括号的不同方式数 an?k。 结论2 已知平面上的点O(0,0),A(n,n),则在对角线OA之上从O至A的非经路径(即 12 沈阳理工大学学士学位论文 行走方向向上或向右)的条数Cn?kn?1。 1、售票问题 现在分两步解决问题。 第一步,将持1元币的n个人彼此之间看作没有区别,均设为1,持2元币的n个人彼此之间也看作没有差异,均设为2。在此种假定条件下求符合条件的排队方式种数为xn。 建立如图2.3的坐标系,则从O到A在OA之上非降路径与问题中在上述假定条件下排队方式之间是一一对应关系。其方法是从O开始向上走一格意味着排“1”,向右走一格意味着排“2” 。如图2.51中粗线所对应的一种排队方式是12112211…122…2。因为从O至A在OA之上的每一条非降路径对应的一种排队方式,从前向后的每一个人前排“1”的均不少于票“2”的,故都是符合条件的排队方式。反之,符合条件的一种排队方式对应着从O到A在OA之上的一条非降路径。 故由结论2,xa?Cn?kn?1 。 第二步,对第一步的每种排队方式,对n个“1”进行全排列,对n个“2”也进行全排列,各有n!种排法.所以由乘法原理,问题的答案: Dn?kn?1?(n!)2? 1 … (2n)! n?1 A 1 1 O 2 2 2 2… 2 图2.3 售票问题 2、城市线路问题 “城市线路问题”是一类问题的总称,其中有些情形复杂,有些情形简单。根据各城市路线布局的不同,这类问题会有各式各样的变化,并且需要各种不同的技巧。下面让我们以一种较为简单的情形作为例子来探讨一下。(如图2.4) 13 沈阳理工大学学士学位论文 A B 图2.4 城市路线问题 显然,在题中“最短路线”的限制下,最下面的一行、最左面的一列和顶部的两个小格是不能通过的,因此我们就可以把图2.4简化成图2.5的样子。 A B E1E2 E3E4E5 图2.5 简化的城市路线问题 E6 在图2.5中,我们注意到,E1-E2和E3-E4这两条虚线是不能通过的,因此E1、E2、 E3、E4这四个点就占有一定的特殊地位。 基于前面关于Catalan数阵的知识和简单的容斥原理,我们可以做出如下计算(用(X →Y)表示从点X到点Y的不同走法总数) 。 A?B=A?E5E5?E6E6?B =A?E5E6?B =[f(8,4)-A?E1f(7,3)-A?E3f(4,1)?A?E1E2?E3f(4,1)]E6 ?B 13122?[f(8,4)-C1f(7,3)-C6f(4,1)?C1C4f(4,1)]C4 4313231012102?[(C12-C12)-C1(C10-C10)-C6(C5-C5)?C1C4(C5-C5)]C4 14 沈阳理工大学学士学位论文 ?864 3、唱票问题 若将甲、乙二人所得的选票分别记为1与0,则问题即是将n-1个1与n-1个0排成一列,求对任意的1?k?n-1,使得前边k个数字中1的个数均不少于0的个数排列数Dn。可认定D1?1。对于n=2,3,4,将2(n-1)个数的符合上述要求的排列方式展示如下(从而得到D2?1,D3?2,D4?5): 10; 1100,1010; 111000,110100,110010,101100,101010。 按照要求,此种唱票序列的首元必是1。前面通过Catalan数的组合意义我们知道: 2n个点均匀分布在一个圆周上,用n条不相交的弦将这2n个点配对成n对,则不同的配对方式数是Cn,因此建立如下映射: 唱票问题?不相交连弦方式,即将唱票序列中(由前向后) 第一个出现的0与其前紧邻的1相配,然后划去此对0,1,再按如上做法继续,直到将唱票序列中配对点的序号两两连弦,即得到3)的一种不相交连弦。例如,n=6,唱票序列1011010010即对应于如下的不相交连弦(如图2.6),不难说明,这样定义的映射是一一映射,从而建立了关系Dn?Bn(Bn为不相交连弦的方式数) 10 0 987 10 0 610121134015图2.6 唱票问题 15 沈阳理工大学学士学位论文 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定义 令hn?np,根据定理[11]8.21和8.22,hn的差分表的第0条对角线有形式 c?p,0?,c?p,1?,c?p,2?,?,c?p,p?,0,0,? 且 ?n??n??n? n?c?p,0???0???c?p,1???1?????c?p,p???p?? (3.1) ??????p如果p=0,则hn?1,它是一个常数,公式(3.21)化为 ?n?n0?1?1??0???1 ??特别地 c?0,0??1 由于np作为n的多项式有一个等于0的常数项,故若p?1,也有 c?p,0??0 ?p?1? 通过引入新的表达式改写成公式(3.1).令 16 沈阳理工大学学士学位论文 ?n?k?n?n-1???n-k?1?若k?1 ??1若k?0?我们注意,?n?k与P?n,k?相同,即n个不同物体的k-排列数(见文献[11]3.2节),但是,现在希望用不太麻烦的记号?n?k.我们还注意到 ?n?k?1??n-k??n?k 由于 ?n?n?n-1???n-k?1??n?k? ??k???k!k!??得到 ?n?k因此,公式(3.1)可以改写为 np?c?p,0?p?n??k!??k?? ???n?00!?c?p,1??n?1???c?p,p??n?p1!p! ??c?p,k?k?0p?n?kk!??c?p,k??n?kk!k?0 现在我们引入数 S?p,k??c?p,k? ?0?k?p? k!则公式(3.1)变为 np?S?p,0??n?0?S?p,1??n?1???S?p,p??n?p ??S?p,k??n?k k?0p刚刚引入的数S?p,k?叫做第二类Stirling数。 3.2.2 几个计算公式 定理?11?3.2.1 如果1?k?p-1,则 17 沈阳理工大学学士学位论文 S?p,k??kS?p-1,k??S?p-1,k-1? 定理?11?3.2.2 第二类Stirling数S?p,k?是将p个元素的集合划分成k个不可辨别的非空盒的划分的个数。 引理3.23 n?4时, 34 S(n,n?2)?Cn?3Cnn?6时, 456S(n,n?3)?Cn?10Cn?15Cn n?8时, 5478S(n,n-4)?Cn?25Cn?105Cn?105Cn 3.2.3 性质 性质1 S(n?1,k)??(?1)i[n]iS(i,k?1) i?01k性质2 S(n,k)??(?1)k!i?0性质3 S(n,2)?2n?1i?k?n??,0?k?n (k?i)?i????n?3n?1?1n?1? ?1,S(n,3)??2,S(n,n?1)????2?2?3.3 第一类Stirling数 3.3.1 定义 第二类Stirling数指出如何利用?n?0,?n?1,?,?n?p写出np.第一类Stirling数的作用则相反.它告诉我们如何用n0,n1,?,np写出?n?p.由定义 ?n?p?n?n-1??n-2???n-p?1? ??n-0??n-1??n-2???n-?p-1?? (3.2) 因此 i) ?n?0?1 ii) ?n?1?n 18 沈阳理工大学学士学位论文 ii) ?n?2?n?n-1??n2-n iv) ?n?3?n?n-1??n-2??n3-3n2?2n v) ?n?4?n?n-1??n-2??n-3??n4-6n3?11n2-6n 一般地,公式(3.2)右边的乘积有p个因子.如果将其乘开,就得到含有n的幂的多项式,其系数的符号正负相间;就是说,得到形如 ?n?p?s?p,p?np-s?p,p-1?np-1????-1?p-1s?p,1?n1??-1?ps?p,0?n0 ???-1?k?0pp-ks?p,k?nk (3.3) 的表达式.第一类Stirling数就是出现在公式(3.3)中的系数 s?p,k? ?0?k?p? 和 s?p,p??1 ?p?0? 因此,第一类Stirling数满足与第二类Stirling一样的初始条件。但是,它们满足不同的递推关系。 3.3.2几个计算公式 定理?11?3.3.1 如果1?k?p-1,则 s?p,k???p-1?s?p-1,k??s?p-1,k-1? 定理?11?3.3.2 第一类Stirling数s?n,p?是将p个物体排成k个非空的循环排列的方法数。 定理?7?3.3.3 n?3时, s(n,n?2)?n(n?1)(n?2)(3n?1), 24n2(n?1)2(n?2)(n?3)s(n,n?3)?? 48定理?7?3.3.4 n?8时, n(n?1)(n?2)(n?3)(n?4)(15n3?30n2?5n?2)s(n,n?4)? 242?1019 沈阳理工大学学士学位论文 3.3.3 性质 性质1 s(n?1,k)??(?1)i[n]is(n?i,k?1) i?0?n?1性质2 s(n,2)?(?1)(n?1)!?,s(n,n?1)????2?? kk?1??nn?1性质3 ?s(n,k)?n!;?s(n,k)?0,n?1;?s(n,k)xk?1k?0k?0nnnk?[x]n 3.4 第一类Stirling和第二类Stirling数的关系式 组合数学中的许多问题是数学中的精华,组合数学的应用也涉及到自然科学的许多领域,本文给出第一类Stirling数和第二类Stirling数的独立计算公式。 定理3.4.1对于任意的正整数n,有s(1,1)?1, s(n,n)?1,k?n时,s(n,n-k)?(-1)kMkn ,其 ?0??0(n)中Mk是矩阵????0?时,s(n,k)?0 。 01?0?0???0?n-1s(n,1)?(-1)(n-1)! ,k?n的k阶主子式之和.特别地,?????n-1??2定理3.4.2 对于任意的正整数n,有S(n,n)?1,S(n,n-1)?-s(n,n-1)?Cn ,而当1?t?n?1时,?S(n,n?k)s(n?k,n?t)?0 k?0t引理3.4.3 第一类Stirling数满足递归关系 s(0,0)?1,s(n,0)?0? ,(n?0,k?0) 。 ?s(n?1,k)?s(n,k?1)?nS(n,k)1?引理3.4.4 第二类Stirling数满足递归关系 S(0,0)?1,S(n,0)?0? ? , (n?0,k?0)。 ?S(n?1,k)?S(n,k?1)?kS(n,k)定理3.4.5 第一类Stirling数满足s(n,k)???(n?k?i)s(n?k?i,i?1) i?o?7?k?120 沈阳理工大学学士学位论文 定理3.4.6 第二类Stirling数满足S(n,k)??(i?1)S(n?k?i,i?1) i?0?7?k?1定理3.4.7 1?k?n,k??S(n,i)k(k?1)?(k?i?1),即 ni?1?7?kknS(n,1)S(n,2)S(n,k?1)??????S(n,k) k!(k?1)!(k?2)!1!3.5 Stirling数的组合意义及应用 3.5.1 引言 利用概率论的方法系统地研究组合问题,最早由Erdls和Spencer提出。但是,这一方向的研究成果不是很多,而且主要集中在概率论方法在Ramsey理论、随机图、组合优化等方面的应用,以及在经典组合问题中,用Monte Carlo方法处理组合计数的数值解.我们发现,许多组合数及组合多项式,以后称为组合变量,包括Stirling数,Bell数,Bernouli数,分拆数以及Bernouli多项式,Hermite多项式,Bessel多项式,Gegenbauer多项式等都和随机变量的矩有关。同时,符号运算中的伞变量(umbral operator)也与概率论有密切的联系。因此,概率的方法和技巧可以在一些经典组合问题中得到广泛应用。本文只讨论Stirling数,证明两类Stirling数是随机变量和的矩,对于?an,kS(n,k),?an,ks(n,k)类型的组合建立了 nn一个统一的处理方法,我们或者能求出这种和式,或者至少也能得到一个恒等式。组合恒等式中的参数不应当仅仅看成一个常数,而应被视为一个随机变量(常数是随机变量的特例),这样我们就可以从一个简单的恒等式中推导出许多(甚至无穷多个)新的、有趣的恒等式.最后,利用中心极限定理,我们得到了k固定时,S(n,n-k)的渐进形式,它在k?3时与精确公式完全吻合。 3.5.2 预备知识 本文所涉及的概率论知识,其中主要是矩和条件期望的概念。 如果X是一个连续随机变量(下文简记为r.v),它有密度函数f(x),满足 P?a?X?b???f?x?dx,f?x??0,?f?x?dx?1. a-?b?那么,对任何一个Borel可测函数p(x),r.vp?X?的矩定义为 Ep?X???p?x?f?x? (3.4) -??特别地, 1)f(x)?xn时,(3.4)称为r.vX的n阶矩; 2)f(x)?x时,(3.4)称为r.vX的期望; 3)如果X,Y是两个r.v,那么 21 沈阳理工大学学士学位论文 E(XY?y)??xf?x??xY?y?dx,f?x??xY?y? ?-?是X关于事件{Y=y}的条件概率密度。 称为r.vX关于事件{Y=y}的条件期望,它是y的函数,记作μ(y),那么μ(Y)?E(XY)是一个r.v,称为X关于Y的条件期望.我们将使用如下的全数学期望公式: E?Eg(X)Y??Eg(X) 来推导Stirling数的递推关系。 本文中,只涉及到两种常见的的连续r.v 1)均匀分布 r.vX~U[a,b],称为X服从[a,b]上的均匀分布,密度函数为 ?1a?x?b,?,f(x)??b-a 其它.??0,bn?1-an?1. 所以EX?(n?1)(b-a)n2)指数分布 r.vX~e(?),??0,称为X服从参数为?的指数分布,密度函数为 ?λe-?x,x?0 f(x)???0其它所以EXn?n!/λn. 当r.vX与Y独立时,它们乘积的矩等于矩的乘积: E(f(X)g(Y))?E(f(X))E(g(Y)). (3.5) 这个性质在本文中起着重要的作用,此外,我们沿用概率论常用的符号,当一列 r.vX1,X2,?不仅是独立的,而且分布还相同,则记为X1,X2,?,i.i.d. 3.5.3 Stirling数的概率表示 定理3.5.1 如果随机变量V服从二项分布B?n,p?，则它的任意m阶原点矩为 ??S?m,k??n?kpk,m?0 k?0mEVm22 沈阳理工大学学士学位论文 这里S?m,k?是第二类Stirling数,?n?k为降阶乘。 证明 我们定义降阶乘为?x?k?x?x-1???x-k?1?，则第二类Stirling数又常常被定义为： x?n?S?n,k??x?k?0nk (3.6) 注意到降阶乘的定义以及 ?i?k?0,i?k-1;?i?k?i!,i?k, ?i-k?!因此V的降阶乘的数学期望为： E?V?k???i?kCpqinii?0nn-i??i?kni!n!?piqn-i ?i-k?!i!??n-i?!n-k?n-k?!pi-qn!kkn-ip???n?kpk ， ??n-k?!i-?k0?i-k?!?n-?i!把x??S(n,k)(x)k式中的x换为随机变量V再取数学期望，则得证。 nk?0n定理3.5.2 假设r.v序列u1,u2,?,i.i.d~U[0,1],Γ1,Γ2,?,i.i.d~Γ(1),并且r.vui 与Γj独立,则n,k?1时, 1)第一类Stirling数s(n,k) ?kn?n-k? s(n,) (3.7) k?(-1)n-?E(uΓ???uΓ)11kk?k????n-1?n-k s(n,k)?(-1)??k-1??E(u1Γ1???uk-1Γk-1) (3.8) ??n-k规定s(n,0)?s(0,k)?0,s(0,0)?1。 2)第二类Stirling数S(n,k)满足 ?n?n-k? S(n,) (3.9) k??E(u???u)1k?k???23 沈阳理工大学学士学位论文 S(n,k)?1E(Γ1?2Γ2???kΓk)n-k (3.10) (n-k)!?n-1?n-k? (3.11) S(n,k)??E(u???u?1)1k-1?k-1???规定S(n,0)?S(0,n)?0,S(0,0)?1. 证明 这里仅证明2)式(3.9) S?n,k???n??n??n-k??1??1?1???????????? ??'''??????????k!i1'???ik'?n?i1i2?ik?i1???ik?n-k?k??i1i2?ik??i1?1??ik?1?诸ij'?0??n??n-k??n???n-k?i1ikikik?????????Eu?Eu?Eu?ukk? ?k???ii?i?k?k????i?i?1???12k?????1k???????n?n-k??. ??Eu???u1k?k???证毕。 式(3.7)、(3.9)和(3.10)是把两类Stirling数分别表示成某些随机变量和的矩,这种概率表示是对Stirling数的一种构造性描述,从而为研究Stirling提供了新的工具。主要结论如下: 定理3.5.3 第二类Stirling数S(n,k)和第一类Stirling数s(n,k)有以下性质: ?n?(i)S(n,1)?1, S(n,2)?2-1,S(n,n-1)???2??,S(n,n)?1. ??n-1?n?(ii)s(n,1)?(-1)n-1(n-1)!,s(n,2)?(-1)n-2(n-1)!Hn-1,s(n,n-1)?-??2??, ??s(n,n)?1,其中Hn为调和数。 ?n?n-11? 证明 由(3.9)式S?n,1???Eu?n?1,显然S?n,n??1, ?1?1n???n?n-2???S?n,2???Eu?u12?2????n?n-2?n-2?n-2-ii??Eu2 ?2?????i??Eu1??i?1??????1n-2?n??????2n-1-1??2i?0?i?1?24 沈阳理工大学学士学位论文 ?n?n?n-1??n???, ??S?n,n-1???Eu???u???n-1?n-1?1??2???2?由(3.10)式也可以得到相应的值。 由(3.7)式s?n,1???-1?n-1?n?n-1n-1???????n-1?!,显然s?n,n??1, Eu??-1?1?11??n-2?s?n,2???-1???n?n-2???Eu??u?22?11?2?n-1??-1???-1?n-2?n-1?!?1??-1?n-2?n-1?!Hn-1 k?1kn-2?n-1?!Hn-1?n??n?????s?n,n-1???-1??Eu????u??-n-1n-1?n-1?11?2?? ????文献[9]根据引理,运用概率技巧重新得到了有关两类Stirling数的递推公式 S(n,k)?S(n-1,k-1)?kS(n-1,k) 和 s(n,k)?s(n-1,k-1)-(n-1)s(n-1,k). 另外我们还可以重新得到下面的递推公式: 定理3.5.4 S(n,k)??kn-mS(m-1,k-1). m?kn下面简单给出该递推公式的推导过程: 记Sk-1?Γ1?2Γ2???(k-1)Γk-1,由(3.75)式 S(n,k)?1E(Γ1?2Γ2???kΓk)n-k (n-k)!?n-k?n-k?n-k-j1j???E????Sk-1?k?k??j(n-k)!?j?1??????kjj?0n-kn-k11-j-(k-1)ESkn--1?n-k-j?! ??kjS(n-1-j,k-1)j?0n??kn-mS(m-1,k-1)m?k此外我们还可以发现如下一些新的递推公式。 25 沈阳理工大学学士学位论文 定理?15?3.5.5 第二类Stirling数S(n,k)和第一类Stirling数s(n,k)满足下列递推关系: kS(n,k)??n??1) ??m??S(m,k-m?k-1??n-1n-1?n-k?S?n,k?????m-k?1?S?m,k-1???n-m?kn-mS?m-1,k-1?? m?k ks?n,k??n-1m?k-1?n-m-1?????-1n-m-1!??n-2n??s?m,k-1? ??m?n-m??n??n??-1??s?n,k?????n-m??n-m?!??m-1??s?n-1,k-1?-?m-k?1??n-m-1?!??m??s?m,k-1?? ??kn-km?k??????3.5.4 渐进与估计 这一节我们利用概率论的技巧给出两类Stirling数的估计,首先介绍一个概率不等式. Minkowski 不等式 如果EXpp??,EYp1p??,1?p??,则 p1p{EX?Y}?{EX}?{EY}p1p 定理3.5.5 当n,k?1, (-1)n-ks(n,k)?(n-1)!S(n,k) (k-1)!kn-k证明 当?1,?2,?,i.i.d~??1?时,r.v?1??2????k的密度函数为 f?x??1xk-1e-x,x?0. ?k-1?!所以 E??1????k??k?k?1???k?r-1??r?k?r-1?!. ?k-1?!因为r.vui与?j的独立性,由定理(3.5.2), E?u1???uk??n-k??1???k?n-k? ?n-1?!?n???k???k-1?!??S?n,k?. ????1n-k??n?n-k??????E??1???k????Eu???u??k?1??n????k???????k????????而由Minkowski不等式 26 沈阳理工大学学士学位论文 E?u1???uk??n-k??1???k?n-k? n-k?E??u1?1???uk?k???u1?2???uk?1???u1?3???uk?2?????u1?k??uk?k-1?? ?n-k??E?u1?1???uk?k????1n-k?E?u1?2???uk?1??1n-kn-k???E?u1?k???uk?k-1??1n-kn-k????n-k ?????????1n-k???k-1?s?n,k????n??????k????????????即?-1?n-k1n-k?????????n-kkn-k?-1?n-ks?n,k?, ??n???k????s?n,k???n-1?!S?n,k?. ?k-1?!kn-k利用定理3.5.2和中心极限定理,我们还能得到当k固定时,S?n,n-k?的渐近行式,为方便记,我们把S?n,n-k?化为S?n?k,n?的形式。 定理?9?3.5.6 任给固定的k?1,当n??时, (n?k)!?n?k1?S(n?k,n)~???2??(k-2nl)!l!(6n)l. n!??l?03.5.5 Stirling数的组合意义 1)由k个轮换构成的n阶置换的个数为s(n,k)。 2)恰可表示成k个互不相交的轮换乘积的n元置换共有(-1)n?1s(n,k)个。 3)把n件相异物分别放到k个相同盒中使得无一盒空的不同放法共有S(n,k)种。 ?k?1k?1n?4)把n元集划分成k个非空子集的方法数为S(n,k)??(?1)j?。 (k?j)??k!j?0?j?5)n元集无序拆分为k个非空子集的方法数为S(n,k)。 6) ①n个不同球,放入m个相同的盒中,盒非空,其放法数为S(n,m)。 ②n个不同球,放入m个不同的盒中,盒非空,其放法数为m!S(n,m)。 27 沈阳理工大学学士学位论文 4 其他几种常见的组合数 4.1 Fine数 4.1.1引言 由于Fine数和格路有着紧密的联系,所以在介紹Fine数之前,我们先来简单了解一些格路的相关知识。 在平面直角坐标系中,横坐标和纵坐标都为整数的点称为平面格点,平面格路径是指在所有的平面格点中,从一点到另一点走格点的路,格路径的长度是指其所走的路的步数。我们这里研究的都是平面格路径,下面都简称为路径。一条长度为n的格路径也可以看做一个n维的向量v??v1,v2,?,vn?,这里vi?Z2,vi?1-vi表示这条路径所走的步法之一。 格路径是组合数学中非常重要的一个概念,因而有关格路径的研究在组合数学中一直占据着非常重要的位置,这是由于格路径不仅可以作为重要的模型来描述其他的组合统计量,像树,有禁排列,正交多项式,连分式等,也可以作为证明组合恒等式的重要工具,并且还在其他数学分支比如概率论,统计学,随机过程等有着广泛的应用.另外,格路径与生物信息学也有着很密切的联系。 在计数组合数学的研究中,对格路径所走的步作不同的限制即得到不同类型的格路径。格路计数只要是研究这些不同类型的格路的数目和性质。Dyck格路是其中最典型的一类格路径,它与计数组合数学中的很多经典的序列有着很密切的联系, 下面我们先来介绍以下什么叫Dyck格路。 4.1.2 Dyck格路与Catalan数 定义4.1.1 一条2n长的Dyck格路是指在Z2中,从原点(0,0)出发到(2n,0),由(1,1)方向的上升步和(1,-1)方向的下降步组成的,始终在x轴上方的一条路径.从(0,0)出发到(2n,0)的Dyck格路记做n-Dyck格路。 为了更好地理解定义,我们画出n=2和n=3时所有的Dyck格路 28 沈阳理工大学学士学位论文 图4.1两条长为4的Dyck格路 图4.2 五条长为6的Dyck格路 我们把长度为2n的Dyck格路的集合记做Cn。Cn是由Catalan数来计数的,Catalan数的初值是1,1,2,5,14,42,132,429,1430,4862,…,并且Catalan数C0,C1…满足西面的递归关系式: 命题4.1.2 Cn??CiCn-1-i,其中C0?1 i?0n-1 命题4.1.3 C?x??1?xC2?x??1-1-4x 2x命题4.1.4 Cn?1?2n??? ??n?1?n?4.1.3 Fine数的基本性质和概念 本文主要研究Fine数的相关知识,在前面我们提到了Catalan数,对Catalan数有了一定的了解后,下面我们就来讨论Fine数的定义及其相关的性质。 定义4.15 在Z2中,一条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格路 29 沈阳理工大学学士学位论文 图4.3一条长度为4的Fine格路 4.4两条长度为6的Fine格路 4.5 五条长度为8的Fine格路 在这篇文章中,我们用u来表示上升步,用d来表示下降步。在一条格路中一对连续的ud步叫做峰,一个峰中所包含的d步叫做fall。格点指的是每一步的两个端点,我们把峰所包含的ud步中所有格点的纵坐标的最大值叫做峰的高度,一条格路的高度是所有峰的高度的最大值。 我们把长度为2n的Fine格路的集合记做Γn。Γn是由Fine数Fn来计数,Fine数的初值是1,0,1,2,6,18,57,186,622,2120,…,Fine数{Fn}n?0的发生函数记做F(x),即 F(x)??Fnxn。Fine数的发生函数和Catalan数的发生函数之间满足如下关系: n?0?命题4.16 F(x)?1?x(C(x)-1)F(x)?11-1-4x x3-1-4x命题4.17 Fine数和Catalan数满足关系式:Cn?2Fn?Fn-1 4.1.4 Fine数的几个重要的恒等式 根据Fine数和Catalan数之间的关系,我们得到Fine数的若干性质如下: 性质1 2(n+1)Fn=(7n-5)Fn-1+2(2n-1)Fn-2 30 沈阳理工大学学士学位论文 性质2 Fn?1?2n-2?2?2n-4?3?2n-6???????????,其中n?2 ??????n-1?n?n-2?n?n-3?n?1?11?n-21C-C?C-??(-1)Cnn-1n-22? 2n-22?222??性质3 Fn?性质4 Fn4~ Cn94.1.5 Fine数的组合意义 Fine数有很多组合解释,它和一些重要的组合对象,比如它和Dyck格路,Young表,分拆,平面树,Motzkin格路有比较紧密的联系。Deutsch和Shapiro在文献[17]中给出Fine数的一些组合解释,我们首先给出一个重要引理,下面的很多证明都是以此引理为基础。 引理1 如果Dyck格路中第一峰的高度是k,那么它的发生函数是xkCk(x)。 性质2 从左向右看,满足第一个峰的高度是偶数的长度为2n的Dyck的格路计数是Fn。 k性质3 具有型(n,n)且每列不出现形式的标准Young表的计数为Fn。 k?1性质4 [n]的第一个块的长度是偶数的不变划分的计数是Fn。 性质 5 [n]的不包含可视的单点的不变划分的计数是Fn。 性质 6 n个结点的有序树中第一层上不包含叶子的有序树的计数是Fn-1。 性质 7 长度为n的2-Motzkin格路中x轴不包含水平步的计数是Fn。 4.2 Pólya计数 4.2.1 Pólya计数产生的历史 G·Pólya是美籍匈牙利数学家、教育家。他在数学的广泛领域里都有许多发现,又热心于教育,1980年被邀请担任第四次国际数学教育会议的名誉主席。他一生中发表过二百多篇论文和许多专著,其作品清晰优美,方法灵巧独特。被人们誉为“Pólya的风格”、 “Pólya的方法”……。 Pólya早在1937年就对树的计数和化合物的同分异构体的枚举问题进行研究,他巧妙地把发生函数、置换群和权函数三者结合起来,设计出一个枚举多项式,揭示了构形计数级数与构形群的循环指标和图形计数级数的关系,解决了许多计数问题。人们把这一方法叫做Pólya计数定理。之后, Pólya基本定理又有许多种推广形式,都有极为广泛的实际应用。 31 沈阳理工大学学士学位论文 4.2.2预备知识 我们参照Pólya原来的说法,把给定的两个有限集合D和R分别叫位置集和图形集。如d?D就说有位置d,称r?R是图形r。D到R的一个映射f叫做一个构形,由所有定义在D上取值于R中的构形作为一个集合叫构形集,并记作RD。若D是n元集,R是m元集,则有D=n,R=m,RD=mn。 把作用在n元集D上的一个n次置换群G叫做D的一个构形群。G中每一个置换g均可表为没有共同元的循环置换之积,若其中有b1个长度为1的循环,b2长度为2的循环等等,且b1?2b2?3b3???n,则说g是{b1,b2,b3?}型的,并令 PG(x1,x2,?xn)?1Gg?G?xb1xbnb2x2?xn 称为置换群G的循环指标。 我们说两个构形等价f1~f2,当且仅当存在一g?G,是对每个d?D有 f1(d)?f2(g(d))。又把构形集的每一等价类叫做一个构形格式。 给R的每个图形r指定一个权w,取值为k维空间的非负整数,记作 w(r)?(w1(r),w2(r),?,w(r) 同样地指定一个构形f的权为 w2(f(d))W(f)??x1w1(f(d))x2?xkwk(f(d)) d?D其中x1,x2,?,xk为形式参量。 若R中权等于(i1,i2,?,ik)的图形有hi1i2?ik个,令 iki1i2 h(x1,x2,?,xk)??hi1i2?ikx1x2?xk称为图形计数级数。 iki1i2若RD中权等于x1的构形格式有Hi1i2?ik个,令 x2?xki1i2ik H(x1,x2,?,xk)??Hi1i1?ikx1x2?xk称为构形计数级数。 令 O(x)??yg(x)?y,x,y?D,g?G? 称为x的稳定核。易知G(x)是G的一个子群。 引理4.2.1 G?O(x)?G(x) 引理4.2.2 一个构形格式F中的诸构形有相同的权。 引理4.2.3(Bursibe定理) 若λ1(g)是置换g?G的1-循环的个数,也就是n元素D中 32 沈阳理工大学学士学位论文 被置换g不变的元的个数,则构形群G的轨道个数为 ?O(x)?而关于轨的权和为 1Gg?G?λ(g) 1?W?Oi??_1Gg?Gfg?f??W?f? 引理4.2.4 构形f在置换g下不变,当且仅当f在g的每个循环的所有元上取值相同。 4.2.3 Pólya计数定理 构形计数级数H(x1,x2,?,xk)可以由图形计数级数h(x1,x2,?,xk)代入到构形群G的 循环指标中去而得到,即 22nn H(x1,x2,?,xk)?PG[h(x1,x2,?,xk],h(x12,x2,?,xk),…,h(x1n,x2,?,xk)] (4.1) b1b2bn1Pólya计数定理:?W(F)?GFn?????2?W(r)[W(r)]?[W(r)]?????? ????g?G?r?R??r?R??r?R? ?PG[?W(r),?[W(r)]2,?,?[W(r)]n] (4.2) r?Rr?Rr?R4.2.4 Pólya计数的例子与性质 例1 设D为全等三角形ABC的顶点集,R为红、白两种颜色之集。G为三次交错群A3={(A),(ABC),(ACB)} 。 若每个顶点都涂上R的一种颜色,试求对A3不变的着色格式的个数。 首先指定红、白两种颜色的权为x、y,那么图形计数级数为h(x1,x2)?x?y。易知构 1形群A3的循环指标是PA3(x1,x2,x3)?(x13?2x3),再把图形计数级数代入上述群指标,得 3到构形计数级数: H(x1,x2,x3)?PA3(?W(r)),?[W(r)]3) r?Rr?R1 =((x?y)3?2(x3?y3)) 3 1 =(x3?3x2y?3xy2?y3?2x3?2y3) 3 =x3?x2y?xy2?y3 故着色格式有4种:x3,x2y,xy2,y3 。 其次,若指定两种颜色的权均为1,则图形计数级数是2,于是构形计数级为 33 沈阳理工大学学士学位论文 1H(x1,x2,x3)?PA3(2,2)?(23?2?2)?4 3分析:指定权的第一种方法对构形计数级数的计算较频繁,但结果能证明每个格式的结构;第二种方法计算较简单,但未能表明格式结构。因此,应视具体要求来选择适当的方法。 容易得到如下推论: 1)设D?{1,2,?,n},R?{a1,a2,?,am},G为构形群,则构形计数级数之数值为 H(x1,x2,?,xn)?PG(m,m,?,m) 2)试求用图形ai恰好ki次(i=1,2,…,m)的构形格式F的个数则是(4.2)式展开式中 km的系数。 W1k1W2k2?Wm例2 设D?{1,2,3},R?{0,1},G?{(1),(23)},那么构形集RD就是所有的三位二进制 数:001,010,011,100,101,110,111,“1”000。易知 1PG?(x13?x1x2)。我们指定0,1的权为x,y,则h(x1,x2)?x?y,代入 21H(x1,x2,x3)?PG[(x?y),(x2?y2)]?[(x?y)3?(x?y)(x2?y2)] 2 ?x3?2x2y?2xy2?y3 由此可见,这里6种格式,不同的格式有相同的权如x2y或xy2。现在的问题是如何具体地写出这些不同的格式呢? 首先,注意到构形群G是由置换(23)生成的循环群,我们利用g?(1)(23)作RD的一个置换g?(1)(2,4)(3,5)(6)(7)(8)其中g满足g(f)?fg。由此得到对G的构形格式与相应的G的生成置换g每一个循环相重合。于是有:001,010,011,110,111,000。容易看出在对换(2,4)和(3,5)里两个三位二进制数对G来说是等价的。因此只要选取一个作代表即可。 同样,对例1中的G是由置换(123)生成的,那么作RD上的相应置换得(124)(365)(7)(8) 。据此4个循环便有如下4种构形格式:001,011,111,000。因此,获得一个性质: 若构形群G是一个由置换g生成的循环群,则对G的构形格式,可由g在G里的相应置换g:g(f)?fg的每个循环里选取一个构形来作一种格式。 例3 设D为一个正四面体的顶点集合,R为红、白两种颜色的集合,G为正四面体的旋转群,试求每个顶点都涂上R的一种颜色的格式的个数。 解 设D={1,2,3,4},R={0,1},而G的元是:(1),(123)(4),(132)(4), ________34 沈阳理工大学学士学位论文 (124)(3),(142)(3),(134)(2),(143)(2),(234)(1),(243)(1),(12)(34),(13)(24),(14)(23). RD:0001,0010,0011,0100,0101,0110,0111,1000,1001,1010,1011,1100,1101,11 10,1111,“1”0000。 利用G的元g作R置换g:g(f)?fg,得: (1)(2)(3)(4)(5)(6)(7)(8)(9)(10)(11)(12)(13)(14)(15)(16); (1,2,4)(3,6,5)(7)(8)(9,10,12)(11,14,13)(15)(16); (1,4,2)(3,5,6)(7)(8)(9,12,10)(11,13,14)(15)(16); (1,4,8)(2)(3,6,10)(5,12,9)(7,14,11)(13)(15)(16); (184)(2)(3,10,6)(5,9,12)(7,11,14)(13)(15)(16); (1)(2,4,8)(3,5,9)(6,12,10)(7,13,11)(14)(15)(16); (1)(2,8,4)(3,9,5)(6,10,12)(7,11,13)(14)(15)(16); (1,2)(3)(4,8)(5,10)(6,9)(7,11)(12)(13,14)(15)(16); (1,4)(2,8)(3,12)(5)(6,9)(10)(11,14)(13,7)(15)(16); (1,8)(2,4)(3,12)(5,10)(6)(7,14)(9)(11,13)(15)(16); (1,2,8)(3,10,9)(4)(5,6,12)(7,14,13)(11)(15)(16); (1,8,2)(3,9,10)(4)(5,12,6)(7,13,14)(11)(15)(16); 由推论易求得5种构形格式:0001,1110,0011,1111,0000。 特别地,这里有三个颇有趣的性质: 1)四位二进制数构形集合对于逻辑加(不进位)运算做成一个群。 2)四位二进制数构形集对于由四次置换群G引入的一个同构的置换群G来说,g中每个k>1循环的全部二进制数的逻辑和恰等于它的某一个1一循环的二进制数。 3)在g里的全部1-循环的二进制数集对逻辑加运算来说作成一个群。 6,5)(7)(8)(9,10,12)(11,14,13)(15)(16) 例如g(123)(4)?(1,2,4)(3,__D____中有:1?2?4=7,3?6?5=0,9?10?12=15,11?14?13=8.注意把这些数转化为二进制数. 0 0 0 1 0 0 1 1 1 0 0 1 1 0 1 1 0 0 1 0 0 1 1 0 1 0 1 0 1 1 1 0 ?0 1 0 0 ?0 1 0 1 ?1 1 0 0 ?1 1 0 1 0 1 1 1 0 0 0 0 1 1 1 1 1 0 0 0 35 沈阳理工大学学士学位论文 <{0111,1000,1111,0000},?>显然是一个群。因为0000是单位元,其余三个元都是以自身为逆元。 易知,对n位二进制数的构形集也具有此类性质,这也与循环字编码等有关。 36 沈阳理工大学学士学位论文 5 总 结 组合数学是一门古老的学科。公元1666年,天才数学家、计算机先驱莱布尼茨为它起名为“组合学”(Combinatorics),并预言了这一数学分支的诞生。如今,组合数学的思想和技巧不仅影响着数学的许多分支,而且广泛地应用于自然、社会的几乎所有科学领域。 本文开篇绪论部分着重介绍了组合数学的研究背景和意义,展现了组合数学在科学以及生活中的各个领域的重要应用价值。其中论文主体部分主要介绍了组合数学中常见的计数方法,例如Catalan数、第一类、第二类Stirling数、Fine数和Pólya以及最近刚出现不久的格路计数。在第二章,从明安图与Catalan数的发展历史讲起,通过Catalan数的起源,给出了Catalan数列的定义和推导过程,并归纳了Catalan数的若干性质,最后举例说明Catalan数在售票问题、城市线路问题和唱票选举问题在生活实际中的应用。在第三章,和Catalan数一样,开始介绍了Stirling的起源、定义和性质,由于Stirling数和概率论知识联系紧密,所以后面应用部分结合概率论有关知识,重点介绍了Stirling数在组合恒等式证明和定理证明方面的应用。在第四章,重点介绍了两类比较常见的组合数,即Fine数和Pólya计数定理。在Fine数一部分,引进了格路径的概念,以Dyck格路的形式给出了Fine数的定义,最后根据Catalan数和Fine数之间的关系,总结了Fine数的若干性质并例了举Fine数的一些组合解释。在Pólya计数一部分,通过数学中有关群的知识引出Pólya定理,最后简单举例说明Pólya定理在组合计算中的简单应用。 组合数学发展至今,已有很多计数方法,由于篇幅有限,本文仅仅简单介绍了几种常见的组合数,涉及的也都是一些简单的应用问题。随着计算机的不断发展,组合数学在计算机应用方面已经占有十分重要的地位,相信在不久的将来,组合数学必将在这一新的领域中独占鳌头。 37 沈阳理工大学学士学位论文 致 谢 在论文完成之际,首先由衷感谢我的导师段红玲老师,在这段时间里,论文从选题到定稿,都是在恩师的悉心指导下完成的,我所取得每一点成绩都凝聚着恩师的心血和汗水。恩师严谨认真的治学态度、渊博的知识和正直的人格,已经深深地铭刻在我的心中,它不仅激励着我在沈阳理工大学的生活,而且将会贯注到我今后的工作和做人中,使我终身受益。在此毕业之际,向段老师表示衷心的感谢和崇高的敬意! 同时对王老师、刘老师给予我的帮助和指导表示深深的感谢!也很感谢王俊杰老师、许可老师对我学习上的帮助。 在做论文的过程中,王明远同学给予了我许多帮助,在此对他表示衷心感谢! 感谢我的亲人,是他们给了我经济上的支助和生活上的关心,才使我静下心来学习,在我成长的道路上他们付出了最博大无私的爱!我在这里向他们真心地道声:谢谢! 在我漫长的求学道路上,很多老师、同学和朋友一直在关心我和支持我,才使我顺利完成学业,借此机会,向所有关心和支持我的人致以最诚挚的谢意! 最后,向各位参考文献的作者表示感谢。 38 沈阳理工大学学士学位论文 参考文献 [1]刘芹英.经典Catalan数的组合背景[J].西北大学学报(自然科学版).2003,33(1):1-3 [2]殷剑宏. 组合数学.机械工业出版社[M].2006:98-100 [3]王丰效,傅丽.关于Catalan数的几种求法[J].陕西工学院学报.2000,16(1):1-3 [4]赵仓梅.Fine格路和有禁错排[D].大连理工大学,硕士.2006:4-17 [5]徐道.售票问题与Catalan数[J].抚州师专学报.1999,(3):1-2 [6]于应龙.数学探究性学习导读[M].上海出版社.2002:22-25 [7]王红,杨雅琴,王艳辉.第一类Stirling数和第二类Stirling数的关系式[J].高师理科 学刊.2008,28(6):1-3 [8]张建国.第二类Stirling数的两个计算公式[J].商丘职业技术学院报.2002,1(3):1-2 [9]孙平,王天明.Stirling数的概率表示和应用[J].数学学报.1998,41(2):1-9 [10]邓记养.Polya计数定理及其若干性质[J].韶关师专学报.1987,(2):4-7 [11](美)Richard A.Brualdi.组合数学[M].冯顺玺,罗平,裴伟东.第三版.机械工业出版 社.2001:179-187 [12](美)William Feller.概率论及其应用[M].胡迪鹤.第三版.人民邮电出版 社.2006:52-56 [13] RO GER EGGL ETON,RICHARD GUY.The Mean-ing of Catalan Numbers[J].Mathematics Magazine,1988,(10):1-4 [14]L.Carlitz.Degenerate Stirling,Bernoulli and Eulerian numbers[J].Utilitas Math,15:51-88.1979 [15]毛俊超.概率方法在组合数学中的应用[D].中国海洋大学,硕士.2007:21-23 [16]Yuan Shih Chow,Henry Teicer.Probability Theory[M],Second Edition.New York:Springer-Verlag,1988:33-35 [17]Deutsch E,Shapiro L.A survey of the Fine number[M].Discrete Math.,2001,241:241-265 [18]康庆德.组合学笔记[M].科学出版社.2009:65-67 39 沈阳理工大学学士学位论文 附录A 英文原文 Combinatorial Mathematics Analyses Combinatorial mathematics, also known as discrete mathematics, is the study of the science of discrete objects. Combinatorial mathematics is the computers after appearing rapidly develop a branch of mathematics, along with the development of computer science, combinatorial mathematics the importance of increasingly prominent. The electronic computer process information is only use \or is the code in this digital information. So the processing of discrete objects became the core of computer science, and combinatorial mathematics is the study of the science of discrete objects. Modern mathematics research content mainly includes two aspects: on the one hand, it is the object of continuous research, such as analysis, algebra, etc, on the other hand, is the study of the discrete objects combination mathematics. Combinatorial mathematics research accord with certain condition configuration object, counting and structure, etc. Discrete configuration problems are the combination of mathematics research content, mainly including: (1) the existence of the configuration; (2) the structure of the configuration of sexual problems; (3) the count of configuration; (4) the configuration optimization problem. In 1666, the combination of art, \the milestone, in the next three hundred years, combinatorial mathematics has made rapid development, especially since the 1940 s, the wide application of electronic computers to combinatorial mathematics has had a huge impact, combinatorial mathematics and computer science in combination won the broad space for development, and also for computer science laid a theoretical foundation. Combinatorial mathematics not only computer technology in network optimization, coding and cryptography has an important application value, in the enterprise management, traffic laws row, financial analysis, etc all have important applications. In the 2 l century, combinatorial mathematics will close with computer science to move forward, ZuGeLun skills will be computerized, and the solution for all the important 40 沈阳理工大学学士学位论文 part of the machine. 1 Combinatorial Mathematics Problems in Classic The classic of combinatorial mathematics problems include: (1) perfect cover board; (2) the cutting cube; Magic square (3); Four color (4); (5) problems 36 officer; 6 the shortest path; 7 NIM take son problem; 8) sheep Wolf food across the river; 9) China the postman problem; ⑩ stable marriage problems. The following key introduced four color problem and China the postman problem. More than a century, the study of four color proof process, because the object complex and lack of mathematics usually work standards, artificial direct verification is not workable. In the 70 s. The electronic computer the rapid development and application of four color make the research appeared turnaround. The university of Illinois upper, hawking in various ways to prove the former research and the ideas of foundation, since 1972, started with the computer four color proof of research work. Finally in 1976 thoroughly solved the problem of four colors, the whole process in computer proof spent 1200 hours. Four color map problem is the first mainly by the computer to complete the proof of the math problems. Scientists in the study and solve the problems of four color, also from which many new mathematical theory, the development of the many mathematics calculation method, stimulate the topology and graph theory development. 1.1 Four-color problem Four-color problem using four different colors on the world map coloring. Requirements of the color of the neighboring countries are different. The use of mathematical language is formally described as follows: a plane arbitrarily subdivided into area not overlap, each region can always be 1, 2, 3, 4, 4 one of the digital tag, but not accounted for on the question the two regions adjacent to make the same number. More than a century, studies have shown that four-color problem, because the object 41 沈阳理工大学学士学位论文 complexity of the problem and the lack of the usual mathematical problem solving norms, artificial direct verification is not feasible. The 1970s. The rapid development and wide application of the computer so that the four-color problem of a turning point. Appel, Haken of the University of Illinois in the basis of the previous kinds of proof methods and ideas, since 1972, and began research work with a computer to prove the four color problem. In 1976, completely solve the four-color problem, the entire certification process has spent 1200 hours on the computer. Map of four-color problem is the first major completion certificate by the computer mathematical problems. Scientists in research and solve the problem of four-color process, but also the resulting number of new mathematical theory, development of mathematical methods to stimulate the development of topology and graph theory. 1.2 China the Postman Problem A postman work is: according to certain route he is responsible for delivering the block of the street every E-mail, and back to the post office, ask the postman must cross the street he is responsible for every street is at least once, and hope to choose a total distance of the shortest delivery routes. Looking for such a shortest delivery route, issues in the international academic community called China the postman problem, because it is sponsored by China in 1962 GuanMei mathematician operator’s professor, first proposed and studied. 1.21 Euler circuit problem Theorem of l connected graph G (V, E), including V said in the chart the node set, E said edge set, then the following conditions are mutually equivalent: (1) G is a European pulling the; (2) the G each node is the even degree; (3) the edge of G can be decomposed into several set E circuit and. 1.2.2 The solution of the Euler circuit 42 沈阳理工大学学士学位论文 Cycle of find the starting point. A node from the start, and then find out a starting from the back to the point of ring path. This method to ensure that every edge are traverse. If there is a point of edge is not traverse let this point as a starting point, this side for start edge, and the current ring cohesion. So until all the edge were traverses. That way, the whole figure will be connected together. Theorem 2 connected to existing eular circuit diagram is the necessary and sufficient conditions for the foot of any node, entering the city at the number (into several) and out the side of the point number (three-dimensional) are equal. 1.2.3 Postman Problem Solving Use of the graph theory of language, save a connected empowerment nets G (V, E), to find a loop, and makes the circuit contains G towel at least once each side, and the weight of the circuit smallest. That is to contain the G each from the edge of the loop to find a minimum weight of the Internet. If G is euler figure, if the figure that Europe has a loop, the you for the \loop all, so any a eular circuit for this problem is the solution, it is very easy to described in section 1.1.2 by luo lai algorithm for the Florida a eular circuit for, but if the G not euler figure, there is a strange degree. Node, then China the postman to the solution of the problem to much more difficult. Interested readers can as reference. 2 Computer Science and Combinatorial Mathematics Along with the juice the further development of the computer technology, especially the widespread use of computer network, the use of computers has been deeply to scientific research and People's Daily life in all areas. The computer to do more intelligent to development, its way out is still the algorithm of mathematics and math mechanization. Algorithm of computer science research is an important research field, combination mathematicians in the early 1970 s established algorithm complexity theory of computer 43 沈阳理工大学学士学位论文 algorithm for NP in research on the complexity of the important theoretical foundation to provide. Combinatorial mathematics is the computer industry. Development of high level software products without combinatorial mathematics. Combinatorial mathematics in the week has been a very important subject, even is the foundation of computer science, this computer science authorities many is the research combinatorial mathematics was born. The United States and India in the software industry is a world leading position, and the two countries in the basic math. Especially the combinatorial mathematics talents reserves inseparable, but still have a man in China to combinatorial mathematics understanding is not enough, think combinatorial mathematics is just a kind of pure fundamental subject, practical significance to economic development is not big, but the actual situation of the software industry, network algorithms and analysis, information compression, network security, coding technology, system software is inseparable from the combinatorial mathematics theory and method of the support. With the basic mathematics for the study on the basic theory of the development of the software industry in our country has become a bottleneck, China to want to can become a software superpower, we need to strengthen the combinatorial mathematics teaching and personnel training, etc. research organization, and founded the first combination mathematics in China international journal annual combination \In addition, Tsinghua University, China University of science and technology, Tongji University, key university also established the key laboratory research combinatorial mathematics. In short, in recent years, China's combination mathematics basic research work by the university and the masses of scientific workers more and more attention, especially in university students' mathematical modeling competition between the carry out activities, improve the students' computer technology with the ability to solve practical problems, also greatly stimulate the students' mathematics knowledge of combination of demand, motivated the combination of learning mathematics boom. 3 Conclusions With the popularity of computer promotion, combinatorial mathematics this of the oldest 44 沈阳理工大学学士学位论文 subjects glow vigorous vitality. Combinatorial mathematics is the study of the rich content, application widespread discipline. It is also a method, pay attention to skills subject. Combinatorial mathematics power lies in a combination of mathematical problems can get perfect solution often depends on whether we can find ingenious solutions, computer powerful computing power to seek for the combinatorial mathematics problems clever solution provides the infinite possible, at the same time, combinatorial mathematics in turn effectively promoted the development of the computer science. 45 沈阳理工大学学士学位论文 附录B 中文翻译 浅析组合数学 组合数学,又称为离散数学，是一门研究离散对象的科学。组合数学是计算机出现以后迅速发展起来的一门数学分支，随着计算机科学的日益发展，组合数学的重要性也日渐凸显。电子计算机处理的信息，都是仅用“0”与“1”两个简单数字表示的信息,或者是用这种数字进行了编码的信息。所以离散对象的处理就成了计算机科学的核心，而组合数学是一门研究离散对象的科学。现代数学的研究内容主要包括两个方面：一方面类是研究连续对象的，如分析、代数等，另一方面就是研究离散对象的组合数学。 组合数学主要研究符合一定条件的组态对象、计数及构造等方面的问题。离散构形问题是组合数学的主要研究内容，主要包括：①构形的存在性问题；②构形的构造性问题；③构形的计数问题；④构形的最优化问题。 1666年，《组合艺术》一书是组合数学发展史上的里程碑，在此后的三百多年里，组合数学取得了快速发展，特别是20世纪40年代以来，电子计算机的广泛应用对组合数学产生了巨大影响，组合数学在与计算机科学相结合中获得了广阔的发展空间，从而也 为计算机科学奠定了理论基础。组合数学不仅计算机技术中的网络优化、编码和密码学中有重要的应用价值，在企业管理、交通规 划、金融分析等领域都有重要的应用。在2l世纪，组合数学将会紧密的伴随着计算机科学向前发展，组合论技巧将会计算机化，进而成为各种解算机的重要组成部分。 1组合数学中经典问题 组合数学中的经典问题[6-9]主要包括：①棋盘完美覆盖；②切割立方体；③幻方；④四色问题；⑤36军官问题；⑥最短路径；⑦NIM 取子问题；⑧羊狼菜过河问题；⑨中国邮递员问题；⑩稳定婚姻问题。以下重点介绍四色问题和中国邮递员问题。 1.1四色问题 四色问题即使用四种不同的颜色对世界地图着色。要求相邻国家的颜色相异。采用数学语占对本问题进行形式化描述如下：将平面任意地细分为不相重迭的区域，每一个区域总可以用1，2，3，4这4个数字之一来标记，而不会使相邻的两个区域得到相同的数字。 一个多世纪以来，在四色问题的研究证明过程中，由于对象问题复杂且缺乏数学通常的解题规范，人工直接验证不可行。本世纪70年代．电子计算机的迅速发展和广泛应用使四色问题的研究出现了转机。美国伊利诺斯大学的阿佩尔、哈肯等人在研究了前人各种证明方法和思想的基础后，从1972年起，开始了用计算机证明四色问题的研究工作。终于在1976年彻底解决了四色问题， 整个证明过程在计算机上花费了1200个小时。地图四色问题是第一个主要由计算机完成证明的数学难题。科学家们在研究和解决四色问题的过程中，还由此产生不少新的数学理论，发展了很多数学计算方法，刺激了拓扑学与图论的发展。 1.2中国邮递员问题 一个邮递员的工作是：按一定路线递送他所负责的街区的各条街道的邮件，最后返回邮局，要求邮递员必须走过他负责的街区的每一条街道至少一次，并希望选择一条总 46