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