论文部分内容阅读
对不同类型格路的研究在组合数学中一直占有重要地位。一方面,格路经常作为重要的模型来描述其它组合结构如树、有禁排列、对称函数、正交多项式、连分式等。另一方面,它们常出现在数学的其它领域如概率论、统计学等。在本文中,我们重点研究了几类格路的计数以及均匀分布问题,其中借助了徘徊杨表、缺陷引理等重要工具。振荡杨表与徘徊杨表最初出现在代数学领域,但它们与组合数学中的重要研究对象匹配与划分有着密切的联系。振荡杨表的概念是由Berele于1986年提出的。之后,Stanley借助RSK算法建立了振荡杨表与匹配之间的一一对应,Sundaram在1990年将这一对应做了扩展。徘徊杨表的概念是2005年由Halverson和Ram给出的。2007年,陈永川等人构造了徘徊杨表与划分之间的一一对应,并且以此为工具解决了经典计数理论中的一个重要问题,即他们用组合方法证明了在所有划分或匹配中,交叉数与嵌套数是对称联合分布的。目前,振荡杨表与徘徊杨表已经成为研究匹配、划分等组合结构的性质以及计数等问题的强有力工具。著名的Chung-Feller定理是计数组合学中的一个经典结果,其内容可叙述为:2n长的自由Dyck路中缺陷数的分布是均匀的。此结果是MacMahon1909年首次发现的。而该定理的命名源于Chung与Feller1949年的工作,他们重新发现并用分析的方法证明了该定理。之后,这个定理被广泛研究。迄今,自由Dyck路上的Chung-Feller定理已经有了多种不同的证明方法。例如:Raney,Narayana,Dershowitz与Zaks等人分别利用循环引理或循环路给出了证明;Callan,Jewett与Ross等人通过构造双射加以证明。此外,很多学者还着力于研究该定理的推广形式。例如:2001年,Woan发现了自由Dyck路上另一个均匀分布的参数:绝对最小长度;同年,Shapiro研究了特定的Motzkin路中绝对最小长度的均匀分布问题;游森棚等人2005年通过对不同格路生成函数泰勒展式的研究,既得到了该定理的一种加细形式又发现了赋权自由Schr(?)der路上的Chung-Feller性质;2007年,陈永川等人定义了双根平面树中的蝴蝶分解,借此给出了Chung-Feller定理以及赋权自由Schr(?)der路上Chung-Feller性质的另一种全新的证明方法;最近,马君与叶永南又研究了三类特殊的格路上缺陷数与绝对最小长度这两个参数的均匀分布问题。在本篇论文中,我们主要研究了不交自由Dyck路、自由m-Schr(?)der路、不完整自由k-Dyck路等不同格路的计数以及它们关于不同参数的均匀分布问题。在第二章中,我们得到了k-不交自由Dyck路的计数公式。该公式是通过构造k-不交自由Dyck路与有限制的平面分拆之间的一一对应,借助Stanley给出的限制行数列数与最大部分值的平面分拆的计数公式得到的。当限定k取2时,我们发现2-不交自由Dyck路与Callan给出的固定块数的不交划分的计数是相同的。借助徘徊杨表,我们建立了2n长的2-不交自由Dyck路与有n+1个块的[2n+1]上的不交划分这两个集合之间的一个双射。此外,根据Labelle合并算法,我们找到了与2-不交自由Dyck路对应的单条Dyck路的刻画方式。在第三章中,一方面,我们研究了自由m-Schr(?)der路关于缺陷数与绝对最小长度这两个参数的均匀分布问题。我们的结果统一并且扩展了之前关于自由Dyck路、自由k-Dyck路以及自由Schr(?)der路等不同格路的Chung-Feller性质,有着更为广泛的意义。特别地,我们得到了一个非常简洁直观的结果,称之为缺陷引理。该引理包含了比循环引理更多的信息,因此可以看作是循环引理的推广。在本文中,缺陷引理是发现并证明赋权自由m-Schr(?)der路上关于缺陷数Chung-Feller性质的有力工具。并且我们找到了限制斜步个数的m-Schr(?)der路计数的一个更简单的组合证明。另一方面,我们发现了一种新的方法来证明自由Dyck路中绝对最小长度的均匀分布问题。在第四章中,我们得到了固定类型的不完整k-Dyck路的计数公式,并且给出了原始的Chung-Feller定理的另一种加细形式,即在给定类型的自由k-Dyck路中缺陷数的分布是均匀的。此外,我们建立了泊车函数与集合[n]上的有根森林之间的一个双射,并且借助固定类型的k-Dyck路的计数公式得到了不交划分、泊车函数以及有根森林等组合结构中的一系列计数结果。在第五章中,我们从另外一个角度重新考虑经典的Chung-Feller定理,即将自由Dyck路看作从原点出发最终回到原点且每步取(1,0)或(-1,0)的格路,由此,我们发现并证明了四分之一平面上两种特定的格路上的有趣的Chung-Feller性质。