论文部分内容阅读
本文主要研究了排列表上的组合性质。我们建立了排列表、连接分拆和排列三者之间的对应关系,研究了排列表的逆序数。我们将禁排的概念推广到排列表上,得到了排列表的不同子类分别与Schroder路,Dyck路,集合分拆的对应关系。我们证明了一些经典的计数结果,如Stirling数,欧拉数等都可以用排列表的某些统计量给出。
第一章简要介绍了排列表相关的背景知识,包括排列表是如何从完全非负的格拉斯曼流形中得出的,排列表与不完全非对称互斥过程的联系。
在第二章中,我们首先回顾排列表的一个递推关系,从递推关系中我们可以看到排列表中某些统计量的分布。接着,我们给出排列表的不同表示,分别是全1表示,限制的0-1表示,选择性表示和阶梯形表示。我们将给出这些表示对于分析排列表中的统计量所起的不同作用。
在第三章中,我们建立了n长的排列表与[n]={1,2,……,n}上的连接分拆之间的一一对应,另外我们构造了[n]上的连接分拆与排列之间的一一对应。结合这两个对应关系,我们建立了新的从n长的排列表到[n]上的连接分拆之间双射,从而我们研究了排列表的一些组合性质。
在第四章中,我们发现并引入排列表上的逆序数这一统计量。利用Corteel和Nadeau的双射,我们证明了排列表逆序数与排列中广义样式32-1是同分布的。这给出了Corteel和Nadeau提出的关于在排列表中寻找与排列中样式32-1相对应的统计量的问题的一种解答。作为特殊情况,我们可以看到逆序数为0的排列表其实就是Corteel和Nadeau定义的L-Bell表。
在第五章中,我们研究了排列表的某些子类,它们与Bell数以及长度为3的一些禁排紧密相关。利用第三章中排列表与连接分拆的对应关系,我们发现不交分拆对应于一类特殊的排列表,称为不交排列表。我们给出不交排列表的递推关系以及n+1长的不交排列表和2n长的Schroder路之间的双射。进一步地,我们引入不嵌套排列表的概念,我们发现不嵌套排列表也可以用Schroder数来计数,我们建立了不嵌套排列表与不交排列表之间的双射并研究了相关的组合性质。