排列表上的組合學(xué).pdf

1、本文主要研究了排列表上的組合性質(zhì)。我們建立了排列表、連接分拆和排列三者之間的對應(yīng)關(guān)系，研究了排列表的逆序數(shù)。我們將禁排的概念推廣到排列表上，得到了排列表的不同子類分別與Schroder路，Dyck路，集合分拆的對應(yīng)關(guān)系。我們證明了一些經(jīng)典的計數(shù)結(jié)果，如Stirling數(shù)，歐拉數(shù)等都可以用排列表的某些統(tǒng)計量給出。
　　 第一章簡要介紹了排列表相關(guān)的背景知識，包括排列表是如何從完全非負(fù)的格拉斯曼流形中得出的，排列表與不完全非對稱互斥

2、過程的聯(lián)系。
　　 在第二章中，我們首先回顧排列表的一個遞推關(guān)系，從遞推關(guān)系中我們可以看到排列表中某些統(tǒng)計量的分布。接著，我們給出排列表的不同表示，分別是全1表示，限制的0-1表示，選擇性表示和階梯形表示。我們將給出這些表示對于分析排列表中的統(tǒng)計量所起的不同作用。
　　 在第三章中，我們建立了n長的排列表與[n]={1，2，……，n}上的連接分拆之間的一一對應(yīng)，另外我們構(gòu)造了[n]上的連接分拆與排列之間的一一對應(yīng)。結(jié)合這

3、兩個對應(yīng)關(guān)系，我們建立了新的從n長的排列表到[n]上的連接分拆之間雙射，從而我們研究了排列表的一些組合性質(zhì)。
　　 在第四章中，我們發(fā)現(xiàn)并引入排列表上的逆序數(shù)這一統(tǒng)計量。利用Corteel和Nadeau的雙射，我們證明了排列表逆序數(shù)與排列中廣義樣式32-1是同分布的。這給出了Corteel和Nadeau提出的關(guān)于在排列表中尋找與排列中樣式32-1相對應(yīng)的統(tǒng)計量的問題的一種解答。作為特殊情況，我們可以看到逆序數(shù)為0的排列表其實就是

4、Corteel和Nadeau定義的L-Bell表。
　　 在第五章中，我們研究了排列表的某些子類，它們與Bell數(shù)以及長度為3的一些禁排緊密相關(guān)。利用第三章中排列表與連接分拆的對應(yīng)關(guān)系，我們發(fā)現(xiàn)不交分拆對應(yīng)于一類特殊的排列表，稱為不交排列表。我們給出不交排列表的遞推關(guān)系以及n+1長的不交排列表和2n長的Schroder路之間的雙射。進(jìn)一步地，我們引入不嵌套排列表的概念，我們發(fā)現(xiàn)不嵌套排列表也可以用Schroder數(shù)來計數(shù)，我們建