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

1、摘 要組合數(shù)學(xué)主要研究某組離散對象中 滿足一定條件的格局的存在性、 構(gòu)造 性、 及計數(shù)等問 題. 由于 計算機(jī)的迅速發(fā)展， 組合數(shù)學(xué)獲得了 新的生命力， 成 為數(shù)學(xué)的一個 重要分支. 組合計數(shù)又是組合數(shù)學(xué)中一個最基本的研究方向， 主要研究滿足一定條件的安排方式的數(shù)目 和計算問 題. 組合計數(shù)的方法之一 是在兩個由 離散結(jié)構(gòu)組成的集合之間 找到一個算法， 建立一個雙射， 然 后求出 它們 在 生成函 數(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)號生成樹的 計數(shù)以來，一些文章從不同角度、 用不同方法對此 進(jìn)行了新的闡述. 本文主要是用另一個方法就完全二部圖中的有根生成樹和 有根生成森林及二色有序樹進(jìn)行了 討論， 大致分為五節(jié)， 簡單介紹如下:第一節(jié)討論完全二部圖中有根生成樹的計數(shù) 樹上的一個算法. 該算法指出 一個有根二色樹可 先提出了有根二色 地分解成幾個

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

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

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

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

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