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

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

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

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

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

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