有根二色樹(shù)的計(jì)數(shù).pdf

1、摘 要組合數(shù)學(xué)主要研究某組離散對(duì)象中 滿足一定條件的格局的存在性、 構(gòu)造 性、 及計(jì)數(shù)等問(wèn) 題. 由于 計(jì)算機(jī)的迅速發(fā)展， 組合數(shù)學(xué)獲得了 新的生命力， 成 為數(shù)學(xué)的一個(gè) 重要分支. 組合計(jì)數(shù)又是組合數(shù)學(xué)中一個(gè)最基本的研究方向， 主要研究滿足一定條件的安排方式的數(shù)目 和計(jì)算問(wèn) 題. 組合計(jì)數(shù)的方法之一 是在兩個(gè)由 離散結(jié)構(gòu)組成的集合之間 找到一個(gè)算法， 建立一個(gè)雙射， 然 后求出 它們 在 生成函 數(shù) 上的 關(guān)系 式.自 從M . F

2、 i e l d l e r 和7 . S e d l a c e k [ 1 0 ] 首先討 論了 完 全二部圖中標(biāo)號(hào)生成樹(shù)的 計(jì)數(shù)以來(lái)，一些文章從不同角度、 用不同方法對(duì)此 進(jìn)行了新的闡述. 本文主要是用另一個(gè)方法就完全二部圖中的有根生成樹(shù)和 有根生成森林及二色有序樹(shù)進(jìn)行了 討論， 大致分為五節(jié)， 簡(jiǎn)單介紹如下:第一節(jié)討論完全二部圖中有根生成樹(shù)的計(jì)數(shù) 樹(shù)上的一個(gè)算法. 該算法指出 一個(gè)有根二色樹(shù)可 先提出了有根二色 地分解成幾個(gè)

3、高度為 1 或2 的有根二 色樹(shù)， 反之，由 幾個(gè)高度為 I 或2 的有根二色樹(shù)可以 合成一個(gè) 有 根二色樹(shù). 利用這個(gè)組合雙射， 便推出了 有根生成樹(shù)的生成函數(shù). 該節(jié)其次 引 人 第 二 個(gè) 算 法 ， 證 明 了 在 有 根 二 色 樹(shù) 與 高 度 為‘ 的 有 根 二 色 樹(shù) 之 f , ) l # 在 一 個(gè) 對(duì) 應(yīng) 關(guān) 系 · 由 這 個(gè) 算 法 直 接 計(jì) 算 了 幾 類(lèi) 特 殊 的 有 根 產(chǎn) 成 樹(shù) 的 個(gè)

4、 數(shù) · r第 二 節(jié) 討 論 完 全 二 部 圖 中 有 根 生 成 森 林 的 計(jì) 數(shù) · I T . L . A u s t i n [ 2 ] 利 用L a - g r a n g e 公式 首先求出了 這個(gè)問(wèn) 題中 的兩種特殊情況 該節(jié)先利用與第一 節(jié)相類(lèi) 似的方法對(duì)其中之一進(jìn)行了 證明. 完全二部圖和完全圖中有根生成樹(shù) M . Z . A b u - S b e i h [ 1 1 用一種新

5、的方法證明了 該節(jié)把該方法推廣到完全二部圖 的有根生成森林， 從而求出了一般情第三節(jié)討論二色有序樹(shù) 節(jié)中， 提出了二色有序樹(shù)上的兩個(gè)算法 一個(gè)指出 一個(gè)二色有序樹(shù) 地分解成一個(gè)全由僅含一邊的有根二色樹(shù) 組成的森林。 第二個(gè)指出 一個(gè)二色有序樹(shù)可被一個(gè)由 幾個(gè)高度為 I 的 二色有 序 樹(shù)組成的森林唯一確h a 直 接利用這兩個(gè)結(jié)論， 便很容易地解出了 二 色有序 樹(shù)上的各類(lèi)計(jì)數(shù)問(wèn) 題。 r第四節(jié)主要是在第三節(jié)提出的第一個(gè)算法的基礎(chǔ)上，討

6、論二色有序樹(shù)上 的 對(duì)合. 這些對(duì)合的共同 點(diǎn)是它們 作用在一個(gè)二色有序樹(shù)上之后， 可使得內(nèi)點(diǎn) 變成葉子、 葉 子變成內(nèi) 點(diǎn)。第 五 節(jié) 主 要 是 提 出 了 有 序 樹(shù) 和 二 色 有 序 樹(shù) 之 間 的 一 個(gè) 組 合 雙 射 . 八人 周 知， 著名的N a r a y a n a 數(shù) [ 1 9 ] 計(jì)算了n + 1 個(gè)非標(biāo)號(hào)頂點(diǎn)上的含k 個(gè)葉 于的有序 樹(shù)的個(gè)數(shù)。 這個(gè)數(shù)與二色有序樹(shù)的個(gè)數(shù)有相似之處， 這說(shuō)明在這兩類(lèi)完全不同

7、 的有序樹(shù)之間 應(yīng)存在一個(gè)內(nèi) 在聯(lián)系. 這節(jié)利用第三節(jié)中的第一個(gè)算法對(duì)這種 相似性給出了 一個(gè)巧妙的組合雙射. 該雙射指出: 任一個(gè)二色有序樹(shù)唯一地對(duì) 應(yīng)于一個(gè)有序樹(shù)，使得二色有序樹(shù)中 高度為奇數(shù)的頂點(diǎn)變成 樹(shù)的葉子嘩 為 偶 數(shù) 的 頂 點(diǎn) 變 成 有 序 樹(shù) 的 內(nèi) 點(diǎn) ，關(guān)鍵詞: 計(jì)數(shù)， 生成 圖， 完全二部圖.、 一 產(chǎn) 合 贏 對(duì) 合 ， 生 成 預(yù) 有 } 俞 杯 森 林 ， 完 鑒有根二色樹(shù)的計(jì)數(shù) 劉春林u n l a b

8、 e l l e d o r d e r e d t r e e s o n n +I v e r t i c e s w i t h k l e a v e s . I n f a c t , t h i s n u m b e r i s e q u a l t ot h e n u m b e r o f b i c o l o u r e d o r d e r e d t r e e s

9、 w i t h s o m e g i v e n v e r t i c e s . T h i s s i m i l a r i t y i n d i c a t e st h e r e s h o u l d b e a n i n t r i n s i c r e l a t i o n b e t w e e n t h e s e t w o d i f f e r e n t k

10、 i n d s o f r o o t e d t r e e s . T h i ss e c t i o n e x p o s e s t h i s h i d d e n r e l a t i o n b y u s i n g t h e f i r s t a l g o r i t h m i n s e c t i o n 3 a n d s o m e o t h e r t

11、 e c h n i q u e s . T h e b i j e c t i o n p r o v e s t h a t a b i c o l o u r e d o r d e r e d t r e e c a n b e t u r n e d i n t o a n o r d e r e d t r e e s u c h t h a t v e r t i c e s w i t

12、 h e v e n h e i g h t a r e t u r n e d i n t o i n t e r n a l v e r t i c e s a n d o d d h e i g h tv e r t i c e s i n t o l e a v e sK e y w o r d s : e n u m e r a t i o n , e x p o n e n t i a l g

13、e n e r a t i n g f u n c t i o n , b i j e c t i o n , i n v o l u t i o n , s p a n n i n g s u b g r a p h , r o o t e d t r e e , f o r e s t , c o m p l e t e g r a p h , c o m p l e t e b i p a r t i t e