收藏本站
《南开大学》 2004年
收藏 | 手机打开

格路与有禁排列

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

手机知网App
【相似文献】
中国博士188bet全文数据库 前1条
1 邓玉平;格路与有禁排列[D];南开大学;2004年
中国硕士188bet全文数据库 前3条
1 赵仓梅;Fine格路和有禁错排[D];大连理工大学;2009年
2 房月静;有禁排列与Dyck格路[D];大连理工大学;2012年
3 高笑松;一种对称格路的性质及应用[D];大连理工大学;2010年
 快捷付款方式  订购知网充值卡  订购热线  帮助中心
  • 400-819-9993
  • 010-62791813
  • 010-62985026