分拆與匹配中的有禁模式.pdf

1、近幾年里，有禁分拆與有禁匹配被廣泛地研究，越來越多的組合數(shù)學(xué)中的經(jīng)典結(jié)果被推廣至分拆與匹配的研究中.本文主要研究了幾類有禁分拆與有禁匹配的計數(shù)問題.文中我們主要使用了構(gòu)造雙射的方法和傳遞矩陣法，并借助計算機開發(fā)了一個Maple軟件包來生成特定序列所滿足的遞歸方程.
　　 本文共由三章組成.其組織如下：
　　 在第一章中，我們簡要敘述了一下該文的研究背景，并介紹了部分文中使用的基本定義和常見符號.
　　 在第二章中

2、，我們主要考慮雙邊對稱的3－noncrossing分拆的計數(shù)問題.Chenet al.首次提出了集合分拆中的k-crossing和k-nesting的概念，并通過vacillatingtableaux與分拆之間的一個雙射來證明這兩個統(tǒng)計量對稱聯(lián)合分布的性質(zhì).該雙射推廣了全排列和標準楊表對之間經(jīng)典的RSK對應(yīng)，并同樣具備RSK對應(yīng)所具備的對稱性.基于該雙射的對稱性質(zhì)和其與格路之間的關(guān)系，并借用迭代級數(shù)的常數(shù)項理論，我們通過開發(fā)了一個針對二

3、維平面內(nèi)vacillaring lattice walk計數(shù)問題的Maple軟件包，以此得到集合[n]中所有3-noncrossing分拆的個數(shù)所滿足的遞歸關(guān)系式.該軟件包適用于一類相似的vacillating lattice walk的計數(shù)問題.
　　 在第三章中，我們主要考慮可通過k次堆棧排序的分拆和匹配的計數(shù)問題.我們刻畫了可通過k次堆棧排序的分拆與匹配的主要性質(zhì).一個分拆足可通過k次堆棧排序的當且僅當它的序列表示避免23

4、…(k+2)1-模式.我們計算了可通過k次堆棧排序的無相交分拆、無相交匹配和無嵌套匹配這三類分拆的生成函數(shù)，并通過構(gòu)造雙射的方法給出了七次堆棧排序的分拆的生成函數(shù)的一個公式.該公式比Mansour和Severini通過核方法所得到的公式更簡單直接.利用經(jīng)典的傳遞矩陣法，我們證明了可通過k次堆棧排序的匹配的個數(shù)的生成函數(shù)足有理的.
　　 最后，我們在附錄中給出第二章中所提到的Maple軟件包及該軟件包應(yīng)用于hesitating l