格路徑與平面樹上的組合學(xué).pdf

1、組合結(jié)構(gòu)是研究組合數(shù)學(xué)的基礎(chǔ)，在組合計(jì)數(shù)領(lǐng)域中占有重要的地位。格路徑和平面樹是應(yīng)用最為廣泛的兩種組合結(jié)構(gòu)，并且兩者之間存在著非常緊密的聯(lián)系。本文主要研究了幾類格路徑以及平面樹的計(jì)數(shù)問題。 首先我們給出了Shapiro，Woan和Getru利用Riordan排列的方法研究的一個(gè)關(guān)于Catalan數(shù)和序列(1，4，4<'2>，4<'3>…．)的矩陣等式的組合證明。通過構(gòu)造帶有一條提升線的賦權(quán)局部Motzkin路與自由Motzkin路

2、之間的雙射，我們得到了一類關(guān)于賦權(quán)Motzkin路和k≥2的序列(1，k，k<'2>，k<'3>,…．)的矩陣等式。進(jìn)一步，利用染色的Dyck路，我們給出了一類關(guān)于序列(1，t<'2>+t，(t<'2>+t)<'2>，…)的矩陣等式。 其次我們研究了平面樹的計(jì)數(shù)問題，提出了雙根樹的概念并給出了這類樹的Butterfly分解算法，且通過這種分解算法建立了雙根樹與自由Dyck路之間的雙射。由這個(gè)雙射可以很自然的導(dǎo)出一個(gè)關(guān)于Catal

3、an數(shù)和二項(xiàng)式系數(shù)的關(guān)系式。作為這個(gè)算法的又一個(gè)應(yīng)用，我們還構(gòu)造了葉子染色的雙根樹和自由Schroder路之問的雙射，而且給出了經(jīng)典的Chung-Feller定理及其多種推廣形式的組合證明，同時(shí)得到了兩個(gè)關(guān)于Dyck路和Schroder路的對合，并進(jìn)一步導(dǎo)出了一系列的奇偶性結(jié)果和組合恒等式。應(yīng)用Butterfly分解算法，我們還給出了Klazar關(guān)于平面樹上鏈條的生成函數(shù)的組合解釋，進(jìn)而揭示了n條邊的平面樹上鏈條的平均長度趨進(jìn)于n+9/

4、6。最后我們利用對于標(biāo)號平面樹的Chen算法，給出了一個(gè)關(guān)于平面森林的雙射，由此解釋了一類關(guān)于Narayana數(shù)的組合恒等式。 2002年，Alex Postnikov提出了一個(gè)關(guān)于多面體體積的Chan—Robbins-Yeun猜想的約簡規(guī)則的公開問題，并要求給出其組合證明。在Postnikov給出的用Catalan數(shù)計(jì)數(shù)的二叉樹的約簡規(guī)則基礎(chǔ)上，我們定義了新的單項(xiàng)式上的約簡規(guī)則，并通過建立雙射的方法證明了這些約簡規(guī)則與許多種類

5、的平面樹相關(guān)，其中包括完全對稱k叉樹、局部對稱k叉樹、對稱偶樹、對稱不交樹、Motzkin樹以及帶圈的平面樹。在證明過程中，我們歸納地使用了一種消除算法來對單項(xiàng)式上的約簡規(guī)則的終項(xiàng)進(jìn)行計(jì)數(shù)。同時(shí)我們還得到了包括3-Catalan數(shù)和Motzkin數(shù)在內(nèi)的許多計(jì)數(shù)性質(zhì)。 在本文的最后我們定義了一種新的組合結(jié)構(gòu)--2-二叉樹：根節(jié)點(diǎn)染黑色而其他節(jié)點(diǎn)染黑色或白色的有根二叉樹。我們研究了許多類2-二二叉樹并給出了它們與多種組合結(jié)構(gòu)之間的