经典Catalan数的组合背景

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

1、万方数据2003年2月第33卷第1期西北人学学报(自然科学版)JournaIofNorthwestUnjvcrslty(NaturaIScIenccEdition)Feb．2003V01．33No．1经典CataIan数的组合背景刘芹英(西北大学教学与科学史研究中心，陕西西安710069)摘要：探讨了经典catalan数在东、西方发现的年代和历史，特别介绍了中国清代数学家明安图(16927—17637)在17世纪30年代对catalan数的首创性工作和应用。列出30种catalan数的有关公式、组合模型或应用实例，并简要阐明其组合意叉。关键词：组合计数ICatalan数；明

2、安图；L¨Euler；E．C．Catalan中围分类号：011文献标识码：A文章编号：1000一274x(2003)01一0121一04Cata}an数：1，l，2，5，14，42，132，⋯是组合数学中应用广泛的重要计数函数，本文记作e。比利时数学家E．c．catalan(1814一1894)，在1838年发表的一篇论文[13中讨论了尔后所称的Catalan问题；”个不同因子间连续作乘法，如何确定不同的求积方法数?他获得Catalan数的计数公式：，0¨c。={ir‘I，(n≥o)。(1)”T1＼nf它表示算术三角形“中垂线”上的数递次除以自然数后所得的数列。现代组合学对

3、Catalan数的深入研究，发现了许多具有组合意义的应用实例，有人估计不少于50种。它们散见于各种文献之中，网上查询，有人列出16种”j，颇为有趣的是令人联想到能否不断补充，使之臻于完备。其中，特别是许多西方数学家不了僻中国历史上对Catalan数的研究成果，清代数学家明安图(约16927—17637)是Catalan数的首刨者[“，现在已逐步被国内外数学界承认n’5]。明安图之后，还有几位清代数学家对此也有研究，均在1838年之前，大多鲜为人知。圊于所见，本文在有限的范围内搜集相关材料，重点在介绍和阐明中国数学家的成果，共获得与Catalan数有关的公式、组合模型和应用实

4、例30种。当然，这还是不够的，也可能有理解或翻译方面的不足，还需要感兴趣的学者给予指导和进一步补充。l经典catalan数的产生1．1Newton二项式定理(1捌。一宝(∽1一一K2o＼虎Jl+善每#‰∥(1水1)o(2)当指数d=l／2时，Newton=项式定理展开式必然可以表示成catalan数作系数的幂级数(推导过程从略)。但是，Newton并没有把系数写成Catalan数的形式。1．2明安圈是cat日lnn数的首创者最早发现catalan数的是我国清代数学家明安图。17世纪30年代他在研究无穷级数时得到该数的3种算法，并多次将它应用于运算之中。其中，两种算法公式是现

5、今组合数学书籍、论文中都未知的。他的有关成果详载于遗著《割圆密率捷法》[63中，由后人整理出版口]。Catalan数的卷积型递推公式c。一∑c—cn(”≥2)。(3)明安图在计算无穷级数时首先发现了这一规律，并在计算中两次运用。明安图一项重要的工作是获得了Catalan数的组台递推公式收稿日期：2002一05—21基金项目：国家自然科学数学天元基金资助项目(2000)作者筒介：刘芹英(1963一)，女，河南安阳人。西北大学博士生。从事中国数学史研究万方数据一122一西北大学学报(自然科学版)第33卷c一一荟c圳‘c(：：：卜一Ⅻ。(3)初始条件是C。一1．C。一1。此式为世

6、界首创，区别于西方在历史上和现代求catalan数的所有方法。除了他的算法之外，迄今投有现代的证明。式(3)当"≤5时有C2=cl—l，C3—2Cz一2，C4C5C8●，●c。一(2c。一(；c；一EC2=5明安图在研究无穷级数展开式过程中多次用判式(3)，说明c。可表为它前边若干项与算术三角形中第n条斜线上若干组合数乘积的代数和。明安图建立了3个几何模型，通过较复杂的几何、代数、级数运算“1(过程从略)．从其中两个获得式(3)，一个获得式(5)，(6)。后者是从原文中经抽象建起的一个奇特的计数结构。设肘，一(1)，M：一(o，1)；以下的算法步骤为％一(2M+％)％一盟(

7、1)+(0，1)](o，1)一(2，1)(0，1)一(0，O，2，1)，M=[2(M，+尬)+托]％一(2，2，2，1)(0，0，2，1)=(0，O，0，4．6，6．4，1)，M。一[2(M，+M2十M3)+M4]MI一(o，o，o，o，8，20，40，68，94，114，116，94，60，28，8，1)。H坛+一一(2∑舰+％)眠(4)^一1肘C一≥：胍一再(1，l，2．5，“，42，132’．．·，c1)。(5)这种算法相当于建立了一种生成函数，英国数学家P．J．Larcombe给出一个现代证明”。明安图应用