（应用数学专业论文）有根二色树的计数.pdf

有根二色树的计 数 刘春林 ab s t r a c t c o m b i n a t o r i c s d e a l s w i t h t h e e x i s t e n c e , c o n s t r u c t i o n , a n d e n u m e r a t i o n o f s o m e s p e c i a l s t r u c t u r e s s a t i s f y i n g c e r t a i n c o n d i t i o n s o n a s e t o f d i s c r e t e o b j e c t s . s i n c e t h e f u n d a m e n t a l r o l e t h a t c o m b i n a t o r i c s p l a y s a s a t o o l i n c o m p u t e r s c i e n c e a n d r e l a t e d a r e a s , c o m b i n a t o r i c s h a s g r o w n e x p l o s i v e l y a n d e n o r m o u s l y . e n u m e r a t i v e c o m b i n a t o r i c s i s a n i m p o r t a n t b r a n c h o f c o mb i n a t o r i c s a n d i s c o n c e rne d w i t h t h e n u m b e r o f e l e me n t s o f a fi n i t e s e t . on e me t h o d u s e d i n e n u m e r a t i v e c o m b i n a t o r i c s i s fi n d i n g a n a l g o r i t h m b e t w e e n s e t s o f d i s c r e t e o b j e c t s , e s t a b l i s h i n g a b ij e c t i o n , a n d t h e n d e r i v i n g t h e i r e x p o n e n t i a l g e n e r a t i n g f u n c t i o n s . s i n c e m. f i e l d l e r a n d j . s e d l a c e k 1 0 fi r s t d i s c u s s e d t h e e n u m e r a t i o n f o r l a b e l l e d s p a n n i n g t r e e s o f t h e c o m p l e t e b i p a rt i t e g r a p h , l o t s o f r e s e a r c h p a p e r s h a v e a p p e a r e d t o d i s c u s s t h e p r o b l e m f r o m d i s t i n c t v i e w - p o i n t s b y u s i n g d i f f e r e n t m e t h o d s . t h i s p a p e r , u s i n g a n e w m e t h o d , w a n t s t o d e a l w i t h t h e e n u m e r a t i o n f o r r o o t e d s p a n n i n g t r e e s a n d r o o t e d s p a n n i n g f o r e s t s o f t h e c o m p l e t e b i p a rt i t e g r a p h , a n d b i c o l o u r e d o r d e r e d t r e e s , w h i c h a r e c o n t a i n e d i n fi v e s e c t i o n s . s e c t i o n 1 d i s c u s s e s t h e e n u m e r a t i o n o f r o o t e d s p a n n i n g t r e e s o f t h e c o m p l e t e b i p a r t i t e g r a p h . b y u s i n g a b ij e c t i o n w h i c h p o i n t s o u t t h a t t h e r e i s a o n e - t o - o n e c o r r e s p o n d e n c e b e - t w e e n r o o t e d b i c o l o u r e d t r e e s a n d f o r e s t s o f s e v e r a l o n e s w h o s e h e i g h t s n o t b i g g e r t h a n 2 , t h i s s e c t i o n d e r i v e s t h e e x p o n e n t i a l g e n e r a t i n g f u n c t i o n f o r t h e r o o t e d s p a n n i n g t r e e s . a n - o t h e r b ij e c t i o n i s a l s o p r o p o s e d t o p r o v e t h a t t h e r e i s a o n e - t o - o n e c o r r e s p o n d e n c e b e t w e e n r o o t e d b i c o l o u r e d t r e e s a n d f o r e s t s o f s e v e r a l o n e s w i t h h e i g h t b e i n g 1 . wi t h t h i s r e s u l t , s o m e s p e c i a l t y p e s o f r o o t e d b i c o l o u r e d t r e e s a r e e n u m e r a t e d . s e c t i o n 2 i s c o n c e rn e d w i t h t h e e n u m e r a t i o n o f r o o t e d s p a n n i n g f o r e s t s o f t h e c o m p l e t e b i p a r t i t e g r a p h . tl . a u s t i n 2 s o l v e d t w o s p e c i a l c a s e b y u s i n g l a g r a n g e f o r m u l a . t h i s s e c t i o n fi r s t p r o v e s o n e c a s e b y a m e t h o d s i m i l a r t o t h a t i n s e c t i o n 1 . m. z . a b u - s b e i h i c a l c u l a t e d t h e n u m b e r o f r o o t e d s p a n n i n g t r e e s o f t h e c o m p l e t e g r a p h a n d t h e c o m p l e t e b i - p a r t i t e g r a p h . t h i s s e c t i o n e x t e n d s t h i s m e t h o d t o s o l v e t h e g e n e r a l c a s e o f t h e e n u m e r a t i o n p r o b l e m s e c t i o n 3 d i s c u s s e s b i c o l o u r e d o r d e r e d t r e e s b y t w o n e w a l g o r i t h m s . t h e fi r s t o n e p o i n t s o u t t h a t t h e r e i s a b ij e c t i o n b e t w e e n t h e s e t o f b i c o l o u r e d o r d e r e d t r e e s a n d t h e s e t o f f o r e s t s c o n s i s t i n g o f b i c o l o u r e d o r d e r e d t r e e s w h i c h c o n t a i n s o n l y o n e e d g e . t h e s e c o n d o n e s a y 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 d e c o m p o s e d i n t o a f o r e s t o f s e v e r a l o n e s w h o s e h e i g h t s b e i n g 1 , a n d o n t h e c o n t r a r y , t h e f o r e s t c a n b e m e r g e d i n t o t h e b i c o l o u r e d o r d e r e d t r e e . f r o m t h e s e t w o r e s u l t s , t h i s s e c t i o n s o l v e s t h e e n u me r a t i o n o f r o o t e d b i c o l o u r e d t r e e s w i t h v a r i o u s t y p e s . s e c t i o n 4 g i v e s s e v e r a l i n v o l u t i o n s o n b i c o l o u r e d o r d e r e d t r e e s w i t h t h e fi r s t a l g o r i t h m i n s e c t i o n 3 a s a b a s i s . u n d e r t h e s e i n v o l u t i o n s , 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 rne d i n t o a n o t h e r o n e s u c h t h a t i n t e rna l v e r t i c e s a r e t u rn e d i n t o l e a v e s , a n d v i c e v e r s a . s e c t i o n 5 p r o p o s e s a b ij e c t i o n b e t w e e n t h e s e t o f o r d e r e d t r e e s a n d t h e s e t o f b i c o l o u r e d o r d e r e d t r e e s . a s w e l l k n o w n , t h e f a m o u s n a r a y a n a n u m b e r f 1 9 c o u n t t h e n u m b e r o f 有根二色树的计数 刘春林 u n l a b 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 o t 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 w i t h s o m e g i v e n v e rt 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 s t 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 i n d s o f r o o t e d t r e e s . t h i s s 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 fi 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 e c h n i q u e s . t h e b ij 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 rn 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 h e v e n h e i g h t a r e t u rn e d i n t o i n t e rna l v e rt i c e s a n d o d d h e i g h t v e rt i c e s i n t o l e a v e s k 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 e n e r a t i n g f u n c t i o n , b ij 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 g r a p h . i i i 有根二色树的计数 刘春林 1前言 一 个图g 是指一个元素偶( v , e ) ， 记作g 二 ( v , e ) .v 是一 个集 合， 其元素 称作顶点，e 是无序积v 若v ( 川= v ( g ) , 到川c e ( g ) ， 则称h 是g 的 生成子图 . 图 的一个顶点 和边相继交替出 现的且点和边各互不相同的 有限非空序列,v = y o e l l . . . e k * 称 为一条( v 0 , v k ) 一 路， 其中v p 和v k 分别称为该路的起点和终点， 并称该路的长为 k 。 图g 中 两顶点u , 、 之间的 距离是指g 中最短的( u , v ) 一 路的 长， 记为d ( u , v ) . 若图g的任一对不同顶点之间均存在一条路，则称g为连通图.无圈连通图 称为树. 无圈图称为森林.由有根树组成的森林称为有根森林. 有根树中， 顶 点到根的距离称为该顶点的高度;树中所有顶点的高度的最大值称为该树的 高度; 与某顶点相邻的且远离根的顶点称为它的子节点， 与之相邻的且趋向于 根的顶点称为它的父节点; 子节点的个数称为该顶点的度. 度大于。 的顶点常 简称为内点， 度等于。 的顶点称为叶子. 按通常画法， 有根树的根将画在最上 面或最下面， 具有相同高度的顶点画在同一条水平线上. 在子节点间规定了一 个左右次序的有根树称为有序树.本文的概念及未列出的基本术语可参阅文 献【 1 4 , 3 2 - 3 4 . 此外， 文章中 还引用了 如下几个定义: 定义1 . 1 . 称k , ， 中 根属于y 的 有根生成 树为咖 ， n 一 二色 树. 定义1 . 2 . 称称。 中由l + k 个有根树组成的且l 个根属于x和k 个根属于y 的 生成森林为m , l ; n , k 一 森 林. 定义1 .3 . 称在子节 .b 、 间 规定了 一 个左右 次序的咖 ， 川 一 二色 树为卜 ， 川 一 二色 有序 树. 定义1 .4 . 称高度为1 或2 的有根二色树为基本二色树;称高 度为1 或2 的二色 有序树为塞本二色有序树。 有根二色树的计数 刘春林 2 m , 司 一 二色树的计数 一些文章 1 , 1 6 , 2 4 用不同的 方法对完全二部图标， 的生成树的个数进行 了 研究。 下面利用一个新的组合方法 3 1 来探讨k m ,。 的具有不同 特点的有根 生 成树的计数. 设t 为一个咖 润一 二色 树，v o 是t 的 根. 对t 中 任一个红色内 点， ， 记t 中由 点集 u lu e v ( t ) , d ( u , v ) 2 , d ( v o , u ) 二 d ( v o , v ) + d ( v , u ) 导出的子 图为s g ( v ) . 显然s g ( v ) 是一个以， 为根的基本二色树. 定 理2 . 1 . 设所有含k 个红色内 点的m , n 一 二色 树组成的集合为a , 所有满 足如 下条件的森林组成的集合为b , ( 1 ) 森林由k 个基本二色 树组成; ( 2 ) 森林的 绿色 顶点集合为 1 ， 二 ， m 、红色 顶点集合为 1 , - - - , n + k - 1 ) ，并 且森林的k 个根在 l ， . . . ， n ) 中 . 则在集合a和b 之间存在一个组合双射. 证明设f是一个满足上述条件的森林，则f在如下算法的作用下可唯一地得 到一个含k 个红色内点的m , n 一 二色树. ( 1 ) 给红色顶点n + l ， 二 ， n + k 一 t 加上星号* . ( 2 ) 在f中选出根最小且不含带星号顶点的树，记为 t o .设i 是t o 的根. ( 3 ) 在f中选出包含最小的带星号顶点的树， 记为t i . 设广是这个最小的带星 号顶点. ( 4 ) 合并t o 和t t ( 如图所示) 把顶点i 和广合成一个新的顶点，该顶点仍标为 i , t o 画在t i 的下面. - - 仁i it t 广t o ( 5 ) 重复步骤( 2 ) 、( 3 ) 、( 4 ) 直到不再存在带星号的顶点. 反之， 设t 为一个含k 个红色内 点的!二 ， n 一 二色树. ( i ) 在t 中 选出 最小的红色内 点( 记为v ) 使得s g ( v ) 中不含其它红色内点. ( 2 ) 从t中移走子图s g ( v ) 使之成为一个以， 为根的基本二色树， 并且把t中 的原顶点， 重新标号为n +l . ( 3 ) 重复步骤( 1 ) , ( 2 ) 直到所有红色内点均是根. 依次用n + 2 , . . . , n + k -1 分别 对选出的顶点重新标号.于是便得到了一个满足上述条件的森林. 证毕二 例2 . 1 . 如图所示，为一个! 1 0 , 9 卜 二色 树和与 之对应的森林. 有根二色树的计数 刘春林 1 01 3 7 1 2 1 了8 双 51 4 l p 1 记含l 个绿色叶 子的二 ， 司 一 基本二 色树的个数为t ,m ,l ,n . 弓 1 人t ,m ,1 ,。 的生 成函数: 洲 月月0口 t ( x , z , y ) = z l ) e n 蘑 恿 各 t l,m ,l,n -m = 11= 0 n= 1 m l y n 二 命题2 . l t 1 (x , z , y ) 一 ， (e (e 一 + z ) 一 l ) . 证明设t 为含l 个绿色叶 子的咖 ， 川 一 基本二色树. 从 1 , . , n 中 选出一个元 素和从 1 , . , m 中 选出。 一 l 个元素 分别作为t 中根和m 一 l 个绿色内 点的 标 号， 共 有( 1 ) 粱 1) 种 方 法 . 由 于t 中 有。 一 1 个 高 度 为2 的 红 色叶 子 和m 一 l 个 绿色内点， 因此先把这， 卜1 个红色叶子分成二 一 t 个分部， 然后在m一 l 个绿色 内点和m 一 l 个分部之间建立一一对应，使得每个分部中的顶点作为相应绿色 内 点的子节点，共有s 2 ( n 一 i m 一 1 ) ( m 一 1 ) i 种方法，其中s 2 ( n 一 i m 一 l ) 是第二 类s t ir l i n ; 数 于 是得到 t (x , z , y ) 二y-y-y- -1 1 =0- 1 n 、 1 m ， 1 / 用 一 、 : (。 一 ， ,m 一 ，) (。 一 ，) !z 1) i= /m :n二 翻口月 沁 二 ， y- yl y- s , ( i 一 ， m=1 1 =0 n =1 、 n - i m ! z l e m 一勺万一石几 了节 了 二 叱 n一 i 少 : : irl二 ， 觉 觉 (e ? - 1 )0- 1 m ! zx - ， 忍 1 1-0 k - 一 厂1 : m: 二 ， 、， .、 -e y么 e , 一1 十z 1 . - 尹 箱 tm飞 y ( ,x ( y - i 十 习 一 1 ) 证毕二 引 理 2 .1 . ( 1 1 4 1 ) 设 a (x ) 二 赚1 a k 若 、 b (x ) 二 艺 几 1 b k 若 为 两 个 生 成 函 毅 ， a * 与 。 * 分 别 是 满 足 性 质 p (a ) 与 p (b ) 的 某 类 标 号 图 形 的 个 数 . 则 。 (x )b (x ) 中 若 的 来 数 等 于 有序二元组( g i , g 2 ) 的个数， 其中g i 是具有性质p ( a ) 的图形，g 2 是具有性质 p ( b ) 的图 形，k 为g ， 和g : 中顶点 个数之和， 这些项点的标号为 1 , 2 , - , k . 由上述引理可以得出如下命题. 有根二色树的计数 刘春林 命 题 2 .2 . 哗 尸叶 裔 的 数 是 满 足 如 下 条 件 的 森 林 的 个 数 的 生 成 函 数 ， ( 1 ) 森林是由k 个墓本二色 树组成，并在这些树之问 规定了 一 个左右次序; ( 2 ) 森林中有n -1 个红色叶子和k 个不标号的红色 根. 为 方 便 起见 ， 记f (x ) i o 为f (x ) 的 展 开 式中纂 的 系 数 . 以 ,k n ,* 表 示 含， 个绿色叶子和k 个红色叶 子的。 ， 川 一 二色树的个数. 引 入t . ,t;n * 的生成函数: 。 口阴 t (x , z , y , w ) 二e艺艺em ,t;n ,k m=1 1 -0n =1 k =0 定理2 .2 . t (x , z , y , w ) = 艺( t 1 (x ,z ,y ) + w )” 一，一 y n ! 证明由定理2 . 1 可知， 在含有。 - k 个红色内 点和k 个红色叶子的有根二色树与 由n 一 k 个基本二色树组成的含有2 n 一 k 一 1 个红色顶点的根均不大于n 的森林 之间存在一一对应关系. 现在考虑上述森林的计数. 首先从 1 , 2 , - , n 中 选出 。 一 k 个 顶 点 作 为 森 林中 有 根 树的 根， 有( n 幼种 方 法。 在 根 被 确 定 后， 由 上 述 命题可知含。 一 1 个红色标号顶点的由k 基本二色树组成的根不标号的有序森 林 的 个 数 的 生 成 函 数 为( t i ( ,z ,y ) ) n - k l、一 ， ， . 于 是 得 到 : : (一卜 l j lrn= ik=o (。 n 、) ( ti (x,z,y)y )一 一 w k ynn! 尹-川 - n 苏 八 w 卫x , z ,y ) + w ) - 讫州 证毕。 由命题2 . 1 和定理2 .2 可知 yn一川 t ( x , z , y , w ) =艺 ( e x (er - i+ z， 一 1 + w )“ 一 w 1 i m 睿 y -i w kn !n ! l k ,n= 1 k=0 愈 y - 1 w kn !n ! k!n= 1 k=0 ( e ( e ， 一 + ) 一 1 ) n - k ( n 一 k ) ! n-1 1 ， 。 一 ! ) s 2 ( m , 。 一 k )( 2 . 1 ) - 凡 浏一刹 川一创 川艺曰 。工洞 间工间 。艺同 一一 有根二色树的计数 刘春林 推 论2 . 1 . 含1 个 绿色 叶 子和k 个红色 叶 子 的m , n 一 二色 树的 个 数等 于告 爷 s 2 (n - m一 1 ) s 2 ( m , 。 一 k ) . 令w 二i , z = l ，由等式( 2 . 1 ) 可得: 推论2 .2 . ( 1 2 , 1 0 1 ) m , n 一 二色 树的 个数等于。 m m - i . 自 从在 3 中首次出现了完全图kn中有根生成树的个数以来，大量的文 章 8 , 1 8 , 2 1 , 2 5 , 2 8 对这个问 题用不同 方法进行了 新的证明. 现在来指出利用上 述结论也可推出完全图k中有根生成树的个数， 记作: ( k n ) . 推 论2 .3 . 2 ( k ) = n - 1 . 证明设t 为k中的有根生成树，t中高度为偶数的顶点的个数为r ( 1 r n - 1 ) . 先 从 1 ， . . . ， n ) 中 选出: 个 作 为 这 些 偶 高 度 顶 点 的 标号 ， 有(?)种 . 由 推论 2 .2 可知，含: 个偶高度顶点和n 一 : 个奇高度顶点的有根二色树个数为 r - r ( n 一 r ) r - 1 .引用a b e l 恒等式 2 0 (二 + ， ) ” 一 y-( :) (y 一 “，”一(一 “，一 令x =- n , y 二 。 , k =r ，得: ,c ( k . ) 二 艺( 一 ) r-r(一 ，尹一 一 ”一 。 证毕二 文献 5 讨论了有根偶树的个数. 现在来考虑有根二色偶树， 即任一顶点的 度均为偶数的树. 记有2 m个绿色顶点和2 n + 1 个红色顶点的根为红色顶点的基 本二色偶树和有 根二色偶树的个数分别为r l ,2 m ,2 n + i , r 2 m ,2 n + ，设r i ,2 m ,2 n + i , r 2 n ,2 n + i 的生成函数分别为: 、(二， 一 名 !息 一 x2. r 1,2ng2n+ii-0 (2rn)! y 2 + i ( 2 n + 1 ) ! r (x , y ) =艺er z n ,z 。 十 i n - 1 n=o 户” 户+ i ( 2 m ) ! ( 2 n + 1 ) ! 应用与前面相仿的推理可以得出: 有根二色树的计数 刘春林 r i(x ,y ) = y (告 (/ + y + e - x flf - ) - ， r (x , y ) =艺1( 些 i 业 e - x i ? y 12n + 1 z ， z n 千i 一l l l r - l , l ，一 ， 咚 n + ) ! 砰 n+ 1 (2 n + 1) ! n , = 0 y ( 2 n + 、 “ ，一 一 ，一 ry+r rx z iy,2n 、nl/ ，暇 y- 矛 2 2 n + 1 ( 2 n 十 ) i 于_.2 n + i e 蒸 (2n +n1 ) 磨 蒸 (2n +i n 1 ) 磨 (2n + 1 - 2n l)nx (ey+2m !“一” ”，”， ( 2 n + i 一 2 n l ) m 尹 2 2 n + i ( 2 n + ) i 2 1 1 m! i m, =0( 扭 、 。 (- )y - l e iy,2rt m vr 1 / ( 2 m ) (2 二 一 2 m l )2n n 0 i / 加江 n = 0 一 恿 蘑22 m 2 2n- 0 - 1 m, =0 2 n + i/ ， . 11 x 又 “ “ 丁 】 ( 2 n + i 一 2 n l ) 2 m 夕滚。 n l / x 2 . ,2 n + 1 ( 2 m ) ! ( 2 n + i ) ! 推论2 .4 . 含2 。个绿色项点和2 n + i 个红色项点的根为红色顶点的有根二色偶 树的个数等于: /2m j (2mm l一 2m l户 zn+l( 2n + 12m 1)2 y ) (2n + 1n,=0 nl 一 ，zn, 加艺 2 2 m + 2 n + 1 n h=0 定理2 . 1 把一个含k 个红色内 点的!m 刊一 二色树分解成k 个基本二色树。 下面介绍另 一个算法， 它把含l 个绿色内点 和k 个红色内点的卜呼二色树分 解成由高度为 1 的基本二色树组成的森林.通过该算法可解决有根二色树上 的其它几类计数间题. 为叙述方便， 推广上述基本二色树的定义. 前面定义的 基本二色树的根均是红色顶点， 高度为1 的顶点均是绿色. 称根为红色顶点且 高度为 i 的有根二色树为r 一 基本二色树，称根为绿色顶点且高度为 1 的有根 二色树为b 一 基本二色树. 定理2 .3 . 设所有含1 个绿色叶子和k 个红色叶子的m , 司 一 二色 树组成的集合为 a,所有满足如下条件的森林组成的集合为b, ( 1 ) 森林由m - 1 个b 一 基本二色 树和。 - k 个r - 基本二色 树组成; ( 2 ) 森 林的 绿色 顶点集合为 1 ， .， .，.， ， ( 2 。 一 6 、 红色 顶 点集合为 1 , . - , 2 n 一 k - 工 ，并 且绿色 根在 1 , 0 . . . ， m i 中 、 红色 根在 i , , n ) 中 . 则在集合a和b 之间存在一个组合双射 证明设t 为一 个含l 个 绿色叶 子和k 个红色叶 子的脚 刊一 二色树. 在t 上运用定 理2 . 1 中的 拆开算法便得到一个由。 一 k 个基本二色树组成的森林， 设该森林中 ，。 一 1 个绿色内 点为， 1 , . . . ， v . - / ( v i . . . v . - i ) . 依次去掉s g ( v l ) , . . . , s g ( v _i ) 使 之成为m - 1 个分别以， 1 , , v m - ， 为根的b 一 基本二色树， 并对原来的: : ， . . i v -1 有根二色树的计数 刘春林 重新标号为( 。 十i ) . . . . . , ( 2 m 一 1 ) , . 于是唯一地得到了一个满足上述条件的森 林. 反之， 设f 为一个满足上述条件的森林. 给森林中的红色顶点n + 1 ， 一， 2 。 一 k 一 i 添 加 星号幸 ， 给 绿色 顶点( m + 1 ) . , . . , ( 2 m 一 l ) , 添加井 号# . ( i ) 在f中选出根最小的b 一 基本二色树t o ，设根是i , ( 2 ) 在f中选出 包含最小的带井号顶点的b 一 基本二色树t i ，设尹为该带井号 顶点。 ( 3 ) 合并t o 和t t ， 方法与定理2 . 1 中的相同. ( 4 ) 重复( 1 ) , ( 2 ) , ( 3 ) 直到不再存在b 一 基本二色树.于是得到了一个由。 - k 个基本二色树组成的森林. ( 5 ) 利用定理2 . 1 中的合并算法，由以上森林便得到一个含l 个绿色叶子和k 个 红色叶子的m , n 一 二色树. 证毕二 事实上， 推论2 . 1 可由 上述定理简单证明如下. 在集合b 的任一个森林中有 m - 1 个b 一 基本二色树 和。 - k 个r 一 基本二色树. 从 1 ， ， m 中 选出m - l 个作 为 绿 色 根 的 标 号 、 从 1 ， . . . , n 中 选出 。 一 k 个 作 为 红 色 根的 标 号， 共 有( 粱!) ( 班 动 种方法.另外还有m 个绿色叶子和。 一 1 个红色叶子.把绿色叶子分成n 一 k 个 分部、 红色叶 子分成m 一 l 个分部， 共有s 2 ( m , n 一 k ) s 2 ( n 一 i m 一 l ) 种方法. 在根 与 分部之间 建立一一 对应关系有( m 一 l ) ! ( n 一 k ) ! 种方法. 于是得出b 中 森林的 个 数 等 于告 兴 s 2 (m , n 一 、 ) s 2 (n 一 1 , 。 一 ， ) 由 定理2 .3 可以 得出 对顶点的度作了一定限制的!m 川一 二色树的个数。 推 论2 .5 . 设非负 整 数d i ， 二， d ,: 和川 ， ，呱分 别 满 足d i +二 + d o = m , 试 + + 成 ， 一 。 一 ， ， 则 使 绿 色 顶 点了 ( 1 j 二 ) 的 度 为弓 ， 红 色 项 点 ( 1 i n ) 的 度 为 d i 的脚 ， 川 一 二色 树的个数为 n 一 j 、 m、 _ d ; 试 ， / d i 丙/ 推论2 .6 . 以某特殊顶点为根且根的度为r 的含l 个绿色叶子和k 个红色叶子的 。 ， 川 一 二色 树的个数等于: / 。 一1 1 ( n 一1 ) ! m !， 又 r 一 ! ) k ! 一 l ! 3 2 1 n 一 ， 一 一 ， )j 2 1n 一 ， ,m 一 ， . 证明由 定 理2 .3 可知 : 含l 个绿 色叶 子和k 个红 色叶 子的m , 川 一 二色 树的 个 数 等于由二一 i 个b 一 基本二色树和。 - k 个r 一 基本二色树组成的、绿色顶点集 合 为 1 ， 二 ， ( 2 m 一 l ) , 和 红 色 顶 点 集 合 为 1 , . . . , 2 n 一 k 一 1 的 、 并 且 绿色 根在 1 ， ， m 中 和红色根在 1 , , n 中的森林的个数. 设m - 1 个b 一 基本二色 树 为叮 ， ， 成 _ ， 、n - k 个r 一 基 本 二 色 树 为t , t 2 , . . . , . - k ， 其中t 的 根是 作为 脚川一 二色树的根的那个特殊顶点( 记作v ) . 从j i r ， 二， m 中 选出m 一 1 个元素和 有根二色树的计数 刘春林 从 1 ， . . . , n / v 中 选 出 。 一 k - i 个 元 素 分 别 作 为 绿 色 根 和 红 色 根 有( mm - l) ( n -, -k 幼 种方法. 又设t i 包含的大于m的叶子的个数为h ， 显然有i h 1 , t . l . a u s tin 2 利 用l a g r a n g e 公式求出了f k ( x , a 现在对f ( m , 0 ; n , k ) 给出一个组合证明. 定理3 . 1 . f (m ,o;n,k， 一 “ ( n ) m ll-kn( k 。一 证明设所有!in 问一 二色树和m , 0 ; n , 创 一 森 林组成 的 集合分别为f 1 和f k 由引 理 3 . 1 可知只需证明: if ji( : 二 ) 一 。 im k- 1, 其中if , i = n n n t - 1 , 1f k i = f ( m , 0 ; n , k ) . 显然f k 中的任一个森林， 含有in 个绿色顶点 现给森林添加k -i 个新的 红色顶点i ， . . . . ( k - 1 ) - ， 在i ( 1 i k - 1 ) 和某一个绿色顶点之间连一条边， 使 得i . 成为该绿色顶点的子节点. 于是得到了一个新的森林， 森林是由k 个有根 二色树组成且含有m个绿色顶点和。 + k -1 个红色顶点记由f k 中元素添加 k 一 1 个 红 色 顶 点 而 成 的 所 有 森 林 组 成 的 集 合 为， 显 然 有 = 川m k - i 。 设 f 为中 的 一 个 元 素 . 从f 唯 一 地 得 到 一 个!m 问 一 二 色 树 的 过 程 如 下 : ( 1 ) 在f中选出根最小且不含带星号顶点的树t o ，设其根为i , ( 2 ) 在f 中 选出含最小的 带星 号顶点的树t , ， 设该带星号顶点为j t ( 3 ) 合并t o 和t , 成一个有根二色树， 把顶点i 和广合并成一个顶点，该