關(guān)于格路的計(jì)數(shù)以及均勻分布的一些研究.pdf

1、對不同類型格路的研究在組合數(shù)學(xué)中一直占有重要地位。一方面，格路經(jīng)常作為重要的模型來描述其它組合結(jié)構(gòu)如樹、有禁排列、對稱函數(shù)、正交多項(xiàng)式、連分式等。另一方面，它們常出現(xiàn)在數(shù)學(xué)的其它領(lǐng)域如概率論、統(tǒng)計(jì)學(xué)等。在本文中，我們重點(diǎn)研究了幾類格路的計(jì)數(shù)以及均勻分布問題，其中借助了徘徊楊表、缺陷引理等重要工具。
　　 振蕩楊表與徘徊楊表最初出現(xiàn)在代數(shù)學(xué)領(lǐng)域，但它們與組合數(shù)學(xué)中的重要研究對象匹配與劃分有著密切的聯(lián)系。振蕩楊表的概念是由Berel

2、e于1986年提出的。之后，Stanley借助RSK算法建立了振蕩楊表與匹配之間的一一對應(yīng)，Sundaram在1990年將這一對應(yīng)做了擴(kuò)展。徘徊楊表的概念是2005年由Halverson和Ram給出的。2007年，陳永川等人構(gòu)造了徘徊楊表與劃分之間的一一對應(yīng)，并且以此為工具解決了經(jīng)典計(jì)數(shù)理論中的一個(gè)重要問題，即他們用組合方法證明了在所有劃分或匹配中，交叉數(shù)與嵌套數(shù)是對稱聯(lián)合分布的。目前，振蕩楊表與徘徊楊表已經(jīng)成為研究匹配、劃分等組合結(jié)構(gòu)

3、的性質(zhì)以及計(jì)數(shù)等問題的強(qiáng)有力工具。
　　 著名的Chung-Feller定理是計(jì)數(shù)組合學(xué)中的一個(gè)經(jīng)典結(jié)果，其內(nèi)容可敘述為：2n長的自由Dyck路中缺陷數(shù)的分布是均勻的。此結(jié)果是MazMahon1909年首次發(fā)現(xiàn)的。而該定理的命名源于Chung與Feller1949年的工作，他們重新發(fā)現(xiàn)并用分析的方法證明了該定理。之后，這個(gè)定理被廣泛研究。迄今，自由Dyck路上的Chung-Feller定理已經(jīng)有了多種不同的證明方法。例如：Ran

4、ey，Narayana，Dershowitz與Zaks等人分別利用循環(huán)引理或循環(huán)路給出了證明；Callan，Jewett與Ross等人通過構(gòu)造雙射加以證明。此外，很多學(xué)者還著力于研究該定理的推廣形式。例如：2001年，Woan發(fā)現(xiàn)了自由Dyck路上另一個(gè)均勻分布的參數(shù)：絕對最小長度；同年，Shapiro研究了特定的Motzkin路中絕對最小長度的均勻分布問題；游森棚等人2005年通過對不同格路生成函數(shù)泰勒展式的研究，既得到了該定理的一種

5、加細(xì)形式又發(fā)現(xiàn)了賦權(quán)自由Schroder路上的Chung-Feller性質(zhì)；2007年，陳永川等人定義了雙根平面樹中的蝴蝶分解，借此給出了Chung-Feller定理以及賦權(quán)自由Schroder路上Chung-Feller性質(zhì)的另一種全新的證明方法；最近，馬君與葉永南又研究了三類特殊的格路上缺陷數(shù)與絕對最小長度這兩個(gè)參數(shù)的均勻分布問題。
　　 在本篇論文中，我們主要研究了不交自由Dyck路、自由m-Schroder路、不完整自由

6、k-Dyck路等不同格路的計(jì)數(shù)以及它們關(guān)于不同參數(shù)的均勻分布問題。
　　 在第二章中，我們得到了k-不交自由Dyck路的計(jì)數(shù)公式。該公式是通過構(gòu)造k-不交自由Dyck路與有限制的平面分拆之間的一一對應(yīng)，借助Stanley給出的限制行數(shù)列數(shù)與最大部分值的平面分拆的計(jì)數(shù)公式得到的。當(dāng)限定k取2時(shí)，我們發(fā)現(xiàn)2-不交自由Dyck路與Callan給出的固定塊數(shù)的不交劃分的計(jì)數(shù)是相同的。借助徘徊楊表，我們建立了2n長的2-不交自由Dyck路

7、與有n+1個(gè)塊的[2n+1]上的不交劃分這兩個(gè)集合之間的一個(gè)雙射。此外，根據(jù)Labelle合并算法，我們找到了與2-不交自由Dyck路對應(yīng)的單條Dyck路的刻畫方式。
　　 在第三章中，一方面，我們研究了自由m-Schroder路關(guān)于缺陷數(shù)與絕對最小長度這兩個(gè)參數(shù)的均勻分布問題。我們的結(jié)果統(tǒng)一并且擴(kuò)展了之前關(guān)于自由Dyck路、自由k-Dyck路以及自由Schroder路等不同格路的Chung-Feller性質(zhì)，有著更為廣泛的意義

8、。特別地，我們得到了一個(gè)非常簡潔直觀的結(jié)果，稱之為缺陷引理。該引理包含了比循環(huán)引理更多的信息，因此可以看作是循環(huán)引理的推廣。在本文中，缺陷引理是發(fā)現(xiàn)并證明賦權(quán)自由m-Schroder路上關(guān)于缺陷數(shù)Chung-Feller性質(zhì)的有力工具。并且我們找到了限制斜步個(gè)數(shù)的m—Schroder路計(jì)數(shù)的一個(gè)更簡單的組合證明。另一方面，我們發(fā)現(xiàn)了一種新的方法來證明自由Dyck路中絕對最小長度的均勻分布問題。
　　 在第四章中，我們得到了固定類

9、型的不完整k-Dyck路的計(jì)數(shù)公式，并且給出了原始的Chung-Feller定理的另一種加細(xì)形式，即在給定類型的自由k-Dyck路中缺陷數(shù)的分布是均勻的。此外，我們建立了泊車函數(shù)與集合[n]上的有根森林之間的一個(gè)雙射，并且借助固定類型的k-Dyck路的計(jì)數(shù)公式得到了不交劃分、泊車函數(shù)以及有根森林等組合結(jié)構(gòu)中的一系列計(jì)數(shù)結(jié)果。
　　 在第五章中，我們從另外一個(gè)角度重新考慮經(jīng)典的Chung-Feller定理，即將自由Dyck路看作從