組合變換在等式、多項(xiàng)式及簡(jiǎn)單圖中的應(yīng)用.pdf

1、利用組合方法給出某些數(shù)學(xué)問(wèn)題簡(jiǎn)潔直觀的證明是組合數(shù)學(xué)研究的熱點(diǎn)課題。其本質(zhì)就是構(gòu)造組合結(jié)構(gòu)，尋找適當(dāng)?shù)慕M合變換。在本文中，一方面，我們將這種方法應(yīng)用于兩個(gè)等式，即Simons等式和Munarini等式，給出了這兩個(gè)等式的組合解釋。進(jìn)一步地，在Munarini等式的證明過(guò)程中涉及的組合技巧也可用于證明Boros-Moll多項(xiàng)式系數(shù)的正性。另一方面，作為組合變換的另一個(gè)應(yīng)用，本文證明了一類(lèi)簡(jiǎn)單圖中交叉數(shù)和嵌套數(shù)是對(duì)稱(chēng)聯(lián)合分布的。
　　

2、 Simons等式是Simons通過(guò)重復(fù)求導(dǎo)得到的一個(gè)關(guān)于二項(xiàng)式系數(shù)的等式。對(duì)該等式的證明包括Chapman給出的生成函數(shù)法，Prodinger給出的柯西積分公式法以及Wang和Sun給出的算子法。Hirschhorn指出Simons等式實(shí)際上是定義在超幾何級(jí)數(shù)2F1上的Pfaff等式的一種特殊情況。而對(duì)于Pfaff等式的組合證明，Labelle和Yeh在他們的文章中已經(jīng)給出。本文通過(guò)構(gòu)造兩種賦權(quán)組合結(jié)構(gòu)上的組合變換，即賦權(quán)自由Dyc

3、k路和賦權(quán)自由Schroder路上的組合變換，給出了Simons等式另一種更加形象直觀的組合解釋。
　　 依照Prodinger的方法，Munarini得到了Simons等式的一般化形式，稱(chēng)之為Munarini等式，該等式同時(shí)也足Pfaff等式的一般化形式。對(duì)Munarini等式的某些特殊情況，Shattuck給出了基本的雙射證明。應(yīng)用Labelle和Yeh在證明Pfaff等式過(guò)程中的技巧，我們給出了Munarini等式的組合解

4、釋。
　　 本文還給出了Boros-Moll多項(xiàng)式系數(shù)正性的組合證明。Boros-Moll多項(xiàng)式足在求一個(gè)四次積分的過(guò)程中產(chǎn)生的，它與一類(lèi)特殊的Jacobi多項(xiàng)式密切相關(guān)。Amdeberhan和Moll給出了有關(guān)該多項(xiàng)式表達(dá)式多種不同的證明。Boros和Moll曾經(jīng)給出該多項(xiàng)式系數(shù)正性的證明，但他們的證明是借助Ramanujan基本定理實(shí)現(xiàn)的。此外，Boros-Moll多項(xiàng)式系數(shù)序列還有其它組合性質(zhì)，如單峰性和對(duì)數(shù)凹性。利用組合

5、方法來(lái)詮釋這些性質(zhì)已成為組合學(xué)中一個(gè)有趣的研究方向。
　　 研究一類(lèi)簡(jiǎn)單圖中交叉數(shù)和嵌套數(shù)的對(duì)稱(chēng)聯(lián)合分布問(wèn)題是該論文中組合變換的另一個(gè)應(yīng)用。1983年，De Sainte-Catherineit明了在集合[2n]的所有匹配中，2-交叉和2v嵌套是等分布的。之后，Klazar推廣了該結(jié)論，證明了含有r個(gè)2－交叉、s個(gè)2－嵌套的匹配的個(gè)數(shù)等于含有r個(gè)2－嵌套、s個(gè)2－交叉的匹配的個(gè)數(shù)。近來(lái)，關(guān)于圖中交叉和嵌套的對(duì)稱(chēng)聯(lián)合分布問(wèn)題又重新

6、引起了廣大學(xué)者的研究興趣。2007年，以RSK算法為基礎(chǔ)，Chen等證明了在集合[n]的所有劃分或集合[2n]的所有匹配中，交叉數(shù)和嵌套數(shù)是對(duì)稱(chēng)聯(lián)合分布的。同時(shí)，通過(guò)考慮Fevers圖表的填充方式，Krattenthaler也證明了這一結(jié)論。本文通過(guò)構(gòu)造一種新的算法，即改進(jìn)的RSK算法，推廣了該結(jié)論。
　　 在本篇論文中，我們主要討論組合變換在兩類(lèi)問(wèn)題中的應(yīng)用。其中之一是給出Simons等式、Munarini等式以及Boros-

7、Moll多項(xiàng)式系數(shù)正性的組合解釋。另一個(gè)是證明在每個(gè)點(diǎn)左度都不超過(guò)1的簡(jiǎn)單圖中，交叉數(shù)和嵌套數(shù)是對(duì)稱(chēng)聯(lián)合分布的。我們主要得到了以下兩個(gè)方面的結(jié)果。
　　 本文的第二章論述了我們的第一個(gè)結(jié)果，也就足組合地解釋了Simons等式、Munarini等式以及Boros-Moll多項(xiàng)式系數(shù)的正性。對(duì)于Simons等式，其組合變換是以自由Dyck路、自由Schroder路以及在賦權(quán)自由Schroder路上的一個(gè)對(duì)合為基礎(chǔ)的。而對(duì)于Munar

8、ini等式和Boros-Moll多項(xiàng)式系數(shù)的正性，其組合變換是以Foata和Labelle給出的一個(gè)關(guān)于Meixner endofunctions和雙色排列的對(duì)應(yīng)，以及Labelle和Yeh用于證明Pfaff等式的方法為基礎(chǔ)的。
　　 本文的第三、四章闡述了我們的第二個(gè)主要結(jié)論。在第三章中，我們給出了一個(gè)改進(jìn)的RSK算法。利用此算法，我們構(gòu)造了某個(gè)有序集合上的字ω與存在限制條件的有序楊表對(duì)(P(ω)，Q(ω))之間的一個(gè)一一對(duì)應(yīng)

9、。此外，在本章中我們還證明了以下結(jié)論：ω的最長(zhǎng)遞增子序列的長(zhǎng)度等于P(ω)的列數(shù)；ω的最長(zhǎng)遞減子序列的長(zhǎng)度等于P(ω)的行數(shù)。
　　 以第三章中改進(jìn)的RSK算法為基礎(chǔ)，在第四章中，我們主要證明了在每個(gè)點(diǎn)左度都不超過(guò)1的簡(jiǎn)單圖中，交叉數(shù)和嵌套數(shù)是對(duì)稱(chēng)聯(lián)合分布的。這個(gè)問(wèn)題是通過(guò)構(gòu)造每個(gè)點(diǎn)左度都不超過(guò)1的簡(jiǎn)單圖和空型的有效徘徊楊表之間的雙射得以解決的。事實(shí)上，對(duì)于每個(gè)點(diǎn)左度都不超過(guò)1的簡(jiǎn)單圖構(gòu)成的圖類(lèi)，如果固定左端點(diǎn)和右端點(diǎn)集合，我們