B型集合分拆的組合性質(zhì)研究.pdf

1、集合分拆是組合學(xué)中的經(jīng)典和廣泛的研究對(duì)象之一,它主要針對(duì)一個(gè)集合的分拆的各種組合結(jié)構(gòu)進(jìn)行考察和研究。在過(guò)去,人們關(guān)心具有特殊組合性質(zhì)的集合分拆,考慮其計(jì)數(shù)、集合分拆的格結(jié)構(gòu),以及定義在集合分拆上的一些統(tǒng)計(jì)量的分布情況等等。1995年,代數(shù)組合學(xué)家Reiner最先研究B型集合分拆。他當(dāng)時(shí)的工作主要是關(guān)于非交集合分拆的格結(jié)構(gòu)的B型模擬。然而,B型集合分拆自身的研究,包括各種特殊的B型集合分拆的計(jì)數(shù)、塊數(shù)的漸近分布、分拆的極小相交等性質(zhì),幾乎

2、沒(méi)有被關(guān)注。這篇論文填補(bǔ)這些空白,同時(shí)對(duì)經(jīng)典集合分拆的一些優(yōu)美性質(zhì)做B型模擬,其難點(diǎn)主要在于對(duì)B型集合分拆的組合結(jié)構(gòu)的深入理解,和對(duì)各種變量進(jìn)行創(chuàng)造性的B型模擬。
　　 本研究分為六個(gè)部分。第一章簡(jiǎn)介經(jīng)典集合分拆研究的發(fā)展,并簡(jiǎn)單回顧B型集合分拆的近期進(jìn)展。第二章主要介紹B型集合分拆的基本的計(jì)數(shù)結(jié)果和組合性質(zhì)。特別地,我們給出無(wú)零塊B型集合分拆個(gè)數(shù)的多種表達(dá)式。該個(gè)數(shù)在對(duì)B型分拆的組合性質(zhì)的研究中扮演重要角色。在隨后的兩章中,我

3、們研究B型集合分拆的子塊對(duì)的個(gè)數(shù)的漸近性質(zhì)。我們?cè)诘谌陆o出子塊對(duì)個(gè)數(shù)的期望與方差的準(zhǔn)確表達(dá)式,并利用復(fù)分析知識(shí)給出它們的漸近表達(dá)式。同時(shí)我們也對(duì)無(wú)零塊的B型分拆做類(lèi)似研究。這些表達(dá)式都是新結(jié)果。在第四章中我們證明,不論考慮全部B型分拆還是無(wú)零塊B型分拆,其子塊對(duì)的個(gè)數(shù)的極限分布都是正態(tài)的。這些也都是新結(jié)果。我們證明極限正態(tài)分布主要基于一個(gè)已有的判別準(zhǔn)則。簡(jiǎn)單地說(shuō),如果隨機(jī)變量的方差趨近于無(wú)窮大,而相應(yīng)的生成多項(xiàng)式只有實(shí)數(shù)根,則其極限分

4、布正態(tài)。前者我們?cè)诘谌轮幸羊?yàn)證,后者借助第二章中給出的遞歸關(guān)系式可以證明。第五章考察集合分拆的極小相交性。我們給出一個(gè)公式計(jì)數(shù)極小相交的B型集合分拆的r元有序組,同時(shí)也對(duì)無(wú)零塊B型集合分拆做類(lèi)似研究。這些公式都是新結(jié)果,它們可以被看做是Pittel對(duì)經(jīng)典集合分拆所做的計(jì)數(shù)公式的B型模擬。然而,研究B型集合分拆時(shí),其組合設(shè)置相對(duì)于研究經(jīng)典分拆中的設(shè)置來(lái)說(shuō)更加復(fù)雜。特別地,我們得到Benoumhani公式的一個(gè)新證明,這個(gè)公式是經(jīng)典的Do

5、bi(n)ski公式的B型模擬。第六章,我們介紹集合分拆中單點(diǎn)和鄰對(duì)的對(duì)稱(chēng)分布結(jié)果。Callan曾對(duì)此給出一個(gè)美妙的組合算法,它誘導(dǎo)出該對(duì)稱(chēng)性的對(duì)合證明。我們?cè)噲D探索B型分拆是否具有類(lèi)似漂亮的對(duì)稱(chēng)性質(zhì)。為此,我們?cè)贐型分拆中合理定義單點(diǎn)對(duì)和鄰點(diǎn)對(duì)的概念,并證明無(wú)零塊B型分拆中單點(diǎn)對(duì)和鄰點(diǎn)對(duì)的對(duì)稱(chēng)分布性。特別地,我們得到Bernhart定理的B型模擬。最后包含兩個(gè)附錄。附錄A由一些有關(guān)數(shù)學(xué)分析的引理構(gòu)成,它們?cè)诘诙潞偷谌轮袝?huì)被用到；在