Enumeration on Set Partitions and（k,m）-ary Trees

《Enumeration on Set Partitions and（k,m）-ary Trees》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、分类号学校代码10055学号021856尚蕊炙浮NankaiUniVersity论文题目：里竺!竺!!!坐竺竺璺壁Partitionsand(k，m)一aryTrees博士学位i仑文DOCTORALDlSSERl-ATION培养院系：缉盒麴差虫!釜一级学科：麴堂二级学科：廑旦麴堂论文作者：堑羞霞。．指导教师：睦丞刖塑援南开大学研究生院2005年4月，÷耘。～黄。孕”j霉。j，九公允欲口新月买摘要本文主要研究了几类带限制的集合分拆以及(≈，m)一叉树的计数．首先我们给出了集合【n】={1，2，⋯，n)上的m正则分拆的一个约简算法．该算法将集合H上的m正则分拆转化为集合h—

2、l】上的(m一1)一正则分拆．我们还证明了分拆的不交性质在这种约简算法下保持不变，从而给出了simion—u11man以及K1azar的一个组合恒等式的简单证明．利用该恒等式我们还给出了一种广义RNA二级结构的计数公式．对于一般的不交分拆，利用该算法，我们可以将其转化为一个只包含单点、独立边及自环的图，从而得到一个将Narayana数用catalan数表示的恒等式．然后我们介绍了Dyck路和2一Mozkin路上的标号规则．对于任意一个3长的排列r，我们都给出了一种Dy矗路上的标号规则，通过这种标号可以建立长为2n的Dyck路与集合M上避免r的有禁排列之间的双射。这些双射

3、还将排列上的一些统计量转化为Dyck路上的统计量。对于2一Mozkin路，我们给出了两种标号规则：最远标号规则与最近标号规则．我们可以利用这些标号规则来研究多种带限制的集合分拆的计数等问题。作为这些标号规则的一个应用，我们还给出了集合M上二正则不嵌套分拆(避免n6她的二正则分拆)和长为n一2的2一Mozkin路之间的对应．接下来我们开始研究3不交匹配和3不交分拆．关于3不交匹配的计数是近两年由Klazar提出的问题．该问题的更广义的形式是关于≈不交分拆的计数．我们在本文中指出有三类禁止长度为6的子序列的『2n1上的有禁匹配均和长为2n的不交Dyck路对的集合之间存在一一

4、对应．这三类有禁匹配分别是3不交匹配(避免123123的匹配)、3不嵌套匹配(避免123321的匹配)以及非双嵌套匹配(避免123312的匹配)．我们还给出了这三类有禁匹配的计数公式．本文中关于集合分拆的最重要的结果是引进了一种新的工具：“犹豫杨表”，并通过它来研究匹配以及分拆上的交叉数与嵌套数。利用集合分拆与犹豫杨表之间的一个双射，我们证明了如果给定分拆的每个块中的最大和最小元素，这些分拆的交叉数与嵌套数有对称的交集分布．因此对所有的集合[礼】上的分拆以及集合fn]=【2m】上的匹配，交叉数与嵌套数也是对称交集分布的．该结论的一个推论就是：女不交分拆(匹配)与女不嵌套

5、分拆(匹配)的个数相等．在本文的最后我们定义并研究了(k，m)一catalan数‰c扯熹(忡”≯)，它是传统意义的catalan数G(n)=击(哿)的一个推广。我们还给出了(％，m)一catalan数的两种组合解释：含有n个关键点的(％，m)一叉树蛆及(mn十1)xk的“停车表”．利用(≈，m)一catalan数的这两种组合解释我们给出了它的一些递归关系。利用这些递归关系我们证明了关于m叉树以及平面森林的hook长度多项式的一些公式．作为在这些公式的推论，我们还得到了关于m叉树以及平面森林上的计数的几个恒等式．关键词：集合分拆，匹配，有禁排列，RNA二级结构，格路，Dy

6、ck路，Motzkin路，2一Motzkin路，整数分拆，振荡杨表，犹豫杨表，RsK算法，k不交分拆(匹配)，％不嵌套分拆(匹配)，(k，m)一catalan数，(％，m)一叉树，(k，m)-parkingtable，二叉树，m叉树，平面森林，hook长度多项式．Abstract。I。histhe8isconcernsseveralenumerationresultsonsetpartitions0ur丘rstresuItisareductionalgorithmwhichtransforms?n。regularpartitionsoffnJ=fl，2，．⋯n)to(m

7、一1)一regu】arpartitionsof[n一1]，1肌showthatthisalgorithmpreserVesthenoncrossingproperty．Thisyieldsasiinpleexplana土iollofanidentityduetoSimi。n—U11manandK1azarinconneccionwithellulneran。nproblemsonnoncrossingpartitionsandRNAsecondarystructuresForordi工1arynoncrossingparticions，t