连接分拆、连接圈和一些格路径上的结果

• 作 者: 吴宜均
• 机 构: 南开大学
• 出 处: 南开大学
• 发表日期: 2007年期
• 关键词: 非交叉分拆 Schroder路 连接分拆 连接圈 上升树 广义k-Stirling数 格多项式 偶树 非交叉树 三叉树 振荡杨表 格路径

这篇论文主要涉及了连接分拆、连接圈和格路径上的一些结论。 K.J.Dykema最近在研究自由概率理论中的非对称T-变换时，引进了"非交叉连接分拆"这样一个新的组合结构。众所周知，集合[n+1]的非交叉连接分拆的个数和计算Schroder路的第n个大Schroder数r<,n>相等。在第2.2节，我们给出了它们之间的一个组合证明，并在此基础上，得到了非交叉连接分拆的一系列组合性质。 接下来，我们引进了连接分拆和连接圈这两个新的组合结构。在第2.3节，我们通过建立连接分拆和上升树之间的一一对应关系，得到集合[n]上的连接分拆的个数为n!，这其中，有k个单连极小点的有c(n，k)(第一类Stirling数)个，满足条件β(π)=k的有A(n，k)(Eulerian数)个。然后我们证明了连接分拆上2-交叉和2-嵌套个数的对称性，并给出了具体的表达式。 在第2.4节，我们给出了连接圈的两种图表示。利用第一种图表示，给出了连接圈个数的递归表达式的一个组合证明，利用第二中图表示，给出了连接圈集合LC(n+1)和集合分拆的子集P<,2>(n)之间的一一对应关系，并得到了集合[n]上单连极小点个数为m的连接分拆的个数为2n-m-1/m-1 (2n-2m)!/(n-m)|2。最后我们给出了连接圈在第二种图表示下，交叉数和嵌套数的对称性。 在第3章中，我们发展了一种形如Pascal三角形的格路——它从(0，0)出发，到(2n，n)结束，有2n步向东、n步向北并且不超过直线y=x/2，和它上面的格多项式。它的每一步和其它能够用三值多项式T<,n>(x)和3-Catalan数T<,n>(1)=1/2n+1( )计数的组合结构之间存在着一一对应的关系，在第三章中，我们详细研究了这种格路和偶树、避免12312模式的匹配、加限制的振荡杨表之间的关系，并给出了格多项式的多种组合解释。