首页 > 硕士 > 理学 > 正文

不套匹配的交叉点计数

Enumeration of Crossings on Non-nesting Matching

作者: 专业:应用数学 导师:邓玉平 年度:2010 学位:硕士  院校: 大连理工大学

Keywords

non-nesting matching, crossing, Dyck path, area, inverse, Catalan number

        在不套匹配的线性表示中,弧与弧之间有交点,叫做交叉点,本文主要目的就是对不套匹配中的交叉点进行计数。组合计数的一种常用解决办法就是建立与某种组合事物之间的双射,利用该组合事物已有的计数结论间接得到所求问题的计数。本文也采用了双射的方法,建立不套匹配关于统计量交叉点与Dyck path关于统计量面积之间的双射,通过逆序的概念将二者联系起来。由于Dyck path的计数为Catalan数,根据Catalan数递推公式的计算方法得到了长为2n且有k个交叉点的不套匹配的计数的递推公式,进而得到一般发生函数;同时给出了Catalan数基于交叉点的一种分类方式;然后给出基于q-Catalan多项式的形式上的交叉点计数公式。
    In linear representation of non-nesting matching, junctions of arcs are called crossings. The major purpose of this article is to count the crossings in non-nesting matchings. One of counting methods of enumerative combinatorics is to establish bijection between one combinatorial object and another combinatorial object. Conclusion can be obtained indirectly by existing methodology of counting of enumerative combinatorics. This article adopted the theory of bijection to establish the one between non-nesting matching related to crossings of statistics and Dyck path related to the area size of statistics. Then the relation between non-nesting matching and Dyck path will be made by the inverse method. The enumeration of Dyck Paths is Catalan number, a recurrence formula can be acquired of non-nesting matching with the length of 2n and k crossings by computing method of recurrence formula of Dyck path. Further more, a generating function is obtained. At the same time, we explored the way of partition Catalan number based on crossings. Then, enumeration formula of crossing formally will be defined based on q-Catalan polynomial.
        

不套匹配的交叉点计数

摘要4-5
Abstract5
1 引言7-11
    1.1 集合的划分及不套、不交的概念7-9
    1.2 格路9-11
2 不套匹配与Dyck path之间的双射11-16
    2.1 不套匹配与统计量交叉点11
    2.2 Dyck path与统计量面积11-15
    2.3 不套匹配与Dyck path之间的双射15-16
3 交叉点计数公式的一般发生函数16-20
    3.1 P(n,k)的递推关系17-18
    3.2 P(n,k)的发生函数18
    3.3 Catalan数的一种划分方式18-20
4 q-Catalan多项式20-25
    4.1 q,t-Catalan polynomial20-22
    4.2 q-Catalan多项式22-25
5 不套匹配和不交匹配问题的进一步讨论25-30
    5.1 不交匹配与统计量嵌套25-26
    5.2 Motzkin path与块中最多两个元素的划分26-30
结论30-31
参考文献31-33
攻读硕士学位期间发表学术论文情况33-34
致谢34-36
        下载全文需36


本文地址:

上一篇:基于Penna模型的一类捕食被捕食模型
下一篇:最后一页

分享到: 分享不套匹配的交叉点计数到腾讯微博           收藏
评论排行
公告