欧拉对经典组合学的贡献

《欧拉对经典组合学的贡献》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、万方数据《自然科学啦研究》笨22卷第4期(2003年)：361--367StudiesinthellistoryofNaturalSrieneesVol22Na4(2003欧拉对经典组合学的贡献刘建军刘芹英西北大学教学系，州毫71帅69)摘要评述欧拉在组合学上的成就一对整数分折、错位排列、欧拉方阵和计数函数所作的奠基性工作，分析他解决这些问题的数学思维方法以厦对后人的启发，简介这些问题后来的发展情况，对欧拉教学成就的研究从学科分支的角度给出补充。关键词欧拉分拆错位排列欧拉方阵Catalan数中图分类号01J文献标

2、识码A文章编号1000—0224(2003)04—0361—07组合学是离散数学的一个重要分支，近年来随着计算机科学的发展不断壮大，它是‘个上要研究离散性对象关系结构的量化模式的学科。组合学中的许多问题看似简单，但解决起来却需要一些思维技巧。在组台学史l，欧拉(LeonhardEuler，1707—1783)曾巧妙地解决了一些经典组合学问题并引入了重要的方法，但在很多研究欧拉数学贡献的文章或书籍中，基本上没有谈到他在组台学方面的下作。本文对此给予补充。欧拉对组合学发展所作的主要工作有四个方面：整数分拆、错位排列、

3、欧拉方阵猜想和计数甬数。1对正整数分拆的研究分拆是指把一个正整数R表示成正整数和的形式，如6可以写成：6，5+l，4+2，4+l+J．3+3，3+2+】，3+1+】+1，2+2+2，2+2+1+1，2+1+1+1+l，1+I+l+1+1+1。共u种形式，也就是说6的分拆数是1l，其中6看成是它的一个单一分拆，而4+2和2+4视为同一分拆，，正整数分拆问题看似简单，但其计算并不是易事，如24的分拆数是1575。整数分拆问题最早是莱布尼兹(GW，Leibniz，1646--1716)在1699年给约翰·伯努利(Joh

4、nBernoulli，1667一1748)的信中提到的。欧拉对整数分拆问题的研究源于1740∞1年诺地(PhilippeNaud∈)给他的一封信。诺地在信中询问欧拉有关凋和级数∑击的计算收祷日期：20D1·】D-23；蝰回日期：2002-11_24作者简介：刘建军，1973年生，内蒙古太仆寺旗^．西北大学数学系博士生。荆芹英，1963年生，洲南毒阳人．阿北大学数学系博士生。万方数据自然科学史研究22卷结果，同时问欧拉是否知道正整数m能够表示成若干个不同或可相同的正整数和的方法数⋯。于是欧拉着手研究这一问题，他对问

5、题深遂的洞察使他很快发现，分拆数的计算与二项式的乘积有着特定的联系。若把Q=(1+x)(1+x2)(1+x3)⋯=兀(1一#“)的乘积形式展为幂级数，则有p=1+』+Ⅳ2+2x3+2∥+3f5+⋯(1)式巾每个z非零次幂的系数恰为把其对应的指数分拆成不同正整数的分拆数。仔细思考后，这种分拆数与幂级数中的系数和指数的关系亦很明硅。如z6的系数是4，即6分拆为不同正整数的方法数是4，通过多项式乘法表示，则*6=x5·z=z4·。2=x3·x2·x，而6的这种分拆正好是6，5+1，4+2和3+2+1。这是一个伟大的发现

6、，它把组合问题与幂级数联系起来，使得分拆问题转化为幂级数中x非零次幂的系数与指数的关系。在此基础上，欧拉又考虑了二项式无穷乘积的倒数与分拆数的关系。南几何级数÷=1+。+n2+Ⅱ5+。4+⋯，故1一“R=(1+』+z2+z3+···)(1+*’+』6+x9+·-)(I+z5+z”+---)(1+z7+#“+···)⋯=(1+￡+x1+1+r1小1+--·)(1+x3+*3+3+z3+3+3+．．-)(1+x5+x5+5+．-．)．．-=l+z+x2+2x3+2x4+325+4≈6+527+一．．f2)此式与上面(

7、1)式中p的表达式一致，这一结果令欧拉激动不已。(2)式中z非零次幂的各个系数正好表示其对应指数分拆为奇数(可重复)的方法数，而这与(1)式中分拆为不同整数的方法数相等。对此，欧拉给出如下定理：把一个正整数分拆为不同正整数与分拆为可重复的奇数的分拆数相等。”1在给诺地的回信中他给出了这一定理的证明。欧拉的另一深入研究是，对(1一z。；)’1=1+x。：+(z。z)2+(98z)3-·-则(x。)’；’对应于d在n的分拆中出现，次。特别地，这导出了现今所谓的分拆一生成函数的公式：∑P(n)z“=几(1一x“)～，这

8、里P(n)是n的分拆总数。^一un2L欧拉又引人了函数P=(1+x)(1+X2)(1+z4)(1+x8)(1+z“)⋯，每个二项式中x的指数是它前一相邻指数的2倍，展开这一乘积后，有P=1+x+x2+#3+z4+』5+⋯。由上述可知，把一个整数分拆成2的指数形式的和是惟一的。这也是数论中一个重要结论。欧拉对整数分拆的研究还不止这些，在其著作《无穷分析引论》(1748)的第