（计算数学专业论文）s（n）因子计数理论及其应用.pdf

摘要 本文系统研究了s ( ”) 一因子计数理论，包括图的分支分析方法和s ( “) 一因子的计数公 式( 第一章，第二章，第三章和第四章) ，并将这一计数理论和组合数学的许多思想和方法 联系起来，给出了平均色数的显示计数公式和对平均色数的刻画，并用来解决图的匹配 数和独立集个数的计算问题作者还提出相伴数的定义，通过数学机械化方法给出了其 发生函数，并进行了详细的研究，得到了许多组合恒等式，这些恒等式涉及到p e l l 数， l u c a s 数，f i b o n a c c i 数，两类s t i r l i n g 数和c h e b y s h e v 多项式等 本文的主要研究成果为 1 利用图的分支分析法，在正则m 叉树t 中，删除鲍以及端点关联边，通过所得的子 正则图m 叉树中分枝点数、叶数和m 之间的内在联系( 第一章) ，导出正则m 叉树t 的 s ( n ) 一因子数递归公式特别地，当m = 2 时，得到正则2 叉树t 的s ( n ) 一因子数的递归 公式正则m 叉树t 在计算机和组合码中的应用十分广泛 2 利用卷积公式，得到完全i 部图的计数公式( 第二章) ，进一步研究了有关完全i 一部图 的组合恒等式，并通过n ( g ，k ) 的卷积公式( 第五章) 得到许多组合恒等式 3 利用n ( k n ，k ) = s ( k ) ( 第二类s t i r l i n g 数) ，得到图的色多项式的显示公式( 第三章) 采用图的分支分析方法和组合计数方法，得到几类图的显示计数公式特别地，给出了 完全t 一部图色多项式的显示表达式 4 利用反演理论，得到s ( “) 一因子数与色多项式系数之间的关系公式( 第四章) ，给出与此 相关的图的计数公式，例如，n 一2 一正则图，n 一3 _ 正则图，补树的显式计数公式等， 这些对平均色数( b a x t e l s 和w e l s h ，1 9 9 5 提出) 的计算提供了新的方法此外，还给出了 完全d 部图的硒- 因子数的计数公式( 第四章) ，完全3 - 部图的最短圈覆盖的计数公式， 以及平均色数的组合和代数的刻画( 第五章) 5 提出相伴数的定义，采用数学机械化的方法给出了相伴数的发生函数( 第六章) ，给 出了相伴数与p e l l 数，f i b o n a c c i 数和两类c h e b y s h e v 多项式之间的组合恒等式 6 利用组合方法给出了n ( g ，k ) 的差分算子表示公式( 第七章) ，利用图的分支分析方法 和s ( ”) 一因子的计数公式，得到了一些组合恒等式和独立集计数的显式公式 7 提出猜想：序列n ( g ，k ) 是单峰性序列 。黔 、- 关键词：s ( “) - 因子；玩因子；n ( c ，) ；a ( g ) ；最短圈覆盖；正则m 叉树；平均色数； 卢( g ) ；完全i 部图；风车图( 荷兰风车图) ；独立集；n ( g ) ；色多项式；相伴数；两类s t i f l i n g 数；p e l l 数；f i b o n a c c i 数；完全分支数n ( k n ，k ) ；差分算子；图论计数；反演关系；发 生函数；数学机械化 1 1 0i 一， e c o u n t i n gt h e o r yo fs ( “) 一f a c t o r sa n da p p l i c a t i o n s a b s t r a c t i nt h i st h e s i s ，t h ea u t h o r 百v e sas e r i e so fc o u n t i n gf o r m u l a sa b o u ts t “) - f a c t o r s ，b ym e a n s o fm e t h o d so fa n a l y z i n gc o m p o n e n t so fg r a p h sa n dc o m b i n a t o r i a le n u m e r a t i o n s ( s e ec h a p t e r 1 ，c h a p t e r2 ，c h a p t e r3a n dc h a p t e r4 ) b yu s i n go f t h ec o u n t i n gf o r m l l l a sa n dm e t h o d sa n d i d e a so fc o m b i n a t o r i c s ，t h ea u t h o rg i v e st h ee x p l i c i tf o r m u l a so ft h em e a nc o l o u rn u m b e r so f d a s s e so fg r a p h sa n dc h a r a c t e r i z a t i o nf o rt h em e a nc o l o u rn u m b e r 弘( g ) o fa n yg r a p h s t h e a u t h o rp r o p o s e st h ec o n c e p to fa s s o c i a t e dn u m b e r s ( s e ec h a p t e r6 ) b ym e c h a n i c a lm e t h o d o fp r o v i n g ，t h ea u t h o rg i v e si t sg e n e r a t i n gf u n c t i o n ，a n dd o e sas e r i e so fr e s e a r c ha b o u tt h e a s s o c i a t e dn u m b e r sa n dg e t ss o m eo fc o m b i n a t o r i a li d e n t i t i e s t h e s ec o m b i n a t o r i a li d e n t i t i e s a r er e l a t e dt oag r e a td e a lo fn u m b e r s ，f o re x a m p l e s ，p e l ln u m b e r ，l u c a sn u m b e r ，f i b o n a c c i n u m b e r ，t h et w ok i n d so fs t i f l i n gn u m b e r sa n dt w ok i n d so fc h e b y s h e vp o l y n o m i a l s i nt h et h e s i s m a l nr e s u l t sa x ea sf o l l o w s ： 1 f o rar e g u l a rm - f u r c a t i n gt r e e ar e c u r r e n c ef o r m u l ao ft h en u m b e ro fa l l i t sf l 叫- f a c t o r si s o b t a i n e db ya n a l y z i n gt h er e l a t i o na n a o n g ta n dmo fs u b - f u r e a t i n gt r e e sa n db ya d o p t i n g m e t h o d so fc o m p o n e n t so fg r a p h s ( s e ec h a p t e r1 ) s p e c i a l l y , m = 2 ，t h er e c u r r e n c ef o r m u l ao f ar e g u l a rb i n a r yt r e ei so b t a i n e d r e c u r r e n c e so fr e g u l a rr n f u r e a t i n gt r e e sh a v ean u m b e ro f u s a g e si nc o m p u t e ra n dc o m b i n a t o r i a lw o r d s ( o rc o d e ) 2 b yu s i n go ff o r m u l a so fc o n v o l u t i o n s ，t h ea u t h o ro b t a i n st h ec o u n t i n gf o r m u l a sa n dc o m b i n a t o r i a li d e n t i t i e so fc o m p l e t e - p a r t i t eg r a p h s ( s e ec h a p t e r2 ) m o r e o v e r ，t h ea u t h o ro b t a i n s s o m ec o m b i n a t o r i a li d e n t i t i e sb yt h ef o r m u l a so fc o n v o l u t i o n so fn ( g ，女) 3 b ya n a l y z i n gc o m p o n e n t so fg r a p h sa n de n u m e r a t i v et e c h n i q u e s ，t h ea u t h o ro b t a i n st h e e x p h c i tf o r m l l l ao ft h ec h r o m a t i cp o l y n o m i a l so fg r a p h s ，s p e c i a l l y , p r e s e n t st h ee x p l i c i tf o r m u l a o ft h ec h r o m a t i cp o l y n o m i a l so fc o m p l e t ei - p a r t i t eg r a p hr e l a t e dt ot h es t m i n gn u m b e r ss ( n ，k ) o ft h es e c o n dk i n d 4 t h ea u t h o rd e r i v e st h er e l a t i o nf o r m u l a sb e t w e e nt h en u m b e r so fs ( n ) 一f a c t o r sa n dc o e f f i c i e n t s o f t h ec h r o m a t i c p o l y n o m i a l s ( s e e c h a p t e r 4 ) ，a n ds h o w se x p l i c i t f o r m u l a s o f a n u m b e ro f g r a p h s ， f o re x a m p l e s ，n 一3 - r e g u l a rf a p b s ，s p e c i a lc o m p l e m e n t a r yt r e eto fa n yt r e et s ot h a tt h e s e p r o v i d en e ww a y sf o rs o l v i n gt h em e a nc o l o u rn u m b e r s ( d e f i n e db yb a r t e l sa n dw e l s h ，1 9 9 5 ) 5 t h ea u t h o rp r o p o s e sac o n c e p to fa s s o c i a t e dn u m b e r s ( s e ec h a p t e r6 ) ，g i v e st h eg e n e r a t i n g f u n c t i o n sb ym e c h a n i z e dm e t h o d ，a n dd i s c u s s e sc o m b i n a t o r i a lf o r m l l l a so na s s o c i a t e dn u m b e r s ， f i n a l l y , o b t a i n e dan u m b e ro f c o m b i n a t o r i a li d e n t i t i e sr e l a t e dt op e l ln u m b e r s ，f i b o n a c c in u m b e r s a n dc h e b y s h e vp o l y n o m i a l s 6 b a s e do nc o m p u t i n gt e c h n i q u eo fc o m b i n a t o r i c s ，t h er e p r e s e n t i n gf o r m u l ao fd i f f e r e n c eo p - e r a t o ro fn ( g ，) i sd e r i v e d ( s e ec h a p t e r7 ) b ya n a l y z i n gc o m p o n e n t so fg r a p h sa n dt h e r e p r e s e n t i n gf o r m u l a so f t h en u m b e r so fs l ”】- f a c t o r s t h ea u t h o rg i v e sag r e a td e a lo fc l a s s i c a l i i i i d e n t i t i e s f o re n u m e r a t i o no fi n d e p e n d e n ts e t s ，e x p l i c i tf o r m u l a so fan u m b e ro fc l a s s e so f g r a p h sa r eo b t a i n e d 7 t h ea u t h o rp r o p o s e sac o n j e c t u r e ：as e q u e n c eo fn ( g ，女) i su n i m o d a l i t y ( c o r r e s p o n d i n gw i t h t h e2 8 t hc o n j e c t u r ei ng r a p ht h e o r yw i t ha p p l i c a t i o n s ) k e y w o r d s ：s ( “) 一f a c t o r s ；k d f a c t o r s ；n ( g ，女) ；a ( g ) ；c o v e r so fs h o r t e s tc i r c l e s ；r e g u l a rm f u r c a t i n gt r e e ；t h em p _ j 1c o l o u rn u m b e r s ；p ( g ) ；c o m p l e t ei - p a r t i t eg r a p h ；w i n d g r a p h ；i n d e - p e n d e n ts e t s ；n ( g ) ；c h r o m a t i c p o l y n o m i a l ；a s s o c i a t e d n u m b e r s ；t w o k i n d s o f s t i f l i n g n u m b e r s ； p e l ln u m b e r ；f i b o n a c c in u m b e r ；c o m p l e t ec o m p o n e n tn u m b e r s n ( k n ，k ) ；d i f f e r e n c eo p e r a t o r ； g r a p h i c a le n u m e r a t i o n ；i n v e r s ep r o b l e m ；g e n e r a t i n gf u n c t i o n ；m a t h e m a t i c sm e c h a n i z a t i o n ； 0 序言 近半个世纪以来，图论的发展十分迅速，已经在离散数学中占有非常重要的地位，由 于信息技术的发展，使得图论在计算机、通信和互联网等诸多领域的应用也日益广泛 近二三十年以来，图论的研究在中国也得到了较快发展，取得了很大成就 、 本论文包括以下几个方面：第一，图的分支数的计算，即图论的计数；第二，色数问 题，特别是色多项式的显式公式以及平均色数；第三，由图的分支计数产生的组合恒等 式；第四，图论及其应用* 【8 中的第2 8 猜想，并提出相应的猜想，即单峰性猜想； 第五，计算机组合码的正则m 叉树以及控制路线设计方案问题，特别是正则2 叉树的应 用基于这些问题，提出s - 因子的概念( 作者原来称为理想子图，见 7 9 ) ，并对其进 行了系统的研究，理想子图属于图的范畴，面s ( n ) 因子是组合数学方法的体现 我们建立了s ( “) 一因子计数理论，包括图的分支分析方法和s ( “) 一因子计数表示公式 ( 第一章，第二章，第三章和第四章) 图的分支分析方法，见 8 0 和i s 4 在【1 3 中，w i l l i a m y c c h e n ，e m e t i cd e u t s c h 和s e 晒e f i z a l d e 研究了关于平面树的老的和新的叶数的计数 公式在【6 4 中，l a s z e k e l e y 和h u aw a n g 讨论了树的子树的计数问题在 6 0 中， i g o rr i v i n 讨论了圈的计数和有限维口模在【5 1 】中，j a m a k o w s k y 和j p m a r i n o 研究了关于边界树宽的图的b a r r e n 多项式，讨论了许多类图的计算复杂性，n ph a r d 和 # h a r d 问题色数问题的研究有平均色数，分数色数，循环色数和四色猜想等，在图论中 是一个内容极其丰富却又十分困难的领域利用组合数学方法，我们得到s ( n ) 因子数计 数表示公式，解决了图口的色多项式与s ( n ) ，因子数的关系通过建立s ( n ) 因子计数理 论，我们研究了一些图论问题( 第三章，第四章和第五章) ，并得到s ( n ) 一因子计数方程( 第 五章) 我们提出( i f ，k ) 的相伴数妒( k ) 的概念，并进行了相关的研究( 第六章) s ( n ) 因子计数理论的应用，使得我们可以得到许多的组合恒等式( 第二章，第四章和第七章) 在这一领域，有许多更深更有价值的问题有待研究 s ( “) 一因子计数在图的计数、组合恒等式、计算机编码学、色数研究、覆盖理论设计 等方面都有应用 关于s ( “) 因子概念，我们的研究是从计数理论入手，利用组合数学的方法研究图 论，反过来，根据图论的研究结果给出新的组合学解释特别地，我们利用s ( “) 一因子计数 给出的组合方程及恒等式是新的成果另外，我们利用这一方法解决了平均色数问题， 这是b a r t l s ，w e l s h 和f m d o n g 的方法难以解决的进一步，给出平均色数的组合和代 数的刻画色多项式的刻画十分困难，这一理论给出了部分色多项式的显式公式，特别 是给出了完全i 部图的含s t i f l i n g 数的色多项式，以及m = 2 时，完全二部图的色多项 式图的独立集的个数的计算是n ph a r d 问题( 见【5 1 ) 利用s ( “) 因子计数理论，我们 s ( n ) 因子计效理论及其应用 得到许多独立集的计数公式在本文中，作者给出了完全d _ 部图的玩因子的计数公式 以及完全3 _ 部图的最短圈覆盖的计数公式，这些都是热点问题，但又是十分困难的此 外，作者利用数学机械化方法给出了一个复杂的偏微分方程的解，由此得到相伴数的发 生函数由于s ( “) 一因子计数理论来源于图论，本文得到了许多新的组合恒等式，特别是 关于两类s t i f l i n g 数和f i b o n a c c i 数的一些组合恒等式 r c r e a d 在1 9 6 8 年提出了咆多项式的系数是单峰性序列”的著名猜想( 见j a b o n d y , u s r m u r t y 【8 ) y iw a n g 和y e o n g n a ny e h 给出一个单峰性猜想的证明( 见 67 】) ， 在此，我们相应地提出n ( g ，k ) 的单峰性猜想，即n ( g ，1 ) ，n ( a ，2 ) ，n ( g ，k ) ，n ( g ，n ) 也是单峰性序列 本文使用的主要概念有s ( n ) 因子、k d - 因子、最短圈覆盖、平均色数、独立集、相 伴数 本文用到的图主要有正则m 叉树、完全部图、n 一2 度正则图、n 一3 度正则图、 风车图、完全图、树、路、圈、完全3 _ 部图 本文用到的组合数主要有两类s t i r n n g 数、p e u 数、l u c a s 数、f i b o n a c c i 数、c h e b y s h e v 多项式、完全图的恰有个分支的s ( “) 因子个数n ( k n ，k ) ( 简称为完全分支数( ，) ) 主要概念和定义，在本文中都有阐述基本符号和定义，见下列文献： 1b o n d y , j a i v i u r t y , u s r ，g r a p ht h e o r yw i t ha p p h c a t i o n s ，a m e r i c a ne l s e v i e r p u b l i s h i n gc o ，i n c ，n e wy o r k ，1 9 7 6 ， 【2 】2c o m t e t ，l ，a d v a n c e dc o m b i n a t o r i e s ，d r e i d e lp u b l i s h i n gc o ，d o r d r e c h t ，1 9 7 4 3 w i l f , h s ，g e n e r a t i n g f u n c t i o n o l o g y , s e c o n de d i t i o n ，b o s t o n ，m a ：a c a d e m i cp r e s s i n c ，1 9 9 4 【4 s t a n l e y ，r p ，e n u m e r a t i v ec o m b i n a t o r i c s v 0 1 1 _ c a m b r i d g es t u d i e si na d v a n c e d m a t h e m a t i c s ，4 9 c a m b r i d g eu n i v e r s i t yp r e s s ：c a m b r i d g e ，1 9 9 7 2 l 正则m 叉树t 的s ( n ) = 凰：1 i n ) - 因子数的递归公式 1 1 定义和简介 定义1 1 1 设s ( “) = 甄：1s i n ) ，n 1 ，其中k 为f 个顶点的完全图，若m 是图g 的子图，且m 的每一个分支都同构于s ( “】= 甄：1 i n ) 中的某一个元素，则m 叫 做s ( “) - 子图，若m 为g 的生成子图，则m 叫做g 的一个s ( n ) = 蜀：1 l n 卜因 子 记n ( g ，) 为图g 的恰有k 个分支的s ( “) = 噩：11 i n ) 一因子数，a ( g ) 是g 的 所有s “= 噩：1 i n 卜因子数，即a ( g ) = 楚1 n ( g ，) 例如，给定星形图1 1 ，3 ( 见图1 ) ，则 。 吩l 咚 培 图l 星形图1 1 3 k 1 ，3 的恰有3 个分支的s - 因子的个数( 凰3 3 ) = 3 ( 见图2 ) ，硷。3 的恰有4 个分支的 s “) - 因子的个数( 甄，3 ，4 ) = l ( 见图3 ) ，而显然( 皿，3 ，1 ) = ( 凰，3 ，2 ) = 0 ，则星形图噩3 的所有s ( “) 因子数 4 且( 研，3 ) = 3 女) = 4 v j 舅蟹 。i 彰醪 v 1 、 蚱晦蟮 图2 星形图k l ，3 的恰有3 个分支的s ( n ) 因子 3 s ( n ) 因子计数理论及其应用 k 辑野 b 图3 星形图所3 的恰有4 个分支的s ( “) - 因子 ， 文f 1 3 w i l l i a my c c h e n ，e m e r i cd e u t s c h 和s e r g ie l i z a l d e 研究了关于平面树的老 的和新的叶数，作者在【6 6 】中利用分拆对应关系得到完全图恰有k 个分支的计数公 式，在 8 l 】中利用组合卷积公式推出a ( 瑶) 计数公式，在【8 0 中利用覆盖法得到0og 的s ( n 】= f 噩：1 i n 卜因子数计数公式本章通过图的分支分析法研究正则m 叉 树t 的子正则m 叉树中分枝点数、叶数和m 之间的关系，从而导出正则m 叉树t 的 s ( “) = f 鳗：1 f 墨n 因子数递归公式特别地，鉴于正则2 叉树t 在计算机及组合码 中有着广泛的应用，我们还将给出2 又树t 的递归公式及一些初值 1 2 正则m 叉树t 的子叉树的分枝点 引理1 2 1 1 8 0 对任意图g ，给定g 的一点p ，若过p 的一切完全图为甄。，k ：心，弓 【1 ，川，1 茎j r ，n 为g 的顶点数，则g 的s ( “) = 尬：1si n 一因子数 r a ( g ) = a ( a y ( 蚝) ) ， j = l 其中g 一矿( 蚝) 是指g 中去掉顶点y ( k i j ) 和与y ( 甄，) 相连接的边 引理1 2 2 若图g 1 g 2 ，g 。两两交集为空集，则 a ( g 1u g 2 u t u g 。) = a ( g 1 ) a ( g 2 ) - - a ( a 。) 定义1 2 2 在根树t 中，若任意结点的出度最多为m ，则称t 为m 叉树，出度不为0 的 结点称为分枝点，若每个分枝点的出度都等于m ，则称为完全m 叉树，出度为0 的点称 为叶，若t 的全部叶点位于同一层次，则t 称为正则m 叉树 引理1 2 3 8 4 j 令t 为正则m 叉树，分枝点数为 ，叶数为t ，则i ( m 一1 ) = t l 引理1 24 令g 为星形图k l 则a ( g ) = m + 1 ， 引理1 2 5 令g 为正则m 叉树t ，分枝点数为m + 1 ，则 a ( t ) = ( 2 m + 1 ) ( m + 1 ) ”一1 证明利用引理1 2 1 和图论计数，详细证明省略 引理1 2 6 令t 为正则m 叉树，分枝点数为i ，叶数为t ，则删去含d 点的一个尬，t 的子图t v ( k 2 ) 中有m 一1 个分支，每个分支都是正则m 叉树，分枝点数为等，叶 4 大连理工大学博士学位论文 数为嘉，另外，有m 个分支，每个分支都是正则m 叉树，分枝点数为击( 等一1 ) ，叶 数为帚t 证明利用分支和组合递归分析，详细证明省略 1 3 正则m 叉树t 的s ( “) = k ：1 i n ) 一因子数的递归公式 定理1 3 1 令t 为正则m 叉树，分枝点数为i ，叶数为t ( 见图4 ) ，记t 的s ( n ) = 托：1 i n ) 因子数所有个数为a ，则a t = a m m + m a i m 。a ；m ，。- 1 ，特别地，a m = m + 1 ，a m 。= ( 2 m + 1 ) ( m + 1 ) ”一1 图4 叶数为t 的正则m 叉树t 证明由于t 是正则m 叉树，分枝点数为i ，叶数为t ，则不妨先记t 的s ( n ) = 匠： 1 i n ) - 因子数的所有个数为a ( 。t ) t 是正则m 叉树，类似引理1 2 5 对给定点 作讨论，过的完全图只有k 1 和鲍通过图论的分支分析方法，我们有： 情况1 y o 作为研，则s ( “) = k ：1 isn ) 一因子数 a ( t y ( k 1 ) ) 。a m ( ，i i - - 1 ，去) 情况2 v o 含于恐，共有m 个施，则s ( ”) = 噩：1 isn 因子数为 m a ( t y ( 鲍) ) 2m a “( ，击( 导一1 ) ，去) a 一1 ( ，i i - - 1 ，去) 则根据引理1 2 1 ，我们得到 a 。t ) = a ( t y ( 蚝) ) j = 1 = a ”( a m ，百i - - 1 ，去) + m a “( 引1i i - - 1 1 ) ，嘉) a ”- 1 ( ，导，去) 5 s ( n ) 因子计数理论及其应用 通过变化 a ( 2 1 m j ，t ) = a m ( a m ，i 去一导，去) + m a “( ，等素一击音) a ”1 ( ，等去一导，去) a ( ，鲁 等，t ) = a “( 乇，i 去一导，去) + m a “( ，导素一导，寺) 且一1 ( ，导去一等，击) 将上述等式看作关于变量t 的函数，记a ：= a ( ，t ，t ) ，则a = a m m + m 叼。a m 。，。- 1 特别地，对于正则m 叉树t ，叶数t = m ，则且。= m + l ；对于正则m 叉树t ，叶数 t = m 2 ，则4 m 2 = ( 2 m + 1 ) ( m + 1 ) ”一1 推论1 _ 3 1 令t 为正则2 叉树，分枝点数为i ，叶数为t ，则a = a 务2 + 2 码4 a t 2 - 特 别地，如= 3 ，a 4 = 1 5 例如，对于正则2 叉树t ，其叶数t = 8 ：如图5 所示 v o 图5 叶数为t = 8 的正则2 叉树t 则根据推论1 3 1 ，我们有a s = 坞2 + 2 a ；a 4 = a ；+ 2 a 弘4 = 1 5 2 + 2 3 2 1 5 = 4 9 5 下面是正则2 叉树t 的一些初值表： t 2481 63 2 a t 31 54 9 5 4 6 7 7 7 54 4 8 0 4 6 5 8 3 7 5 1 4 问题 表1 1 ：正则2 叉树t 的一些初值 正则m 叉树t 的s ( n ) = 墨：1s n ) 因子数的所有个数a 的递归公式是非线性 的，它是高次递归关系，因此，无论是利用组合数学理论还是偏微分方程理论，导出a 的计数公式都是十分困难的，而且a 的渐近逼近也很难建立，这些问题都有待解决当 然对任何叶数，a 的递归公式存在，因此我们可以建立算法利用计算机算出a t 的值 此外，利用s ( n ) = k ：1 f 兰n ) 因子数的递归公式，我们能够解决正则m 叉树t 的匹配数的递归关系和二部图( 偶图) 的匹配数的显示公式 6 2 完全 部图 ( 两，恐，五) ，嘲的计数公式和组合恒等式 本章利用卷积公式和组合计数方法，得到完全i 一部图n ( x l ，x 2 ，墨) ：翻的计数 公式以及与其相关的组合恒等式更进一步，我们利用n ( g ，k ) 的组合恒等式，得到关于 完全i 部图的组合恒等式 2 1 引言 l a s z e k e l e y 和h u aw a n g 讨论了树的子树的计数问题 6 4 3 ，i g o rr i v i n 研究了圈的计 数和有限维口模 6 0 j 在这一章，我们将利用组合数学的卷积公式讨论完全i 部图的恰 有个分支的s ( “) = 蜀：1 曼t s n ) 因子的计数问题 记n ( c ，k ) 为图g 的恰有k 个分支s ( “) 一因子数，a ( g ) 是g 的所有s ( “) = 墨，：1 i 墨n 一因子数，即a ( g ) = 麓l n ( g ，) 定义2 1 1 1 3 】设图g = ( 蜀，x 2 ，置) ，x j 为i 玛j 个顶点的集合，其中1 j 墨i ，对于 图g 中的任意两点u 墨，u x j ，若i = j ，则“与口不相连，否则u 与 相连，则称 g = ( x 1 ，x 2 ，墨) 为完全i - 部图特别地，当江2 时，g = ( x l ，x 2 ) = ( x ，y ) 为完全 二部图 引理2 1 1 q t = t 0 1 ) - o 一 + 1 ) = 兀：1 0 一k + 1 ) 引理2 1 2 1 4 嘲i = s ( ，f ) t f ，其中s ( k ，f ) 是第一类s t i f l i n g 数 引理2 1 3 6 6 】若图g 无凰图，n 为图g 的顶点数，则当1 k n 2 时，n ( g ，k ) = 0 引理2 1 4 设图g 的色多项式为f ( g ，t ) ，则f ( g ，t ) = 楚1n ( g ，k ) t 引理2 1 5 若0 是图g 的补图，则g 的色多项式f ( g ，t ) = ：1 ( 0 ，k ) 兀垒1 ( t i + 1 ) 引理2 1 6 若g 是图g 的补图，则g 的色多项式f ( g ，t ) = 笔1 区 n ：1n ( g ，k ) 8 ( k ，r ) 矿，其 中8 ( k ，r ) 为第一类s t i f l i n g 数 证明1 ( c ，t ) = n = 1 n ( g ，) i l l 。( t i + 1 ) = ：；。( o ，k ) s ( ，f ) 一， nn ， f ( g ，t ) = 匹( g ，k ) s ( k ，r ) r = lk = l 引理2 1 7 令g 为完全i 部图( i 2 ) ，则g 无凰+ l 图 7 s ( n ) 因子计数理论及其应用 引理2 1 8 7 0 】若( g ，k ) 是图g 的恰有k 个分支的s ( “) 一因子个数，则 雕k ) t 疑搿) h n ( a , k 也 ( n ) ( o ， = e j 。釜1 ) 垆 2 2 卷积公式 定理2 2 1 令g = ( x 1 ，x 2 ，墨) 为完全i - 部图，则n ( g ，k ) 满足如下的卷积公式 nk i x i il x 2 i x , i n ( g ，) i i ( t j + 1 ) = 1 - i ( t k + 1 ) ( t k + 1 ) i i ( t k + 1 ) k = l j = l k = lk = lk = i 其中x 1 + x 2 + + 墨= n 证明由于g = ( x l ，x 2 ，五) 为完全i - 部图，则g = k i x 。iu k t x 。iu u i k x 。i ，对任意 p ，口，p q ，n = 也1 p ，q s i ，图0 的色多项式为： f ( g ，t ) = f ( k x 。，( k f 拖j t ) ，( k 隅i ，t ) ， x l ll 髓ii 置l f ( o ，t ) = i i o k + 1 ) i i o k + 1 ) i i o k + 1 ) k = lk = lk = 1 另外，根据引理；3 ；k 图盆欧垒i 丕亟菡盏： ( 垒，王】三：；- 盘【g & 2 釜】生= j l 苴虫一 n ( g ，k ) 为完全i 部图g 的恰有k 个分支s ( “) - 因子个数，所以 x l ll x 2f 置i j + 1 ) = 1 - i ( t k + 1 ) o 一 + 1 ) 1 - 1 ( 一k + 1 ) k = lk = 1女= 1 其中x 1 + 蜀+ - + 置= n 推论2 2 1 令g = ( x ，y ) 为完全二部图，其中i x i = l y i = 仉并且n = 2 m ，则n ( g ，k ) 满 足如下的卷积公式： 2 r nkm n ( g ，) ( 一j + 1 ) = ( t j + 1 ) 2 k = m j = l k = l 证明由于g = ( x ，y ) 为完全二部图，则根据引理2 1 7 ，g 无蚝子图；根据引理2 1 3 当1 k n 且s ( 1 ，1 ) = s ( 2 ：2 ) = =i ： s ( n ，n ) = 1 ，所以 b ( 1 ，1 ) 0 d e t m = i 0 0 于是，我们有 s ( 2 ，1 ) s ( 2 ，2 ) 其中m k 可以通过把 中第k 列换成 得到，即为 m k 证明完毕 3 ( n ，1 ) s ( n ，2 ) 0 s ( n 一1 ，n 1 ) s ( n ，n 1 ) 00 s ( n ，n ) = 8 ( 1 ，1 ) s ( 2 ，2 ) s ( h ，矗) 二1 n ( g = 等= d e t 慨，1 s sn = 2 m p ( 1 ，1 ) s ( 2 ，1 ) i o s ( 2 ，2 ) m = i ioo ioo 8 ( 1 ，1 ) 0 0 0 s ( 2 ，1 ) s ( 2 ，2 ) 0 0 s ( n 一1 ，1 )s ( n ，1 ) s ( n - 1 ，2 )s ( n ，2 ) s ( m ，1 ) s ( m ，p ) l + p = l s ( m ，1 ) s ( m ，p ) l p = 2 s ( m ，1 ) s ( m ，p ) l + = n 一1 es ( m ，1 ) s ( m ：p ) h 中- - n s ( m ，1 ) s ( m ，p ) l + p = 1 8 ( m ，f ) s ( m ，p ) z + p = 2 s ( m ，1 ) 4 m ，p ) 定理2 3 2 令g = ( x x ，x 2 ，置) 为完全i 一部图，i 2 ，】x 1 l + l x 2 l + + i x i l = n ，则 n ( g ，k ) 满足如下公式： 【( x l ，j ，2 ，置) ，k 】= d e t m k ，1 k n 1 0 o 哪一“ sl n k 0 一ns 大连理工大学博士学位论文 其中 m k ： s ( 1 ，1 ) s ( 2 ，1 ) 0 4 2 ，2 ) 0 0 0 o 兀s ( 1 玛i ，如) ，曩i b = 2 卢1 ns ( | 玛l ，b ) 。曩；o 一，声 兀s ( 1 玛i ，0 ) ，曩b = n 卢1 s ( n - - 1 ，1 )s ( ，l ，1 ) s ( n 一1 ，2 )s ( n ，2 ) o s ( n ，k ) 为第一类s t i f l i n g 数 证明由于图g = ( x h x 2 ，墨) 为完全i 部图，根据定理2 2 1 e n ( g ，k ) n o j + 1 ) = o k + 1 ) i i o k + 1 ) 1 - i ( t k + 1 ) ， k = l ，= 1 k = l k = lk = l nn f x l l x 2 il 置f e 匹n ( c ，) s ( k ，r ) = es ( i x l ，z 1 ) f 1e sc i x 2 1 ，1 2 ) t 2 2 es ( i x d ，圳t r = lk = l l l = 0z 2 = 0k = 0 n = e s ( 1 墨) s ( 阢l ，t 2 ) s ( i x i l ，训， r = 1h + f 2 + - m i = r n t e ( g ，k ) s ( k ，r ) = s ( t x j l ，l j ) ，1 r n ， 其中阻j + i 恐j + + i 五i = i 1 s ( 1 ，1 ) n ( g ，1 ) + 8 ( 2 ，1 ) n ( g ，2 ) + s ( 1 ，2 ) n ( c ，1 ) + 8 ( 2 ，2 ) n ( c ，2 ) + + s ( n ，1 ) n ( c ，n ) =es ( i 玛i ，f j ) 1 曩1 j = l 扛1 t + s ( n ，2 ) g ( v ，n ) =