论文部分内容阅读
排列是组合学中一个经典的研究对象,与许多其它组合结构密切相关,包括树、格路、无交叉集合划分、01-矩阵、标准杨表等。自著名组合学家P.A.MacMahon在20世纪初的标志性工作以来,排列统计量的研究成为组合学领域一个重要研究课题。排列上重要的统计量包括主指标、逆序数、下降数、胜位数等。众所周知,排列构成的对称群是A型Coxeter群。对称群上统计量的许多结果已被推广到B型Coxeter群和D型Coxeter群上。 本文主要研究A型、B型和D型Coxeter群上(整数值)统计量和集合值统计量的性质。我们的贡献主要包括如下几个方面。第一,利用D.Foata和G.-N.Han在对称群上的一个双射,我们回答了T.K.Petersen关于寻找一个等分布结果的组合解释的问题。我们还重新得到了S.Poznanovi(c)在带限制的排列上的一个等分布结果,并将两个排列统计量推广至标准Fibonacci表上。第二,通过在B型排列上构造双射,引入若干新的集合值统计量,我们得到等分布的六组四元集合统计量,从而推广了Foata和Han关于集合统计量的分布结果。进一步,我们还考虑B型排列的分解结构和带限制的情况,并由此得到若干细化和加强形式。第三,通过在D型排列上引入D型排列码,我们构造了一个双射,从而得到了Petersen另一个等分布结果的加强形式,同时我们也用群代数的工具给出了一个代数证明。 本论文的结构如下。 在第一章中,我们回顾了相关的研究背景和基础知识。具体而言,我们介绍了Coxeter系统、对称群、排列统计量、Dyck路、完美匹配等。同时,我们给出了一些已知的统计量的生成函数公式。 在第二章中,通过研究Foata和Han利用排列码构造的双射,我们得到若干排列统计量的性质。在本章的第二节中,我们给出了一个等分布结果的组合解释,从而回答了Petersen的一个问题。在第三节中,我们证明了带限制的排列上的一个等分布结论,这对应于在n行n列的Ferrers板上放置n个互不攻击的车。在本章最后一节,受K.Killpatrick将MacMahon关于对称群上主指标和逆序数的等分布这一经典结果推广至标准Fibonacci表上的研究的启发,我们将一些排列统计量推广到标准Fibonacci表上。 在第三章中,我们在B型排列上引入若干新的集合值统计量并得到了这些统计量的分布结果。本章包含的结果可概括如下。我们在第三节中定义B型排列的两个排列码,这给出Foata和Han关于排列码的B型模拟。在第四节中我们构造了Bn上的一个双射,从而得到了B型Coxeter群上的六组四元集合统计量的等分布性,这刻画了B型排列的圈表示、从左到右极大位、从右到左极小元的联合分布性质。同时,我们利用B型排列的一个分解得到了这些等分布组的细化结果。此外,作为推论,我们还得到一些整数值统计量在B型Coxeter群上的等分布性质。在本章最后一节,我们考虑了此双射在特定限制的B型排列上的性质,得到另一个细化结果,其特殊化对应于S.Poznanovi(c)应用染色匹配和染色Dyck路得到的等分布结果。 在第四章中,我们引入D型排列上的两个新的统计量,并构造了一个双射,从而得到了D型排列上两对等分布的统计量。这是对Petersen的一个等分布结果的细化和加强。此外,我们发现该结论也可以用群代数的工具证明。具体来讲,通过应用Petersen关于D型排列的对角和的两种分解形式,我们在本章最后得到这两对统计量的生成函数。