论文部分内容阅读
有禁排列在过去的十几年中被广泛地研究,它和组合计数中的一些经典序列有密切关系.1972年Hammersley给出了S<,n>(321)的计数,1973年Knuth给出了S<,n>(231)的计数.1993年Gire发现S<,n>(321,3142)和S<,n>(231,4132)的基数都是n-th Motzkin数.Gire和West分别发现一些避免一对4长模式的有禁排列的计数是Schroder数.Stanley猜想有十类避免一对4长模式的有禁排列的计数是Schroder数,2000年Kremer证明了这一猜想.我们知道上述这些序列都计算了一些格路的基数,因此这些有禁排列与相应的格路之间存在双射.有很多人在这个方面做了一些研究,最常见的方法是ECO方法,即通过证明它们都满足同样的生成树来说明他们之间存在双射.该文我们利用标准约合分解来刻画有禁排列,然后通过标号及拆分相应的格路,从而建立他们之间的双射.该文的主要内容如下:第一章介绍一些基本概念.第二章构造了S<,n>(321),S<,n>(231)和Dyck路径的双射,以及D<,n>(321)和Fine路径的双射.第三章给出S<,n>(321,3142),S<,n>(231,4132)和Motzkin路径的双射.第四章首先定义了一类新的格路,Riordan路径,其基数是Riordan数,然后给出了D<,n>(321,3142)和Riordan路径的双射.第五章给出了S<,n>(1243,2143),Sn(4231,4132)和Schroder路径的双射.而且对于上述各种有禁排列都分别给出了它们的一些统计量.第六章利用2-Motzkin路径给出了从Motzkin数到Catalan数的"离散的连续"过程,这解决了Barcucci,Del Lungo,Pergola和Pinzani提出的一个问题.