關于格路的計數以及均勻分布的一些研究.pdf

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

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

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

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

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

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

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

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

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