catalan数的一个递归关系

《catalan数的一个递归关系》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、第16卷第2期苏州大学学报(自然科学)Vol.16,No.22000年4月JOURNALOFSUZHOUUNIVERSITY(NATURALSCIENCE)Apr.2000文章编号:100022073(2000)0220019203Catalan数的一个递归关系X骆汝九(连云港职业技术学院,江苏连云港222001)摘要:将非结合代数中n元X1,X2,⋯,Xn按给定次序的加括号乘法(结合法)转化为长为n-1的路X1X2⋯Xn的边收缩问题,用容斥原理,得到Catalan数的一个新的递归关系.关键词:Catalan数;递归关系;边的收缩中图分类号:O15711文

2、献标识码:A1主要结果Catalan问题(CATALANEC,1838):求非结合代数中n元X1,X2,⋯,Xn按给定次序的加括号乘法(结合法)的种数an1称an为Catalan数1[1]12n-2周知:an=且满足递归关系nn-1an=∑akan-k,n≥21FkFn-1a0=0,a1=11(111)本文主要结果:定理1Catalan数an满足递归关系n-tt-1an=∑(-1)an-t(112)1FtFrtnn其中r=[],即≤的最大整数122考虑Catalan问题的一个变着:求n圈X1X2⋯XnX1上n元X1,X2,⋯,Xn按给定次序的加括号乘法的种

3、数an1定理2an满足递归关系X收稿日期:1999-05-28作者简介:骆汝九(19672),男,江苏盐城人,连云港职业技术学院讲师,研究方向为组合数学.20苏州大学学报(自然科学)第16卷n-tt-1nan=∑(-1)an-t(113)1FtFrn-ttn其中r=[]12推论an=nan1(114)2预备知识及引理首先给出加括号乘法的一种表示法1考虑路X1X2⋯Xn,联接相邻顶点Xi、Xi+1的边记为ei(1≤i≤n-1),见图1:图1路X1X2⋯Xn用收缩边ei(记为ei)表示对元Xi与Xi+1加括号,边ei被收缩后,Xi与Xi+1叠合在一起,成为边e

4、i-1的右端点(集),同时也是边ei+1的左端点(集)1-在路的边收缩方式C下,边ek(1≤k≤n-1)的左、右端点集分别记为Vc(ek)、+-+0Vc(ek)1若

5、Vc(ek)

6、=

7、Vc(ek)

8、=1,则边ek被收缩记为珋ek1例讨论路X1X2X3X4(图2):图2路X1X2X3X40000在边收缩方式C1:珋e1珋e3珋e2和C2:珋e3珋e1珋e2下--++Vc(e1)=Vc(e1)={X1},Vc(e1)=Vc(e1)={X2},1212--++Vc(e2)=Vc(e2)={X1,X2},Vc(e2)=Vc(e2)={X3,X4},1212--++

9、Vc(e3)=Vc(e3)={X3},Vc(e3)=Vc(e3)={X4}112120在边收缩方式C3:珋e1珋e2珋e3下-+Vc(e1)={X1},Vc(e1)={X2},33-+Vc(e2)={X1,X2},Vc(e2)={X3},33-+Vc(e3)={X1,X2,X3},Vc(e3)=={X4}133边收缩方式C1和C2对应着同一种加括号乘法:((X1X2)(X3X4))1边收缩方式C3对应着加括号乘法:(((X1X2)X3)X4)1定义路的两种边收缩方式是相同的,当且仅当在这两种边收缩方式下,每条边的左、右端点集分别对应相等1由定义,例中的两种

10、边收缩方式C1和C2相同1第2期骆汝九:Catalan数的一个递归关系21由上面的分析不难得知:非结合代数中n元X1,X2,⋯,Xn按给定次序的加括号乘法(结合法)的种数an即为对路X1X2⋯Xn的n-1条边e1,e2,⋯,en-1收缩的不同方式数1为证明定理,引入下面的引理(见文献[2])1引理1(容斥原理)设A1,A2,⋯,Aq是给定集合S(有限或无限)的一个q-子集系,允许有空集或相同1则

11、A1∪A2∪⋯∪Aq

12、=∑

13、Ai

14、-∑

15、Ai1Ai2

16、+∑

17、Ai1Ai2Ai3

18、1≤i≤q1≤i

19、A1A2

20、⋯Aq

21、(211)引理2设fl(n,p)为具有以下性质的p-块P<{1,2,⋯,n}的个数:P的任意两个元素间至少有{1,2,⋯,n}的l(≥0)个元素不属于P1则n-(p-1)lfl(n,p)=()(212)p引理3设gl(n,p)为具有下列性质的p一块P<{0,1,⋯,n-1}的个数:P的任意两个元素间至少有{0,1,⋯,n-1}的l(≥0)个元素不属于P1则nn-plgl(n,p)=()(213)n-plp3定理的证明定理1的证明对(3)及(33)分别应用(211)、(212)1000an=

22、珋e1∪珋e2∪⋯∪珋en-1

23、(3)000000=∑

24、珋

25、ei

26、-∑

27、珋ei1珋ei2

28、+∑

29、珋ei1珋ei2珋ei3

30、1≤