论文部分内容阅读
近几年里,有禁分拆与有禁匹配被广泛地研究,越来越多的组合数学中的经典结果被推广至分拆与匹配的研究中.本文主要研究了几类有禁分拆与有禁匹配的计数问题.文中我们主要使用了构造双射的方法和传递矩阵法,并借助计算机开发了一个Maple软件包来生成特定序列所满足的递归方程.
本文共由三章组成.其组织如下:
在第一章中,我们简要叙述了一下该文的研究背景,并介绍了部分文中使用的基本定义和常见符号.
在第二章中,我们主要考虑双边对称的3-noncrossing分拆的计数问题.Chenet al.首次提出了集合分拆中的k-crossing和k-nesting的概念,并通过vacillatingtableaux与分拆之间的一个双射来证明这两个统计量对称联合分布的性质.该双射推广了全排列和标准杨表对之间经典的RSK对应,并同样具备RSK对应所具备的对称性.基于该双射的对称性质和其与格路之间的关系,并借用迭代级数的常数项理论,我们通过开发了一个针对二维平面内vacillaring lattice walk计数问题的Maple软件包,以此得到集合[n]中所有3-noncrossing分拆的个数所满足的递归关系式.该软件包适用于一类相似的vacillating lattice walk的计数问题.
在第三章中,我们主要考虑可通过k次堆栈排序的分拆和匹配的计数问题.我们刻画了可通过k次堆栈排序的分拆与匹配的主要性质.一个分拆足可通过k次堆栈排序的当且仅当它的序列表示避免23…(k+2)1-模式.我们计算了可通过k次堆栈排序的无相交分拆、无相交匹配和无嵌套匹配这三类分拆的生成函数,并通过构造双射的方法给出了七次堆栈排序的分拆的生成函数的一个公式.该公式比Mansour和Severini通过核方法所得到的公式更简单直接.利用经典的传递矩阵法,我们证明了可通过k次堆栈排序的匹配的个数的生成函数足有理的.
最后,我们在附录中给出第二章中所提到的Maple软件包及该软件包应用于hesitating lattice walk计数问题时的初始变量.