沈阳理工大学学士学位论文
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