排列和Fibonacci字上的Foata變換.pdf

1、Foata第一基本變換和Foata第二基本變換是組合學(xué)中的兩個(gè)經(jīng)典變換。Foata第一基本變換是Lyndon展開的逆，它的基本作用是將字的勝位數(shù)轉(zhuǎn)換為字的下降數(shù)。Foata第二基本變換的基本作用是將字的主指標(biāo)轉(zhuǎn)換為字的逆序數(shù)，已經(jīng)被廣泛推廣到其他組合對象上，比如r-染色字，匹配，集合分拆，標(biāo)準(zhǔn)楊表，月亮多聯(lián)骨牌等。
　　本文的主要貢獻(xiàn)是研究Foata的這兩個(gè)基本變換在排列和Fibonacci字上的性質(zhì)。一方面我們研究對稱群上的主理

2、想（關(guān)于布呂阿序）在Foata第二基本變換作用下的不變性質(zhì)，另一方面我們利用Foata第一基本變換研究Fibonacci字上的歐拉對。同時(shí)我們還利用韓國牛的一個(gè)Foata-型雙射來研究對稱群上的主理想（關(guān)于弱序）的不變性質(zhì)。
　　本文共由四章組成，其組織如下:
　　在第一章中，我們首先介紹Foata第一基本變換和Foata第二基本變換的背景，然后介紹一些常用的定義，包括四種常見的統(tǒng)計(jì)量、Fibonacci字以及弱序和布呂阿序

3、。最后我們簡要概括該文的主要內(nèi)容和結(jié)構(gòu)。
　　在第二章中，我們研究對稱群上的主理想（關(guān)于布呂阿序）在Foata第二基本變換下的的不變性質(zhì)。我們的主要貢獻(xiàn)是給出主理想在Foata第二基本變換下不變時(shí)的一個(gè)刻畫，主要思路如下:首先，對于任意的主理想，我們根據(jù)該主理想中元素的最末位對這個(gè)主理想進(jìn)行分類，進(jìn)而求出每一類的極大元的具體形式;其次，我們得出主理想在Foata第二基本變換下不變時(shí)的極大元必須是一個(gè)132-禁排，進(jìn)一步得到主理想不

4、變時(shí)極大元的刻畫;最后，我們證明一個(gè)主理想在Foata第二基本變換下不變等價(jià)于它在韓國牛的Foata-型雙射下也不變。
　　在第三章中，我們研究韓國牛的Foata-型雙射作用下主理想（關(guān)于弱序）的不變性質(zhì)。我們同樣也給出主理想在韓國牛的Foata-型雙射下不變時(shí)的一個(gè)刻畫。為此我們構(gòu)造了一個(gè)集合，記為Ln。首先我們分析給出Ln中的排列以n開頭時(shí)該排列的刻畫，接著我們根據(jù)Ln中排列從右至左的極大元的個(gè)數(shù)分別給出這個(gè)排列的刻畫，基于這

5、些結(jié)果我們證明了一個(gè)主理想在韓國牛的Foata-型雙射下不變當(dāng)且僅當(dāng)它的極大元在這個(gè)集合Ln中。最后我們給出一個(gè)區(qū)間在韓國牛的Foata-型雙射作用下不變的一個(gè)充分條件。
　　在第四章中，我們研究Fibonacci字上的歐拉對，解決了Sagan和Savage所提出的一個(gè)問題。我們推廣Steingrímsson的雙射得到一個(gè)映射，可視為Foata第一基本變換的一個(gè)變形。我們?nèi)匀荒軌蜃C明它將下降數(shù)轉(zhuǎn)換為到勝位數(shù)，而且在某個(gè)特殊的集合上