（应用数学专业论文）二色有序树的研究及其在计算分子生物学中的应用.pdf

国防科学技术大学研究生院博士学位论文 摘要 树是结构非常简单而应用范围非常广泛的一种组合结构。本文研究了二色有 序树、有序树的计数问题和它们与非交叉划分、m o t z l d n 路等组合结构之间的联系 问题。r n a 二级结构的计数研究是计算分子生物学中的重要课题之一，本文通过 二色有序树研究了r n a 二级结构的计数问题。本文的主要工作和创新之处概括如 下： ( 1 ) 本文讨论了满足多个新参数条件的标号二色有序树和非标号二色有序树 的计数问题，得出了多个将在r n a 二级结构计数问题中有直接应用价值的新的完 全显式的闭公式。本文还讨论了多色有序树的计数问题，得出了关于多色有序树 个数的一些新计算公式。 ( 2 ) 本文提出了满足某四个参数条件的标号有序树的一个分拆组装算法，通 过该算法首次直接讨论了这类树的计数问题。通过该算法本文还首次构造了使这 类树中的叶子能在两种类型之间进行转换的对合，从而给出了关于一个计数结论 的组合证明。 ( 3 ) 本文提出了非标号二色有序树的二高度分解算法、非标号有序树的左单 偏路分解算法，首次构造了带某四个参数的非标号二色有序树与带某四个参数的 非标号有序树之间的一个双射，从而对它们个数相等的结论首次提供了一个直接 的组合证明。此外，这里讨论的参数均可以对应到d y c k 路上的某些参数，所以本 文也相当于首次给出了分别满足四个参数条件的某两类d y c k 路之间的一个双射， 从而首次部分解决了c l a r k 在1 9 9 7 年提出的公开问题。 ( 4 ) 本文提出了非交叉划分中块串的概念以及对非标号二色有序树中的边进 行标号的两种不同算法，首次构造了非标号二色有序树与非交叉划分之间的两个 双射，建立了它们之间的组合联系。由其中的一个双射以及非标号二色有序树上 的计数结论，得出了非交叉划分在一些新参数条件下的新计数结论。 ( 5 ) 本文提出了非标号二色有序树的左链树分解算法、m o t z k i n 路的一高度 分解算法，从而首次构造了非标号二色有序树与r i o r d a n 路、m o t z k i n 路、 2 一m o t z k i n 路之间的双射，建立了它们之间的组合联系。 ( 6 ) 在已有的关于r n a 二级结构个数的成果当中，绝大部分是关于个数的 递推关系式或者近似估计值，只有少数几个为完全显式的闭公式。本文提出了r n a 二级结构的极大子结构分解算法，首次构造了非标号二色有序树与r n a 二级结构 之间的一个双射，该双射指出了上述两类对象在很多参数之间存在一一对应关系， 从而提供了研究r n a 二级结构计数问题的一条新途径。本文利用上述双射以及非 标号二色有序树上的计数结论，得到了大量计算r n a 二级结构个数的完全显式的 第i 页 国防科学技术大学研究生院博上学位论文 第i i 页 国防科学技术大学研究生院博士学位论文 a b s t r a c t t r e e sa r et h es i m p l e s tc o m b i n a t o r i a ls t r u c t u r e st h a ta r i s en a t u r a l l yi nd i v e r s e a p p l i c a t i o n s t h i st h e s i sc o n c d t i st h ee n u m e r a t i o no fb i c o l o u r e do r d e r e dt r e e sa n dt h a t o fo r d e r e dt r e e s ，a n ds t u d i e st h ei n t r i n s i cr e l a t i o nb e t w e e nt h e ma n dn o n c r o s s i n g p a r t i t i o n s ，m o t z k i np a t h sa n do t h e rc o m b i n a t o r i a ls t r u c t u r e s e n u m e r a t i o no fr n a s e c o n d a r ys t r u c t u r e si s o r i eo ft h em o s ti m p o r t a n tb r a n c h e si nt h ec o m p u t a t i o no f m o l e c u l a rb i o l o g y u s i n gb i c o l o u r e do r d e r e dt r e e s ，t h i st h e s i sc o n c e r n st h ee n u m e r a t i o n o fr n as e c o n d a r ys t r u c t u r e s t h em a i nw o r ka n dt h ec r e a t i v ea c h i e v e m e n t si n t h i s t h e s i sa r e 嬲f o l l o w s 1 t h ee n u m e r a t i o no fl a b e l l e db i c o l o u r e do r d e r e dt r e e sa n du n l a b e l l e db i c o l o u r e d o r d e r e dt r e e sa r ec o n c e r n e d ，a n dl o t so fe x p l i c i tf o r m u l a ea r ed e r i v e d ，w h i c hw i l lb e u s e dd i r e c t l yi nt h ec o m p u t a t i o no fr n a s e c o n d a r ys t r u c t u r e s t h ee n u m e r a t i o no f m u l t i c o l o u r e do r d e r e dt r e e sa r ec o n c e r n e da l s oa n dm a n yf o r m u l a ea r ed e r i v e d 2 ad e c o m p o s i n ga l g o r i t h mf o rl a b e l l e do r d e r e dt r e e ss p e c i f i e dw i t hf o u r p a r a m e t e r si sd e r i v e da n dt h ee n u m e r a t i o ni sd i s c u s s e dd i r e c t l y b yt h ed e c o m p o s i n g a l g o r i t h m i n v o l u t i o n so n ak i n d o fl a b e l l e do r d e r e dt r e e sw h e r el e a v e sc a l lb e e x c h a n g e db e t w e e nt w od i f f e r e n tt y p e sa r ei n t r o d u c e d ，w h i c hg i v ec o m b i n a t o r i a lp r o o f s t oae n u m e r a t i n gr e s u l t 3 a2 d e p t h d e c o m p o s i t i o no l lu n l a b e l l e db i c o l o u r e do r d e r e d t r e e sa n da l e f t - l a t e r a ld e c o m p o s i t i o no nu n l a b e l l e do r d e r e d 仃e e sa r ei n t r o d u c e d ab i j e e t i o n b e t w e e nu n l a b e l l e db i c o l o u r e do r d e r e dt r e e sa n du n l a b e l l e do r d e r e dt r e e sw h i c ha r e s p e c i f i e dw i t hf o u rp a r a m e t e r sr e s p e c t i v e l yi se s t a b l i s h e dt h ef i r s tt i m e ，w h i c hg i v e s d i r e c t l yac o m b i n a t o r i a lp r o o ft ot h e i re q u a l i t y d u et ot h ef a c tt h a tt h ep a r a m e t e r s d i s c u s s e dh e r ec o r r e s p o n dt os o m eo n e si nt h ed y c kp a t h s ，t h ea b o v eb i j e c t i o ni s a c t u a l l yo n eb e t w e e nt w od i f f e r e n tk i n d so fd y c kp a t h ss p e c i f i e dw i t hf o u rp a r a m e t e r s r e p e c t i v e l y ，w h i c hs e e n l $ t oa p p e a rt h ef i r s tt i m ea n ds o l v e sf i r s t l yp a r to ft h eo p e n p r o b l e mg i v e nb yc l a r ki n1 9 9 7 4 an o t i o n ( i e ，b l o c kr u n ) a n dt w od i f f e r e n ta l g o r i t h m st oa s s i g nl a b e l sf o rt h e e d g e si na nu n l a b e l l e db i c o l o u r e do r d e r e dt r e ea r ep r o p o s e d t w ob i j e c t i o n sb e t w e e n u n l a b e l l e db i c o l o u r e do r d e r e dt r e e sa n dn o n - c r o s s i n gp a r t i t i o n sa r ee s t a b l i s h e dt h ef i r s t t i m et or e v e a lt h e i rr e l a t i o n f r o mt h ef i r s tb i j e c t i o n s e v e r a ln e we n u m e r a t i v er e s u l t so f n o n - c r o s s i n gp a r t i t i o n ss p e c i f i e dw i t hs o m en e wp a r a m e t e r sa r ed e r i v e d 5 al e f t c h a i nd e c o m p o s i t i o no nu n l a b e l l e db i c o l o u r e do r d e r e dt r e e sa n da l l 1 - d e p t hd e c o m p o s i t i o no nm o t z k i np a t h s a r ep r o p o s e d ，a n db i j e c t i o n sb e t w e e n u n l a b e l l e db i c o l o u r e do r d e r e dt r e e sa n dr i o r d a i lp a t h s ，m o t z k i np a t h s ，2 一m o t z k i n p a t h sa r ee s t a b l i s h e dr e s p e c t i v e l yt h ef i r s tt i m et or e v e a lt h e 打r e l a t i o n 6 f o rt h ee n u m e r a t i o no fr n a s e c o n d a r ys t r u c t u r e s ，l o t so fr e e u r s i v er e s u l t sa n d 第i i i 页 国防科学技术大学研究生院博上学位论文 a s y m p t o t i c sa n df e wo fe x p l i c i tf o r m u l a eh a v eb e e ng i v e n am a x i m u ms u b s t r u c t u r e d e c o m p o s i t i o n o nr n as e c o n d a r ys t r u c t u r e si s p r o p o s e d ab i j e c t i o nb e t w e e n u n l a b e l l e db i c o l o u r e do r d e r e dt r e e sa n dr n as e c o n d a r ys t r u c t u r e si se s t a b l i s h e dt h e f i r s tt i m e ，w h i c hr e v e a l st h ec o r r e s p o n d e n c eb e t w e e nt h e i rl o t so fp a r a m e t e r s ，a n dan e w m e t h o dt os t u d yt h ee n u m e r a t i o no fr n as e c o n d a r ys t r u c t u r e si sp r e s e n t e d f r o mt h e b i j e c t i o nh e r ea n dt h ev a r i o u se n u m e r a t i v er e s u l t so fu n l a b e l l e db i c o l o u r e do r d e r e dt r e e s ， l o t so fn e we x p l i c i tf o r m u l a ef o rt h en u m b e ro fr n a s e c o n d a r ys t r u c t u r e ss p e c i f i e d w i t hs o m ep a r a m e t e r sa r ed e r i v e d k e yw o r d s ：l a b e l l e db i c o l o u r e do r d e r e dt r e e ，l a b e l l e do r d e r e dt r e e ， u n l a b e l l e db i c o l o u r e do r d e r e dt r e e ，n o n c r o s s i n gp a r t i t i o n ，r i o r d a np a t h ， m o t z k i np a t h ，r n as e c o n d a r ys t r u c t u r e s 第i v 页 国防科学技术大学研究生院博：七学何论文 表目录 表2 1 标号二色有序树与二色森林之间的参数对应关系18 表4 1 有序树与d y c k 路在参数之间的联系4 4 表7 1r n a _ 二级结构与非标号二色有序树之间存在对应关系的参数8 3 第1 i i 页 国防科学技术大学研究生院博士学位论文 图2 1 图2 2 图3 1 图3 2 图3 3 图3 4 图3 5 图3 6 图4 1 图4 2 图4 3 图4 4 图4 5 图5 1 图5 2 图5 3 图5 4 图6 1 图6 2 图6 3 图6 4 图6 5 图6 6 图6 7 图6 8 图6 9 图6 1 0 图7 1 图7 2 图7 3 图目录 一个标号二色有序树15 与一个标号二色有序树对应的二色森林1 7 一个 13 ，6 ；10 ，5 - 树。3 3 一个 2 2 ，13 ，6 ，5 】一森林。3 3 与图3 1 中【1 3 ，6 ；1 0 ，5 卜树对应的框架子树3 3 一个 10 ，6 ；10 ，3 - 树及其对应的 19 ，1o ，6 ，3 - 森林。3 7 与图3 4 中的【1 0 ，6 ；1 0 ，3 卜树对应的 1 0 ，4 ；1 0 ，3 】一树3 9 与图3 4 中的 1 0 ，6 ；1 0 ，3 卜树对应的另一个 1 0 , 4 ；1 0 ，3 - 树4 1 一个有序树与其对应的d y c k 路4 4 6 个左偏树4 6 有序树上的左单偏分解4 6 二色有序树上的二高度分解4 7 有序树与其对应的二色有序树5 1 有序树上的e 一标号法5 5 有序树上的d 一标号法5 5 一个二色有序树及其对应的非交叉划分5 8 一个二色有序树及其对应的另一个非交叉划分6 1 一个长为n 的m o t z k i n 路6 2 一个r i o r d a n 路6 3 一个2 一m o t z k i n 路。6 3 m o t z k i n 路上的一高度分解6 5 6 个左链树6 5 非标号二色有序树上的左链树分解6 6 一个二色有序树及其对应的r i o r d a n 路。6 8 二色有序树及其对应的m o t z k i n 路。7 0 2 一m o t z k i n 路上的一高度分解7 1 一个非标号二色有序树及其对应的2 一m o t z k i n 路7 2 r n a - - 二- - 级结构中的茎、凸包环、内环、端环、多分支环7 6 两个r n a 二级结构7 9 r n a - 级结构及其对应的非标号二色有序树8 2 第页 独创性声明 本人声明所呈交的学位论文是我本人在导师指导下进行的研究工作及取得的 研究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其 他人已经发表和撰写过的研究成果，也不包含为获得国防科学技术大学或其它教 育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何 贡献均已在论文中作了明确的说明并表示谢意。 学位论文题目：三鱼直庄挝鲍珏窒丞基查过篡金垒堑堂生鲍廑用 学位论文储始萼雄喊7 年夕月，如 学位论文版权使用授权书 本人完全了解国防科学技术大学有关保留、使用学位论文的规定。本人授权 国防科学技术大学可以保留并向国家有关部门或机构送交论文的复印件和电子文 档，允许论文被查阅和借阅；可以将学位论文的全部或部分内容编入有关数据库 进行检索，可以采用影印、缩印或扫描等复制手段保存、汇编学位论文 ( 保密学位论文在解密后适用本授权书。) 学位论文题目：三鱼盔庄挝鲍珏窒区基垄i 篡佥歪垒堑堂生的廑周 日lr 日 茂t 箩b 国防科学技术大学研究生院博士学位论文 1 1 1 选题依据及意义 第一章绪论 1 1 研究背景 1 1 1 1 组合计数概述 组合数学是一门古老而又年轻的科学。组合数学有悠久的历史，其渊源可追 溯到一些古典的数学游戏中。但长期以来由于缺乏生产的刺激，组合数学的进展 一直十分缓慢。2 0 世纪中叶以来出现了许多新兴的应用和理论学科，例如计算机 科学，通讯网络，信息编码，运筹学，试验设计，计算分子生物学等，在这些学 科的带动下，也由于其自身内部的不断发展，古老的组合数学焕发了青春，以迅 猛的速度蓬勃发展以来。目前它不仅成为纯粹科学和应用科学中十分重要的一门 独立的学科，而且它自身已发展出了不少独立的分支，例如图论，组合计数方法， 组合设计，组合最优化，组合群论，拟阵，组合编码理论，格论等等。组合数学 的思想和技巧不仅在数学的其他分支中被采用，而且还涉及到许多自然科学、社 会科学及工艺美术领域，其影响极为广泛【l 】。 组合数学是研究一个对象集合到一个具有指定结构的有限抽象集满足一定条 件的映射( 即某组离散对象中满足一定条件的格局) 的存在性、构造性及计数等 问题。组合计数又是组合数学中的一个最基本的研究方向，主要研究满足一定条 件的格局的数目和计算问题【l 】。组合计数的基本问题是计算一个有限集合的元素个 数问题，通常是给定一个由有限集合s ；组成的无限集族，其中i 取遍某一个指标集 ( 如非负整数集) ，希望能够“同时”计算每一个集合墨的元素个数厂( z ) 。其中 计数函数可以由几种标准形式给出：( 1 ) 给出厂( f ) 的完全显式的闭公式，这是最 令人满意的形式，但这样的公式只在很少的情况下才存在：( 2 ) 用前面已经计算 的f ( j ) 给出厂( f ) 的一个递推关系式；( 3 ) 给出对f ( i ) 的估计，这个估计常常是以 渐进公式f ( n ) g ( n ) 的形式给出，其中g ( n ) 是一个大家“熟知的函数”；( 4 ) 给 出厂( f ) 的生成函数【2 1 。组合计数问题的研究方法与工具很多，既包括诸如生成函数、 反演、递归关系、群论、矩阵论等比较成熟的系统理论或方法【l 】，也包括双射、对 合【2 】等技巧性很强的纯组合方法。在数学的其它分支中，建立两个对象间具体的同 构要比仅仅证明它们同构更好；与此原理相同，组合计数学也认为给出两个有限 集合之间的具体的一一对应( x x 射) 要优于仅仅证明它们元素个数相等【z 】。为证明 某个集合s 的元素个数为聊而构造出s 与另个我们已知有m 个元素的集合之间 的一一对应，这样的证明称为组合证明或者双射证明，一般也认为组合证明是证 第1 页 国防科学技术大学研究生院博上学位论文 明一个计数函数具有某些给定性质的最好方法1 2j 。此外，在某两个已知其元素个数 相等的集合之间，首次构造出或者再次构造出与其它已有双射有本质不同的一一 对应，也是一个很有意义和具有挑战性的组合计数课题。 树是组合数学中结构最简单的一个研究对象，也是最重要且应用范围最广泛 的研究对象。树是k i r c h h o f f 在18 4 7 年为了求解电路理论中一类线性方程组而提 出来的，树在计算机科学的算法设计、数据结构、网络技术、人工智能、软件工 程、知识工程、计算分子生物学以及其它许多领域都有广泛的应用【3 卅。当把树应 用到实际问题中时，树的顶点与边都能表示出实际对象的某些属性。有序树是一 个在兄弟顶点之间规定了左右次序的有根树，这个顶点之间的序能够存储和体现 出实际问题的研究对象之间的明显或隐含信息。二色有序树是在有序树的基础上 增加了一个也能用来存储和体现信息的参数。非交叉划分、格路( r i o r d a n 路、 m o t z k i n 路、2 - m o t z l d n 路等) 是组合数学中的另两个组合结构，其中非交叉划分 也是一个出现在非交换概率( n o n c o m m u t a t i v ep r o b a b i l i t y ) 、低维空间拓扑 ( 1 0 w d i m e n s i o n a lt o p o l o g y ) 、几何群论( g e o m e t r i cg r o u pt h e o r y ) 等其它数学领域 中的研究对象【7 8 】。因此对二色有序树及其与非交叉划分、格路的联系问题进行深 入的研究既有理论意义也有实用价值。 1 1 1 2 计算分子生物学概述 生命科学是2 1 世纪自然科学的带头学科，分子生物学是生命科学中发展最迅 速的学科之一，已成为生命科学研究领域中一颗璀璨的明珠【9 , 1 0 。由于计算机、网 络以及由此导致的信息科学的快速发展，尤其是随着人类基因组计划的快速发展， 大量核酸和蛋白质序列以指数形式呈迅猛的骤增态势，这就要求采用最新的信息 学技术去探索这些核酸和蛋白质序列所蕴藏的生命意义。在这一需求和背景下分 子生物信息学应运而生【l o 】。它以核酸、蛋白质等生物大分子数据为主要对象，以 数学、信息学、计算机科学为主要手段，以计算机硬件、软件和计算机网络为主 要工具，对浩如烟海的原始数据进行存储、管理、注释、加工，使之成为具有明 确生物意义的生物信息。并通过对生物信息的查询、搜索、比较、分析，从中获 取基因编码、基因调控、核酸和蛋白质的结构与功能及其相互关系等理性知识。 在大量信息和知识的基础上，探索生命起源、生物进化以及细胞、器官和个体的 发生、发育、病变、衰亡等生命科学中的重大问题【l 。 核酸( n u c l e i ca c i d ) 是生物体细胞内一类重要的生物大分子，它储存着生物体 内全部遗传信息，它在生物的个体生长、发育、繁殖、遗传和变异等生命过程中 起着极为重要的作用【9 】。核苷酸( n u c l e o t i d e ) 是核酸的基本组成单位，核苷酸又 由碱基、戊糖、磷酸通过一定的结合方式而构成。组成核酸的糖类分为2 种：核 糖( d f i b o s e ) 和脱氧核糖( 2 d e o x y r i b o s e ) ；碱基主要包含5 种：腺嘌呤( a d e n i n e ， 第2 页 国防科学技术大学研究生院博士学侥论文 a ) 、鸟嘌呤( g u a n i n e ，g ) 、胞嘧呤( c y t o s i n e ，c ) 、尿嘧呤( u r a c i l ，u ) 、胸腺 嘧呤( t h y m i n ，t ) 。依照戊糖的不同，可将核苷酸分为核糖核苷酸( r i b o n u c l e o t i d e s ) 和脱氧核糖核苷酸( d e o x y r i b o n u c l e o t i d e s ) 两种【9 , 1 2 】。 d n a 的一级结构是由四种脱氧核糖核苷酸通过3 ，5 磷酸二酯键连接起来的 直线形或环形分子，它主要以双链形式存在，是遗传信息的储存者和携带者。r n a 的一级结构则主要是由四种核糖核苷酸a 、g 、c 、u 组成，它通常是单链线形分 子，但在分子内可通过自身回折，使链中的一部分核苷酸与其它部分核苷酸互补 配对( 一般为a 与u 配对，g 与c 配对) ，形成局部的双链区段( 二级结构) ， 或者进而折叠( 三级结构) 。r n a 既是遗传信息的传递者，也是遗传信息的储存 者和表达者，具有多种生物功能，如生物催化剂的功能、参与蛋白质生物合成的 功能、调控遗传信息的功能等等 9 , 1 2 】。 理解分子的生物功能是生物信息学的核心问题，而分子的序列( 一级结构) 和高级结构( 二级甚至三级结构) 是决定其功能的基础。序列分析和结构模拟与 预测是生物信息学研究的两个主要组成部分，从序列和结构两个方面同时入手研 究生物大分子的功能是最为理想的途径。在过去的几十年里，为了发现大分子的 高级结构，特别是r n a 和蛋白质的三维结构，许多科学家提出了基于原始序列预 测其结构的方法。遗憾的是，与大量的序列数据相比，可用的结构信息依然十分 有限【l 。目前利用现有的预测算法去预测出所有序列的二级结构仍然非常困难， 因此对给定长度的分子序列能够产生的满足一定参数条件的二级结构个数进行估 计或者计算就成了一个有实际应用价值的数学问题。 1 1 2 国内外研究现状 1 1 2 1 树的计数问题研究现状 关于树的计数结果最早出现于1 8 8 9 年，c a y l e y t l 3 】讨论了标号树的计数问题， 分析出了在n 个顶点上的标号树的个数等于玎，但没有给出严格的证明，直到 1 9 1 8 年p r u f “1 4 】才首次对该结论进行了严格的证明，之后有多篇文章【1 5 捌】从不同 的角度用不同的方法对该结论进行了再次证明，其中m o o n 1 6 】在1 9 6 7 年对之前出 现的共l o 种不同证明方法进行了小结和回顾。 在树计数问题的研究历程中，有一种方法就是先考虑满足某些特殊参数条件 的树的个数，然后关于其中的一些参数进行求和，从而得出所要的计数结论( 事 实上这一方法在其它组合结构的计数问题研究中也被经常采用) 。 例如，r e n y i 1 5 】讨论了在刀个顶点上且含k 个叶子的标号树、e r d o s 1 9 】讨论了只 对叶子进行标号的部分标号树、s c h o r 2 0 1 讨论了在忍个顶点上且含k 个反边( 即父 结点的标号比子结点的标号小的边) 的标号树、h a k i m i 2 1 】讨论了顶点的度序列为 第3 页 国防科学技术大学研究生院博士学位论文 某个给定序列的标号树等等。 对有序树计数问题最早进行讨论的是e r d e l y i 2 2 1 ，他在1 9 4 0 年得出了顶点的度 序列为某个给定序列的非标号有序树个数的计算公式。h a r a t y 2 3 】与g o o d 2 4 】较早地 分别计算了在 个顶点上的非标号有序树的个数。对在n + 1 个顶点上且含后个叶子 的非标号有序树的计数，有必要提到现在众所周知的一个数- - n a r a y a n a 数【2 堆6 j 。 n a r a y a n a 数由数学家n a r a y a n a 首先提出，后来的大量研究表明该数不仅刻画了上 述非标号有序树的个数，也等于其它很多满足一定参数条件的组合结构的个数。 m o r d a n t 2 7 1 、d e r s h o w i t z 2 8 1 、c h e n t 2 9 】等人通过不同的方式对在刀+ 1 个顶点上且含后个 叶子的非标号有序树的个数进行了计算，其中c h e r t 2 9 】提出了一种能将一个标号有 序树分解成若干个顶点个数较少的树的分拆组装算法，通过该算法可以对大量不 同参数条件下的树个数进行计算，由于该算法在树的计数领域具有较大的适用范 围和有效性，现在一般称之为c h e n 算：i 去【3 0 , 3 1 】。 在有序树计数问题的研究过程中，人们经常会陆续引入一些新参数，然后对 这些参数条件下的计数问题展开讨论【3 2 - 3 引，事实上在其它很多组合结构的计数问 题中也往往是这样。 例如，e u 3 2 1 利用生成函数研究了有序树上叶子个数的奇偶性问题、c h e n 3 3 】将 有序树中的叶子分成左叶子与右叶子两种并得出了与之对应的有序树个数的生成 函数及该个数的完全显式的闭公式、g e s s e l t 3 7 】利用生成函数与l a g r a n g e 反演公式 等作为工具讨论了标号有序树中的能构成逆序的顶点对个数，又如s a p o u n a k i s 3 8 】 提出了一种对有序树中的顶点和边进行访问的新方式，然后研究了在这种新访问 方式下产生的度序列的性质。 在计数问题的研究过程中，人们会发现有序树的很多不同参数( 已有的参数 或刚引入的参数) 之间存在等价的关系，即分别在这些不同参数条件下的有序树 的个数具有相等的关系。针对这些等价的参数，首次提出或者再次提出与其它已 有双射有本质不同的一些双射作为它们等价性的组合证明，在组合数学中是一件 很有意思的事情【3 0 , 3 9 , 4 0 a 1 1 ，但鉴于双射的提出往往需要敏捷的思维、灵活的技巧、 一定的经验、较强的观察分析能力和灵感【l 】，这些双射的构造也是一个颇具挑战性 的课题。 例如，1 9 9 9 年c h e n 【3 0 】利用c h e r t 算法【2 9 】和其它一定的技巧构造了标号有序树 上的一个对合，给出了“在n + 1 个顶点上且含k 个叶子的标号有序树的个数与在 n + 1 个顶点上且含七个内点的标号有序树的个数相等”的一个组合证呀3 0 】；1 9 9 4 年s c h m i t tm 】通过构造非标号有序树上的一个对合给出了“在n + 1 个顶点上且含k 个叶子的非标号有序树的个数与在n + 1 个顶点上且含七个内点的非标号有序树的 个数相等 的一个组合证明；又如d e u t s c h 4 1 】提出了非标号有序树上的一个双射， 第4 页 国防科学技术大学研究生院博上学何论文 从而既得出。j ，下列两个等价的新参数“度为k 的顶点个数与度为k l 且高度为奇数 的顶点个数”，也对一些旧参数之间的等价性提供了新的组合证明。 在有序树与其它的组合结构之间构造双射，从而发现不同研究对象之间的组 合联系，也是组合数学的研究课题之【4 2 4 7 1 。例如，c h e n 4 7 1 在非标号有序树的基 础上提出了双根树的概念并给出了这类树的一种分解算法_ b u t t e r f l y 分解算法， 通过该算法建立了双根树与自由d y c k 路之间、叶子染色的双根树与自由s c h r o d e r 路之间的双射，给出了经典的c h u n g - f e l l e r 定理及其多种推广形式的组合证明和其 它结论。 二色树是指一个树中的每个顶点都用两种颜色( 例如红色和蓝色) 中的某一 种进行了染色，并使得任两个相邻顶点染了不相同的色。f i e d l e r t 4 引、a u s t i n 4 9 1 、 s c o i n s 5 0 】较早地研究了二色树的计数问题，得出了含刀个红色顶点和m 个蓝色顶点 的标号二色树的个数等于m ”1 万一。1 9 6 4 年t u t t e 5 1 】利用生成函数和l a g r a n g e 反演 公式给出了顶点的度序列为某个已知序列的非标号二色有序树个数的计算公式， g o r d a n 5 2 1 、g o u l d e n 5 3 1 、l a b e l l e t 5 4 】利用不同的方法也对上述计数结论进行了讨论。 在讨论有根树的计数问题时，常见的一种方式是使用“移走根以得到若干子 树”的方式从而得出生成函数满足的等式或递推关系式，而c l a r k 5 5 】首先使用了“移 走叶子 的方案和利用生成函数对非标号二色有序树、标号二色平面树等的计数 问题进行了讨论，给出了对很多己知的计数结论的新组合证明。 d y c k 路( 在有的文献中常称为桥、斜道等等【孙6 3 】) 是与有序树有密切联系的 一个组合结构，它们之间存在一个非常简单的双射【矧，并且从该双射可以直接看 出它们的很多参数之间存在一一对应关系。f l a j o l e t 5 6 1 、g e s s e l 5 7 1 、d e l e s t 5 s l 等讨论 了长为n 且含有k 个u 在偶位置( 见定义4 1 ，定义4 2 ) 上的d y c k 路的计数问题， 发现了上述d y c k 路的个数等于n a r a y a n a 数。k r e w e r a s 及其合作者【5 9 - 矾1 深入讨论 了d y c k 路，发现了多个可用n a r a y a n a 数刻画的参数。他们还得出了至今仍被公 认为是非常漂亮的计数结论：分别满足4 种不同参数条件的三类d y c k 路的个数相 等【6 1 1 。1 9 8 9 年z e i l b e r g e r 以生成函数为工具对上述三类d y c k 路个数的结论和其它 能用n a r a y a n a 数刻画的d y c k 路中的参数给出了新的证明【6 2 】。 上述三类d y c k 路 在某个双射1 4 2 】的作用下对应到分别满足4 种不同参数条件的三类非标号树，其中 两类为非标号二色有序树，类为非标号有序树【5 5 ，6 2 1 。1 9 9 7 年c l a r k s s 】讨论了其 中一类非标号二色有序树，他也同时提出了一个公开问题：找出它所讨论的那类 非标号二色有序树与另两类d y c k 路之间的双射。对他的这个公开问题，至今无人 问鼎。若考虑到之前的一个双射【4 2 】的存在性，那么他的这个公开问题也可以理解 为：找出上述三类非标号树之间的双射或者找出上述三类d y c k 路之间的双射。本 文将给出上述三类非标号树中某两类( 一类非标号二色有序树与一类非标号有序 第5 页 国防科学技术大学研究生院博士字何论文 树) 之间的一个双射，从而解答了上述公开i 、口j 题的一部分。 在关于d y c k 路的计数问题研究中，新的参数6 “8 】不断出现，新的双射【6 3 ，6 5 】 和对创6 9 1 等纯组合的证明过程、新的考虑方式【7 0 】和新的手段与工具【“，6 6 】也不断涌 现。例如s u l a n k e 6 4 , 6 6 在研究过程中首先借助计算机对短长度d y c k 路中的能用 n a r a y a n a 数刻画的参数进行搜索，然后通过建立双射等形式严格证明搜索出的参 数确实能被n a r a y a n a 数刻画。此外，探讨d y e k 路与其它组合结构之间的联系也 是一个重要的研究课题r 7 1 】。 在树的计数问题研究过程中，有的使用了诸如生成函数、l a g r a n g e 反演公式、 递归关系、群论、矩阵论等比较成熟的理论或方法作为工具，有的则借助双射、 对合等技巧性很强的纯组合方法。在它的不停息研究历程中，由于其自身的理论 发展或其它学科的带动，新的研究方式、观察角度、考虑手段、分析技巧时而出 现，新的参数、新的方法、新的结论也不断涌现。本文的第二章将深入讨论在计 算分子生物学领域有直接应用价值的二色有序树的多个参数，得出在这些参数条 件下的二色有序树的多个新计数结论。 1 1 2 2 非交叉划分的计数问题研究现状 非交叉划分是出现在组合数学、非交换概率、低维空间拓扑、几何群论等数 学领域的一个离散结构【7 引。 1 9 7 2 年心e w e r a s 【7 2 1 、p o u p a r d 7 3 】较早地对非交叉划分上的组合性质进行了讨 论。1 9 8 0 年e d e l m a n 7 4 】讨论了集合【甩】- 1 , 2 ，刀) 上含k 个块的非交叉划分个数的 的计算问题，发现该个数恰好等于n a r a y a n a 数。1 9 8 0 年在d i s c r e t em a t h e m a t i c s 的同一期杂志上出现了两篇文章【2 8 刊分别计算了：在n + 1 个顶点上且含k 个叶子 的非标号有序树的个数，和集合 ，z 】上含k 个块的非交叉划分个数，发现它们都等 于n a r a y a n a 数。 上述个数相等的关系，表明在非标号有序树与非交叉划分之间应该存在组合 解释，多篇文章对这种组合联系进行了大量讨论【4 5 4 6 , 7 5 , 7 6 1 ，得出了从不同角度来 考虑的双射。 例如，p r o d i n g e r l 4 5 】构造了在行+ 1 个顶点上且含k 个叶子的非标号有序树与集合 m 】上含k 个块的非交叉划分之间的一个双射，d e r s h o w i t z 4 6 】构造了在n + 1 个顶点 上且含k 个内点的非标号有序树与集合研】上含k 个块的非交叉划分之间的一个双 射。 后来关于非交叉划分自身及其与其它研究对象的讨论仍在大量继续7 7 。8 5 1 ，一 些参数也不断出现。例如，2 0 0 7 年y a n o 8 6 】将块分为单块与多块、内层块与外层块。 非覆盖划分是与非交叉划分有密切联系的另一种划分，一些文章7 9 ，8 6 , 8 7 】对它们进 行了讨论：近年来很多文章【8 , 8 8 - 9 2 】提出了比非覆盖划分和非交拆划分更一般化的概 第6 页 国防科学技术大学研究生院博士学位论文 念或其衍生概念，例如k 一非交叉划分、有禁非交义划分、非交叉连接划分，双侧 对称k 一非交叉划分等等。 现有文献对非交叉划分的计数问题和非交叉划分与其它组合结构之间的联系 问题已进行了大量的讨论，新的参数与新的计数结论也正不断地涌现以及非交叉 划分与其它组合结构的新联系也正不断地建立。本文的第五章将首次引入非交叉 划分上的一个新概念一块串，首次建立非交叉划分与非标号二色有序树之间的组 合联系，以及得出非交叉划分的一些新计数结论。 1 1 2 3m o t z k