经典Catalan数的组合背景.pdf

《经典Catalan数的组合背景.pdf》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、2003年2月西北大学学报(自然科学版)Feb.2003第33卷第1期JournalofNorthwestUniversity(NaturalScienceEdition)Vol.33No.1经典Catalan数的组合背景刘芹英(西北大学数学与科学史研究中心,陕西西安710069)摘要:探讨了经典Catalan数在东、西方发现的年代和历史,特别介绍了中国清代数学家明安图(1692?—1763?)在17世纪30年代对Catalan数的首创性工作和应用。列出30种Catalan数的有关公式、组合模型

2、或应用实例,并简要阐明其组合意义。关键词:组合计数;Catalan数;明安图;L.Euler;E.C.Catalan中图分类号:O11文献标识码:A文章编号:10002274Ò(2003)0120121204Catalan数:1,1,2,5,14,42,132,⋯是组合数学中应用广泛的重要计数函数,本文记作Cn。比利时1经典Catalan数的产生数学家E.C.Catalan(1814—1894),在1838年发表[1]的一篇论文中讨论了尔后所称的Catalan问题:n1.1Newton二项式定理

3、∞个不同因子间连续作乘法,如何确定不同的求积方1ö2AK(1+z)=∑(z=法数?他获得Catalan数的计数公式:K=0k2n∞1k-1Cn=,(n≥0)。(1)(-1)kn+1n1+∑2k-1Ck-1Z(ûzû<1)。(2)K=12它表示算术三角形“中垂线”上的数递次除以自然数当指数A=1ö2时,Newton二项式定理展开式必然后所得的数列。可以表示成Catalan数作系数的幂级数(推导过程现代组合学对Catalan数的深入研究,发现了从略)。但是,Newton并没有把系数写成Catalan

4、数许多具有组合意义的应用实例,有人估计不少于50的形式。种。它们散见于各种文献之中,网上查询,有人列出1.2明安图是Catalan数的首创者[2]16种,颇为有趣的是令人联想到能否不断补充,最早发现Catalan数的是我国清代数学家明安使之臻于完备。图。17世纪30年代他在研究无穷级数时得到该数其中,特别是许多西方数学家不了解中国历史的3种算法,并多次将它应用于运算之中。其中,两上对Catalan数的研究成果,清代数学家明安图(约种算法公式是现今组合数学书籍、论文中都未知的。[3]1692?—1

5、763?)是Catalan数的首创者,现在已他的有关成果详载于遗著《割圆密率捷法》[6]中,由[4,5]逐步被国内外数学界承认。明安图之后,还有几后人整理出版[7]。位清代数学家对此也有研究,均在1838年之前,大Catalan数的卷积型递推公式多鲜为人知。囿于所见,本文在有限的范围内搜集相n-1关材料Cn=∑Cn-kCk,(n≥2)。(3),重点在介绍和阐明中国数学家的成果,共获k=1得与Catalan数有关的公式、组合模型和应用实例明安图在计算无穷级数时首先发现了这一规30种。当然,这还是不

6、够的,也可能有理解或翻译方律,并在计算中两次运用。面的不足,还需要感兴趣的学者给予指导和进一步明安图一项重要的工作是获得了Catalan数的补充。组合递推公式收稿日期:2002205221基金项目:国家自然科学数学天元基金资助项目(2000)作者简介:刘芹英(19632),女,河南安阳人,西北大学博士生,从事中国数学史研究。—122—西北大学学报(自然科学版)第33卷∞n-kk2n+3Cn+1=∑(-1)(Cn-k,(n≥2)。∑(16Cn-2Cn+1)sinA。(7)k≥0k+1n=1[10]

7、(3)Larcombe已把上述结果推广到2kA的情况。初始条件是C1=1,C2=1。此式为世界首创,1.3L.Euler(1707—1783)的创造性工作区别于西方在历史上和现代求Catalan数的所有方用n-1条不相交的对角线将一个凸n+2边法。除了他的算法之外,迄今没有现代的证明。式(3)形分割为n个三角形的方法数为Cn。由于此例在几当n≤5时有C2=C1=1,何或组合数学中经常遇到,具有典型性,这个结果曾C3=2C2=2,多次被发现。当Catalan数成为组合数学家关注的课32题时,人们才

8、从Euler的著作中得知,他在C4=C3-C2=5,121758—1759年的一篇论文中早已提出这个问题,并43予以解决。在西方为首创,要比Catalan早80年。C5=C4-C3=14,121.4清代数学家董诚(1791—1823)的工作543董诚受明安图的影响,在《割圆连比例法图C6=C5-C4+C3=42。123解》中获得[11]⋯2m(m-1)3明安图在研究无穷级数展开式过程中多次用到式sinmA=msinA-3.sinA+222(3),说明Cn+1可表为它前边若干项与算术三角形m(m-