【作者】 龚泽；

【导师】 陈永川；

【作者基本信息】 南开大学 ， 应用数学， 2013， 博士

【摘要】 排列是组合学中一个经典的研究对象,与许多其它组合结构密切相关,包括树、格路、无交叉集合划分、01-矩阵、标准杨表等。自著名组合学家P.A.MacMahon在20世纪初的标志性工作以来,排列统计量的研究成为组合学领域一个重要研究课题。排列上重要的统计量包括主指标、逆序数、下降数、胜位数等。众所周知,排列构成的对称群是A型Coxeter群。对称群上统计量的许多结果已被推广到B型Coxeter群和D型Coxeter群上。本文主要研究A型、B型和D型Coxeter群上(整数值)统计量和集合值统计量的性质。我们的贡献主要包括如下几个方面。第一,利用D. Foata和G.-N. Han在对称群上的一个双射,我们回答了T.K. Petersen关于寻找一个等分布结果的组合解释的问题。我们还重新得到了S. Poznanovic在带限制的排列上的一个等分布结果,并将两个排列统计量推广至标准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关于排列码的曰型模拟。在第四节中我们构造了Bn上的一个双射,从而得到了B型Coxeter群上的六组四元集合统计量的等分布性,这刻画了B型排列的圈表示、从左到右极大位、从右到左极小元的联合分布性质。同时,我们利用B型排列的一个分解得到了这些等分布组的细化结果。此外,作为推论,我们还得到一些整数值统计量在B型Coxeter群上的等分布性质。在本章最后一节,我们考虑了此双射在特定限制的B型排列上的性质,得到另一个细化结果,其特殊化对应于S. Poznanovic应用染色匹配和染色Dyck路得到的等分布结果。在第四章中,我们引入D型排列上的两个新的统计量,并构造了一个双射,从而得到了D型排列上两对等分布的统计量。这是对Petersen的一个等分布结果的细化和加强。此外,我们发现该结论也可以用群代数的工具证明。具体来讲,通过应用Petersen关于D型排列的对角和的两种分解形式,我们在本章最后得到这两对统计量的生成函数。更多还原

【Abstract】 Permutations are among the richest objects in combinatorics. We can bijectively associate them with other structures, such as trees, lattice paths, noncrossing partitions,01-matrices, standard Young tableaux and so on. The modern study of permutation statistics began with the work of P.A. MacMahon. There has been much work done in studying distributions of permutation statistics, such as maj, inv, des, exc, etc. It is known that the symmetric group of permutations is a Coxeter group of type A. Many properties of permutation statistics have been extended to the Coxeter groups of type B and type D.The main objective of this thesis is to research the distributions of both integer-valued statistics and set-valued statistics on Coxeter groups of types A, B and D. Our contribution is briefly summarized as follows. Firstly, we find a combinatorial interpre-tation of an equidistribution result on permutations by employing a bijection of D. Foata and G.-N. Han on permutations. This answers a question of T.K. Petersen. We also give an explicit combinatorial interpretation of an equidistribution result of S. Poznanovic on restricted permutations. We further extend some permutation statistics to standard Fibonacci tableaux. Secondly, we construct a bijection on Bn and obtain several dis-tribution results concerning some new set-valued statistics. This gives a generalization of several distribution results of Foata and Han on permutations. We also derive some refinements of these conclusions by considering a decomposition and some restrictions on signed permutations. Lastly, we introduce two new statistics on even-signed permu-tations and deduce a strengthened form of an equidistribution result of Petersen. This thesis consists of four chapters.In Chapter1, we give a review of the background of this work as well as some ba-sic knowledge. To be specific, we introduce the Coxeter system, the symmetric group, Dyck path, perfect matching and so on. Meanwhile, some well-known generating func-tions are exhibited.In Chapter2, we focus on some distribution properties of permutation statistics. In the second section, we use a bijection of Foata and Han to interpret an equidistribution of Petersen combinatorially. In the third section, we give a proof of an equidistribution result on the set of permutations that correspond to arrangements of n non-attacking rooks on a Ferrers board with n rows and n columns. In the last section, we will extend some permutation statistics to standard Fibonacci tableaux.In Chapter3, we introduce several set-valued statistics for signed permutations of Bn and obtain many distribution results corresponding to them. We construct a bijection on Bn to show that the six quaternaries of set-valued statistics (CycB, RmilB, CycB, RmilB),(CycB, LmapB, CycB, LmapB),(RmilB, LmapB, RmilB, LmapB),(LmapB, RmilB, LmapB, RmilB),(LmapB, CycB, LmapB, CycB) and (RmilB, CycB, RmilB, CycB) are equidistributed over Bn. These results serve as type B analogues of equidistribution results of Foata and Han on permutations. More-over, we show that these equidistributions can be refined by virtue of a decomposition of signed permutations. At the end of this chapter, we also consider the equidistribution property of two quintuples of statistics on restricted signed permutations.In Chapter4, we introduce two new statistics on even-signed permutations, and obtain an equidistribution result of two pairs of statistics by constructing a bijection on Dn. This gives a refinement of an equidistribution result of Petersen. We also give an algebraic proof of this result. To achieve this goal, we apply two factorizations of the digonal sum of Dn and obtain explicit formulas for the bivariate generating functions of these two pairs of statistics.更多还原