dyck路%2cmotzkin路和schroder路上峰计数

《dyck路%2cmotzkin路和schroder路上峰计数》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、摘要Dyck路，Motzkin路和Schr6der路等格路径作为一类重要的组合结构是近年来计数组合学研究的一个热点．它们与树，有禁排列，正交多项式，连分式等其它结构联系紧密，并且在统计学，随机过程及生物信息学等领域有着广泛应用．在本文中我们主要研究了这三种格路径上的统计量：峰的个数．A．Regev在[16】中利用递推关系通过大量的计算给出了Motzkin路上的峰的个数，并发现n阶广义Motzkin路的个数等于所有n阶的Motzkin路上的峰的个数的两倍加一，并提出公开问题，即寻找这一问题的双射证明．本文的主要结果就是构

2、造了一个双射从而解决了A．Regev提出的问题．利用这一双射我们给出了Dyck路，Motzkin路和SchriSder路上峰的个数，以及Narayana数的一个新的证明．另外通过用两种不同的方法计数广义Schr／Sder路的个数，我们还得到了一个有趣的组合恒等式．这个等式即为[21]中第115页习题3(g)等式的变形．本文的另一个主要结果就是利用RSK算法，给出了Motzkin路和行数不超过3的标准杨表之间的一个双射．关键词：格路径，Dyck路，Motzkin路，SchriSder路，峰，标准杨表，RSK算法．ABST

3、RACTDyckpaths，MotzkinPathsandSchroderpathsaleveryimportantcombinatorialstruc—turesinenumerativecombinatorics．Besidestheircloseconnectionswithothercombina-torialstructuresliketrees，restrictedpermutations，orthogonalpolynomials，continuedfrac-tions，etc．，theirapplica

4、tionsalsoarisefromfieldsasstatistics，randomprocessesandbioin—formatics．Inthispaperwemainlystudythestatistic“numberofpeaks’’intheselatticepaths．In【16】A．Regevcomputethenumberofpeaks(humps)inMotzkinpaths，andnoticethatthenumberofgeneralizedMotzkinpathsoforder，lequal

5、soneplustwicethenumberofpeaksinallMotzkinpathsofordern，andaskforabijectiveproofforthisidentity．Inthispaperwegivesuchabijection，fromwhichwegivethenumberofpeaksinDyckpaths，MotzkinpathsandSchr6derpaths．Usingthisbijection，wegiveanewproofthatthenumberofDyckpathsoford

6、er，1withkpeaksistheNarayananumber．Bydoublecountinggener-alizedSchr6derpaths，wealsofindaninterestingidentityinvolvingproductsofbinomialcoefficients，aslighflydifferentformofthisidentityappearsin【21】Page15ex．3(g)．AnotherresultofthispaperisabijectionviaRSKalgorithmb

7、etweenMotzkinpathsandStandardYoungTableauxwithatmostthreerows．Keywords：Latticepaths，Dyckpaths，Motzkinpaths，Schr6derpaths，peaks，StandardYoungtableaux，RSKalgorithm．丁云硕士学位论文答辩委员会成员名单姓名职称单位备注任韩教授华东师范大学数学系主席吕长虹教授．华东师范大学数学系郭军伟副教授华东师范大学数学系第一节引言1引言1．1Motzkin路的概念在平面直角坐标系

8、中，横坐标和纵坐标都为整数的点称为平面格点，平面格路径是指在所有的平面格点中，从一点到另一点只走格点的路，格路径的长度是指其所走的路的步数．我们这里研究的都是平面格路径，下面都简称为格路径．一条长度为n的格路径也可以看做一个，l维的向量v=(v1’V2，⋯％)，这里vf∈刃，vf+l—vf表示这条格路径所走的步法之一．格路径是组合