（计算数学专业论文）有限和无限符号序列的研究.pdf

摘要 离散动力系统中的揉序列、形式语言中的f i b o n a c c i 序列或更一般的s t u r m 序 列及广义f i b o n a c c i 序列，以及分子生物学中的d n a 序列等在各自的领域中发挥着 重要的甚至是中心的作用同时，作为有限字母表上的序列，有时也称作字，它们又 是组合数学研究的对象本文主要对反对称立方映射的符号序列、s t u r m 序列、广 义f i b o n a c c i 数列以及d n a 序列做了一些研究和讨论，主要内容如下： 第一章主要研究了反对称立方映射符号序列的组合性质对于给定长度我们 讨论了反对称立方映射符号揉序列和三种颜色上本原项链的等价类之间的关系最 后确定了给定长度反对称立方映射揉序列的个数，并给出一个组合解释 第二章研究了s t u r m 序列的组合性质根据其等价定义，对任意的正整数n 和 ，构造了一系列具有梳4 - 1 复杂度的序列，在这些序列的基础上，通过某种粗粒化 的过程又构造了一系列新的s t u r m 序列，并确定了新的s t u r m 序列与原s t u r m 序 列之间的关系 第三章从代数的观点讨论了t 步f i b o n a c c i 数列的w a l l 数的一些性质，给出了 w a l l 致的一些一般属性最后提出了关于w a l l 数的两个问题 最后一章主要在d n a 的比较和分析方面做了一些研究和探讨，并给出了d n a 序列的一个简单表示和数值刻画，在此基础上，对1 1 种生物的d n a 序列给出了它 们之间的相似性分析 关键词：组合学，字上的组合，符号序列，s t u r m 序列，k 步f i b o n a c c i 序列，d n a 序列 a b s t r a c t t h ek n e a d i n gs e q u e n c e si nd i s c r e t ed y n a m i c a ls y s t e m ，s t u r m i a ns e q u e n c e si n t o r m a ll a n g u a g ea n dd n a s e q u e n c ei nb i o i n f o r m a t i c sp l a ya l li m p o r t a n t ，e v e nc e n t r a lr o l ei nt h e i rr e s p e c t i v ef i e l d s a ss e q u e n c e si nf i n i t ea l p h a b e t s ，t h e yd x ea l s o r c a r c ho b j e c t so fc o m b i n a t o r i c so nw o r d s i nt h i st h e s i sw em a k es o m es t u d i e s a n dd i s c u s s i o n sf o rt h cs y m b o l i cs e q u e n c e so fa n t i - s y m m e t r i cc u b em a p si nd i s c r e t e d y n a m i c a s y s t e m s ，s t u r m i a ns e q u e n c e s ，g e n e r a l i z e df i b o n a c c is e q u e n c e sa n dd n a s e q u e n c e s i nt h ef i r s tc h a p t e r ，w es t u d yc o m b i n a t o r i a lp r o p e r t i e so fs y m b o l i cs e q u e n c e s o fa n t i s y m m e t r i ec u b i cm a p si nd i s c r e t ed y n a m i c a ls y s t e m s f o ras v e nl e n g t h w e s t u d yt h er e l a t i o n s h i pb e t w e e nt h ek n e a d i n gs e q u e n c e so fa n t i s y m m e t r i cc u b i cm a p s a n dt h ee q u i v a l e n c ec l a s s e so fp r i m i t i v en e c k l a c e so nt h r e ec o l o r su n d e rt h ef i x i n g o n eo ft h e ma n de x c h a n g eo ft h eo t h e r s ，t h e nd e t e r m i n et h e i rc a r d i n a l i t i e sa n dt r y t of i n dac o m b i n a t o r i a li n t e r p r e t a t i o n i nt h es e c o n d c h a p t e r ，w es t u d yc o m b i n a t o r i a lp r o p e r t i e s o fs t u r m i a ns e q u e n c e s b yar o t a t i o ns e q u e n c e ，a l le q u i v a l e n td e f i n i t i o n o fs t u r m i a ns e q u e n c e s ，w ef i r s t c o n s t r u c tas e r i e so fs e q u e n c e sw i t he o m p l e x i t yk n + 1f o ra n yp o s i t i v ei n t e g e rn a n d ，t h e n ，f r o mt h c s cs e q u e n c e s ，w er e c o n s t r u c to t h e rs t u r m i a ns e q u e n c e sb y s o m ec o a r s e - g r a i n e dp r o c e s s e s ，a n dd e t e r m i n et h e i rr e l a t i o n s h i p sw i t ht h eo r i g i n a l s t u r m i a ns e q u e n c e t h et h i r dc h a p t e ri sc o n t r i b u t e dt ot h ew a l ln u m b e r so ft h ek - s t e pf i b o n a c c i s e q u e n c e s i ti si n t r o d u c e df r o mav i e w p o i n to fa l g e b r a ag e n e r a lp r o p e r t yo fw a l l n u m b e ri sg i v e n t w op r o b l e m sa r ep o s e d i nt h el a s tc h a p t e r ，w ep r e s e n tan e wr e p r e s e n t a t i o no fad n a s e q u e n c ea n d g i v eac o r r e s p o n d i n gn u m e r i c a lc h a r a c t e r i z a t i o n b a s e do nt h e m ，s i m i l a r i t ya n a l y s i s o ft h cc o d i n gs e q u e n c e so fe x e r t1o fb e t a - g l o b i ng e n co fe l e v e ns p e c i e si sm a d e k e y w o r d s ：c o m b i n a t o r i e s ，c o m b i n a t o r i e s o nw o r d s ，s y m b o l i c s e q u e n c e ，s t u r m i a ns e q u e n c e - s t e pf i b o n a c c is e q u e n c e d n as e q u e n c e i i 0 前言 离散动力系统中的揉序列、形式语言中的f i b o n a c c i 序列或更一般的s t u r m 序 列及广义f i b o n a c c i 序列，以及分子生物学中的d n a 序列等在各自的领域中发挥着 重要的甚至是中心的作用同时，作为有限字母表上的序列，有时也称作字，它们又 是组合数学研究的对象字上的组合的研究最早要追溯到1 9 世纪初1 9 0 6 年t h u e 发表了他在重复自由字方面的第一篇文章，这被认为是关于字上的数学研究的起点， 但是从郡以后的几十年，他的研究成果一直不被人们所知遭后来在这方面衔续有 了一些比较分散的研究性文章，但在很多情况下都是对t h u e 一开始所做的结果的 一些重复性的工作系统地进行字上的研究开始于1 9 世纪5 0 年代，分别在巴黎和 莫斯科独立进行在法国，这方面的研究始于m p s c h f i t z e n b e r g e r ，是为了对编码 理论的研充在俄罗斯，关于字的理论主要是ps n o v i k o v 和s a d i a n 为解决群上 b m n s i d e 问题所利用的一种工具真正推动字上的组合理论研究的是ml o t h a i r e 子1 9 8 3 年所写的一本书，书名正是叫做字上的组合学( c o m b i n a t o r i c so nw o r d s ) 这本书覆盖了在那之前几乎所有的这方面的研究成果l o t h a i r e 于2 0 0 2 年出版了 该书的第二卷字上的代数组合学( a l g e b r a i cc o m b i n a t o r i c so i lw o r d s ) 现在一个 关于字的国际会议从1 9 9 7 年开始每两年举行一次，最近的一次于2 0 0 3 年在芬兰的 土尔库举行，第五届i n t e r n a t i o n a lc o n f e r e n c eo nw o r d s 也将于2 0 0 5 年9 月1 3 一1 7 号在加拿大的蒙特利尔举行字上的组合不仅是在数学，而且与其它许多学科都有 紧密的联系，如计算杌科学、物理学和生物学等方面都有广泛的应用，关于字上的组 合的相关文章，请参看3 ，3 5 ，4 6 ，6 1 ，6 2 ，6 3 ，8 0 ，8 3 ，9 9 本文利用字上的组合的方法研究离散动力系统中的揉序列、形式语言中的s t u r m 序列、广义f i b o n a c c i 序列分子生物学中的d n a 序列也有所涉及 大连理上大学博士学位论文：有限和无限符号序列的研究 o 1 离散动力系统中的序列 人类对自然界的研究和观测只能在一定精度下进行 其目的在于对客观事物或 过程的基本不变的性质作出严格的结论精细的测量必定带来大量的数据，而用以 刻画事物根本性质的特征量通常为数不多为了得到这些少数特征量，未必要从大 量精细的原始数据出发符号序列就是在有限精度下考察复杂系统的一个有效的手 段 离散动力学，也称符号动力学，作为动力系统理论中的抽象篇章已经有悠久的 历史，从2 0 世纪2 0 年代开始它已成为数学家证明定理的有效手段6 0 年代中期以 来，随着混沌现象的研究日趋活跃，它由原来极为抽象的符号动力学迅速发展成为 可以为实际工作者所掌握和运用的一种巧妙工具符号动力系统是形式上最简单的 一种动力学系统，它是实际动力学系统的一种粗粒化描述，是一种高度概括和抽象 符号动力学的状态空间或相空间就是符号序列空间，动力学则由移位操作实现 对一个特定的符号序列，从初始点出发。不断地施行移位，就得到一串新的序列，即 相空间中的一串点，这些点就构成了一条轨道，这个过程就是一个动力学过程按照 这种抽象方向发展的符号动力学既适用于连续空问上的动力学，也适用于离散动力 学系统正如1 4 3 】中所说的那样，一方面基于传统的无穷小分析的微分理论难以施 展时，基于粗粒化的符号动力学仍能发挥作用；另一方面，一般的数值方法行不通的 地方它仍提供了定性分析的手段而对于符号序列组合性质的研究，为揭示符号动 力系统本质特征提供了强有力的工具符号序列还可以帮助回答一些整体性的问题， 例如某类映射的参数空间中总共可能有多少长度一定的周期制度 根据文献f 84 所提到的，符号序列的使用可追溯到1 8 5 1 年1 9 2 1 年m o r s e 首先注意到符号动力学方法对于研究动力学系统的重要性f 7 0 1 9 3 8 年m o r s e 和 h e d | u n d 研究动力学系统拓扑理论的一篇文章，标题就是符号动力学1 7 1 1 此后 b o w e n 、r u e l l e 和s i n a i 等人在各态历经理论和微分动力系统理论方面发展了符号 动力学，文献【4 3 1 中对此有详细的介绍 现在对于符号序列的研究已经广泛渗透到物理、生物、化学以及计算机科学等 多个领域对于符号学动力序列的研究主要有下面两方面；一是从符号动力学的应 用角度出发，给出了其在物理学，微分方程和混沌等方面的应用，二是从组合数学的 角度，对符号序列的组合结构及其性质进行了深入的研究 2 第0 章前言 关于符号序列的组合性质的研究是从m i t r o p o l i s ，s t e i n 和s t e i n 的论文 6 6 】开 始，而且这篇文章就发表在组合论杂志上该文中他们并未强调符号序列的动力 学意义，而是从数学的角度对符号序列进行了讨论，发现了由单峰映射所生成的周 期符号序列的一些普适性后人把这些序列称为m s s ( - 一个作者姓氏的第一个字母) 序列，并对此作了广泛的研究如m i l n o r 和t h u r s t o n 于1 9 7 7 年引入揉序列和揉行 列式的概念在非线性科学界中广为流传；c o l l e t 和e c k m a n n 的专著 2 1 1 从数学的角 度，详细讨论了一维映射符号动力学；b r u c k s 在文献【16 】中进一步研究了单峰映射 的m s s 序列，证明了给定长度n 的m s s 序列的个数恰好等于由函数，( z ) = z 2 2 所生成的周期为n 的不同的非负轨道的数目，并且提供了一个算法来构造长为n 的 m s s 序列集到7 1 个珠子的本原项链集之间的双射；c h c n 和l o u c k 在文献1 18 1 中 利用b u r n s i d c 引理，给出了计算符号序列( m s s 序列) 的等价类的一个统一的计算 公式；l o u c k 于1 9 9 7 年在他的文章1 6 q 中深入讨论了n 序列的一些性质，并发现 了m s s 序列的一个纯组合性质，作为公开问题在这上面提了出来这个问题被称为 m s s 序列的奇偶交替性质，该同题被c h e n ，l o u c k 和w a n g 在【1 9 1 中解决；2 0 0 1 年， c h c n 和w a n g 在1 2 0 】中给出m s s 序列与其它一些组合对象之间的双射构造及其 分解性质 本文的第一章利用【2 0 l 中的思想研究反对称立方映射的周期揉序列的组合性 质对于给定长度的反对称立方映射的周期揉序列，讨论并建立了它与同长度三种 颜色的本原项链的等价类之间的关系，然后确定了给定长度反对称立方映射的周 期揉序列的个数 o 2 s t u r m 序列 对于符号序列，我们还可以将其看作是有限字母表上形式语言对于形式语言 语法复杂性的研究也是符号序列当中一个非常重要的研究方向s t u r m 序列是一个 两个字母表上的无限长符号序列，并且对每个正整数n ，它的长为n 的因子恰好有 n + 1 个，因此我们简单地说s t u r m 序列是语法复杂度为n + 1 的无穷序列因为 s t u r m 序列是具有最低语法复杂度的非周期序列，因此是形式语言当中研究得最为 广泛的一类符号序列，它在计算机图形学、博弈论、信号分析、丢番图逼近、自动机 和准晶图形学等方面都有广泛的应用 最早对s t u r m 序列进行深入研究的是m o r s e 和h e d l u n d 【7 1 ，7 2 ，他们证明丁 3 大连理工大学博士学位论文：有限和无限符号序列的研究 在某种意义上s t u r m 序列是一种最简单的非平凡序列并且给出了这些序列的两个 简单的组合解释“s t u r m i e m ”这个术语，更精确一点应该是s t u r m 轨道，是他们在 1 9 4 3 年提出来的，是以数学家c h a r l e s f r a n c o i ss t u r m ( 1 8 0 3 - 1 8 5 5 ) 的名字所命名的， 他因为在计算代数方程的根方面的成就而阿名于世考虑微分方程 y ”+ ，( z ) = 0 这里，( z ) 是一个关于z 的周期为1 的连续函数设该方程的解为y = t ( ) ，则正 如m o r s e 和h c d l u n d 所描述的那样，一个s t u r m 序列可以用来刻画t ( z ) = 0 的解 的分布情况如果k 。表示方程t ( 。) = 0 在区间 n ，n 十1 1 上的解的个数，则无限序 列0 1 k 0 0 1 女0 1 b 0 l h 是一个s t u r m 序列 c o v e n 和h c d t u n d 的文章i 2 3 】和c o v e n 的文章 2 2 j 讨论了s t u r m 序列中的许 多组合性质而s t o l a r s k y 在他的文章 1 0 1 j 中主要研究了连分式、不动点和b e a t t y 序列之间的关系最近二十多年，对于s t u r m 序列的研究有了很大的发展，主要是 从算法、动力系统和字上的组合的角度进行研究 s t u r m 序列具有许多的等价定义，每一个定义都反应了s t u r m 序列的一个特定 的性质这些等价定义包括t w o - d i s t a n c e 序列( l u n n o na n dp l e a s a n t s 【6 5 1 ) 、b e a t t y 序列( d eb r u i j n 3 1 ，3 2 1 ) 、b a l a n c e d 序列、c u t t i n g 序列和r o t a t i o n 序列以及通过某 些算法所作的定义通过构造一个算法来描述s t u r m 序列，给组合数学和数论之间 搭起了一座桥梁而利用因子所定义的s t u r m 序列恰好描述了一个符号动力系统 最先详细研究该序列的也是从这个角度出发的 7 2 1 ，它给出了平滑圆盘上的测地学 的一个描述 对于s t u r m 序列组合结构的研究主要集中在利用其各种等价定义来得到该序 列的的组合性质以及一些有关算法和几何上的性质 2 ，5 ，1 7 ，3 0 ，4 0 ，1 0 5 l 最近研 究较为广泛的是和s t u r m 序列相关的可逆替换的一些内容，特别是f i b o n a c c i 替换 关于可逆s t u r m 替换的文章请参考【1 0 4 ，1 1 0 ，1u 】- 本文中关于s t u r m 序列研究的出发点是基于下面的考虑：既然一个复杂的动力 系统所对应的数值轨道可以约化为一条简单的符号序列，那么一条具有较高语法复 杂度的序列是否可以经过某种粗粒化的过程约化为一条具有较低语法复杂度的序 列? 我们将给出这个问题的一个肯定的回答 本文第二章中我们根据其等价定义，构造了一系列具有女n + 1 的复杂度的序 列，然后对这些序列施行某种租粒化过程得到一系列新的s t u r m 序歹l j ，并给出了它 4 第0 章前言 们与原s t u r m 序列之间的关系 另外，两个字母的f i b o n a c c i 序列是结构最简单的一种s t u r m 序列令 表示 f i b o n a c c i 序列前n 次迭代所包含的字母的个数，得到所谓的f i b o n a c d 数列，而自 步f i b o n a c c i 数列是f i b o n a c c i 数列的推广在第三章中，我们从代数的观点讨论了 女步f i b o n a c c i 数列的w a l l 数的一些性质，给出了w a l l 数的一些一般属性，最后给 出了关于w a l l 效的两个问题 o 3 d n a 序列 d n a 序列是生物信息学的主要研究对象，它是由a ( 腺嘌呤) 、c ( 胞嘧啶) 、g ( 鸟 嘌呤) 和t ( 胸腺嘧啶) 这4 种核苷酸残基所构成因此一个d n a 序列可以看作是 在一个有四个字母的字母表f ，4 ，c g ，丁) 上的字因此，字上的组合学和统计学的工 具和方法可以在d n a 序列的研究中发挥很大的作用 生物信息学就是把基因组d n a 序列信息分析作为源头，找到基因组序列中代 表蛋白质和r n a 基因的编码区，阐明非编码区的信息实质、破译隐藏在d n a 序列 中的遗传语言规律；同时，归纳、整理与基因组遗传语言信息释放及调控相关的转 录谱和蛋白质谱的数据，从而认识代谢、发育分化、进化的规律 生物信息学的内容包括三个层次：基因组信息学、蛋白质的结构计算与模拟以 及分子药物设计这里基因组信息学是生物信息学的源头和基础；蛋白质的结构计 算与模拟是基因组信息学发展的必然结果；分子药物设计是利用蛋白质结构与功能 信息造福人类的有力工具具体的研究内容有序列的比较和分析、构造进化树、基 因预测、r n a 和蛋白质结构预测、d n a 和蛋白质序列的表示和药物设计等等其 中序列比较是生物信息学中最基本也是最重要的问题因为对于d n a 序列，即使 我们考虑它的一个很短的片断，我们也不可能直接得出它表示的对象所具有的信息， 然而如果我们比较不同的序列就有可能得到某些信息然而这个问题非常复杂，至 今还有许多未解决的问题，因此仍有许多工作需要做 本文第四章主要在d n a 的比较和分析方面做了一些研究和探讨，并给出了 d n a 序列的一个简单表示和数值刻西，在此基础上，对1 1 种生物的d n a 序列 给出了它们之问的相似性分析 5 大连理上大学博士学位论文：有限和无限符号序列的研究 总之，本文的主要出发点就是从数学的角度对符号序列进行研究和分析对于 离散动力系统中的符号序列和s t u r m 序列的研究主要采用的是字上的组合的方法， 而对于广义f i b o n a c c i 数列采用的主要是代数的方法随着生物信息学的兴起，对 d n a 序列的研究和分析也变得越来越重要，因此本文也不可避免地要涉及到d n a 序列然而对于d n a 序列，我们只对其中很小的一个方面，即从数值分析的角度进 行了一些探讨，很少涉及其组合性质的生物学意义，而后者也许是有意义的工作，这 将是我们继续研究的课题之一 6 1 反对称立方映射符号序列的组合性质 本章，我们将讨论一维映射的符号序列的组合性质一维映射在实际动力学系 统的研究中起着重要的作用其中研究得最为广泛的一维映射包括单峰映射、反对 称立方映射、裂峰映射罗伦兹映射、一般立方映射和正弦平方映射等单峰映射的 符号序列的组合性质在【2 0 1 中被详细讨论本章主要讨论反对称立方映射的符号序 列 1 1 基本概念 众所周知，比单峰映射多一个临界点的最简单的情形就是立方映射设映射函 数为t z 。+ l = ，( a ，z 。) = 舡i + ( i 一 ) z 。， 此处z j = ( - 1 ，1 ) 且入( 1 ，4 3 是一个参数或参数组合对于给定参数下的反对 称立方映射函数，( a ，。) ，它有两个临界点g 和百，满足： _ 强- - ；哥 它们将映射区间分为三段：才点左侧的左段，c 点右侧的右段以及介于c 和虿之间 的中间段它们分别以字母l ，r 和 ，表示在左右段映射函数是上升的，而在中 间段为下降的给定一个初始点x o j ，通过迭代映射“+ 。= ，( 入，z 。) 可以得到一 条数值轨道 。o ，z l ，。一， ( 1 , 11 ) 若不考虑戤的具体数值，而只考虑它所在的区间，就可以得到集合 l 弓m ，e ，咒】 上的一条符号序列 1 0 0t l ， t 7 ( 1 1 2 ) 大连理j 二大学博士学位论文：有限和无限符号序列的研究 如果对某个l ，w = 弓则该序列就结束这里的符号序列只涉及到三个字母l ， j 和r ( c 和e 可以认为是退化的l 、m 或r ) 显然，符号序列( 1 ，1 2 ) 比之轨道 ( 1 1 1 ) 在描述方法上粗糙的多然而这种只考虑区阃的粗粒化描述，却带来许多简 化，而且更能反映某些本质首先，轨道与符号序列之间可能的多一对应，提供了将 不同轨道按照等价类分类的方法，便于进一步分析研究其次，符号序列只反映映射 拉伸和折叠的本质，只问单调性，不问映射函数的具体形式于是由分析符号序列所 得到的结果具有极大的普遍性，便于刻画和分析共性，为动力系统进行科学的分类 既然我们的研究对象是符号序列，首先必须了解对于给定的反对称立方映射，什 么样的符号序列可以出现，以及对于给定的符号序列是否可以找到一个反对称立方 映射的一条轨道与该符号序列相对应，这就是允字条件，它是决定一个符号序列或 一个字应予禁止或允许的规则， 1 _ 1 1 允字条件 在讨论允字条件之前，首先引进符号序列排序的概念考虑集合 l 口，a f c r ) 上的一个有限符号序列，如果它所含字母m 的个数是奇数，我们就称它是奇的，否 则就称它是偶的对于单个字母有一个很自然的排序 l c m c 口，则构造新的揉 序列字的具体步骤如下： 1 令e l = ( r 石) 、e 2 = ( 虿) 此处( r 0 ) 土分别记为字节r l 和f m 中的较 大者和较小者，其中( r 才) + 为奇，( r 口) 一为偶 2 假定1 = 2 ，则r 弓和刁相邻，它们中间没有其它的揉序列字 3 ，假定e 1 = e u 、岛= e v ，且字母“t j ，此处e 为公共字头，那么： ( a ) 如果p 和u 之一为字母l ，则e 虿为周期最短的中介揉序列字 ( b ) 如果肛和t ，无一为字母l ，则g l 露和( s c ) + l 面为中介揉序列字 1 0 第l 章反对称立方映射符号序列组合性质 由最初给定的揉序列和新生成的揉序列，经过上面的步骤，就可以不断的生成 新的中介揉序列 1 1 3 字上的组合基本概念 下面将给出本章将要用到的一些记号和与字上的组合有关的一些概念 现在，忽略掉动力学背景，仅仅考虑字上的组合这里我们将采用【6 1 中的术语 和记号设a 是一个有限字母表集合令口= a l 口2 o 。( n i ) ，则q 被称为是集合 a 上的一个字，n 被称作口的长度，用f 似) 表示以上的所有字的集合用a 表示 令p = b l b 2 k a ，则( 口l 口2 ) ( 6 1 6 2 b m ) = a l a 2 o 。h b 2 k = a 臼 对于z ， 毫a 。，如果存在两个字u ， a 使得z = 伽o ，则称”是z 的一个因子 ( 如c t o r ) 如果“扣) 是空字，则称 是2 2 的一个左( 右) 因子从定义可以发现空字 和z 本身既是2 - 的右因子又是他的左因子如果”既不是空字也不是z ，则称t ，是 z 的一个真因子为方便起见用u f z 表示 是z 的左因子，v t z 表示u 不是z 的左 因子用z a y 表示z 和y 最长的公共左因子 下面给出本原( p r i m i t i v e ) 的概念如果一个长为n 字w 不能被写成长度比它 的长度短的字u 的幂的形式，即矿，则称枷是本原的如果”可以被写成长为p 的 字t ，的幂的形式，即t u = u k ( k 1 ) ，就说”是以p 为周期的周期字很显然，一个字 是本原的当且仅当它的最小周期等于它本身的长度，一个等价的说法是，不存在 的真因子t 和 使得 = u u = t 接下来定义几个相关的集合 w n = h i 2 t 。i i , = l ，m 或m w = 【jw 。； n 0 k 。( 百) = o 百j n w 。一j 且n 百是揉序列) ； k 。( g ) = o c l a w 。且a d i 百是揉序列) 记k ，( e ) = c ) 和k d c ) = g ) 对于 w ，用( 埘) 表示经过循环置换后 所得到的字的集合，并称( w ) 是一个等价类宣觉上，一个等价类可以被看作是一个 项链( n e c 艘a c g ) 如果两个序列属于同一个等价类就说它们是等价的用”表示 项链( w ) 的互补对，即协= 似) u ( - ) 如果面( w ) ，就称项链似) 是自互补的 ( 3 e ，- c o m p l e m e n t a w ) 很显然 ) 是自互补的当且仅当( ) = 大连理工大学博士学位论文：有碾和无限符号序列的研究 下一节首先给出集合w 上的序列的两个扩展的交替字典序，并且研究了它们 的性质在这个基础上，第三节给出了和揉序列相关的某些计数结果最后，试图给 出这些计数结果的某些组合解释 1 2 两个扩展的交替字典序 由l 和r 所构成的字的交替字典序首先由s u n 和h e l m b e r g 在【m 3 中提出 来对于反对称立方映射，既然存在两个临界点虿和c ，那么我们在原来的交替字 典序的基础上将其扩展令“和u 属于w ，那么： a ，百o r d e r ：如果u 是奇的，则 札，否则u 伽 b c - o r d e r ：如果u 是偶的，则u “，否则“ “ 如果u ，w 满足v t w 和t u 扣，规定石o r d e r 和c - o r d e r 都与最原始交替字 典序是一致的 在这一章1 通常用d 表示e 或g 给定一个字 w ，如果( 1 1 5 ) 在d o r d e r 下成立，就称 是一个d l e x i c a l 字令l i ( d ) = l m ，r ) ，对n 1 ，令 l n ( d ) = o i o w n 且q 是d l e x i c a l ， l ( d ) = u l n ( d ) 下面的两个引理由定义可以很容易就得到，因此我们省略了它们的证明过程 引理13 ：假设o 和p 是属干w 并且有。悃和口协那么，下面的条件是等价的： ( 1 ) 在c - o r d e r 下，口 p i ( 2 ) 在c o r d e r 下，“ p j ( 3 ) 在口- o r d e r 下，西 p j ( 4 ) 在c o r d e r 下西 序 引理14 ：令a ，移，7 和铷是属于w ，如果在c o r d e r 或c o r d e r 下有口矽 t u 1 ) 冀l i 当d = 虿和d = c 时，叫l = r ；如果d = g ，则t = l 或肘，如果口= c ，则。= m 或r 证明：设w 1 = l 则 面假设t j 1 = m 则不论在己o r d e r 还是c o r d e r 下，如 果w nz r ，荫 有w w n ，如果w n = l ，有w 。，在c o r d e r 下，i t w 。这些都与已知矛盾，因此w l = r 1 2 第1 章反对称立方映射符号序列组合性质 假设d = 百且t “= r 或d = c 和u 。= l 则在 c - o r d e r 下w w 。或在 c o r d e r 下w 。 v s 不难验证u t v s 由不等式v t w t v s 可得到 是 w r 的一个左因子，并且，如果( f s ) = ( l ， n 则r ，是奇的：如果( t s ) = ( ) ，则 ”是偶的既然这样，令”= ”u ，就得到 m u t l 又因为在c - o r d e r 下如果“以m 开头，则有u t m ，若l i , 以l 开头，则有u 丁 l ， 这样就得到矛盾，因此说在刁一o r d e r 下v t 乜f 丁 现在假设v t 行同上面的讨论类似，我们有 v t 行 v s 因此t 一是丽的一个真左因子令而= r 这样就得到 l 行 m 又是一个矛盾，因此i 万 v t 所以说葫5 ( v t w 丁 接下来，考虑c o r d e r 这一次，令s 和丁表示m 和r ，也就是，( s t ) = ( r ，m ) 或( m ，r ) 假设w s l 。( g ) ，需要证明w 丁l 。( g ) ，也就是说，对于的每一个右因子 u ，不等式五厅 w t ，那么 v s t v t 由此可以得到 是 的一个左因子，并且如果( t ，s ) = ( r m ) 则”是偶的，如果 ( t ，s ) = ( m ，r ) ，则u 是奇的这样的话，令1 1 ) = u u ，就有 m u t r ，如果t 以m 开头，有 a t m 这样使得到一个矛盾 ( 2 ) 如果v t w t ，那么 v t m 口 由上面的讨论我们知道，给定一个字 w ，如果u 是偶的则有 v l u 百 v m ； 同样如果”是奇的就有 v m 刁 u l 对偶的，如果 是偶的有 v m v c u 兄： 如果u 是奇的有 r 1 有t u = 如果u 是偶的，那么，作为仙的一个左因子，由定义有u u 另 一方面，u 也是w 的一个右因子，因此必定有 这就得到矛盾，故u 是奇的同 样的，如果女 2 ，那么”2 是偶的、并且它既是 的左因子又是t j 的右因子因此有 = 2 令“是1 ，的任意一个右因子那么u 也是1 的一个右因子由硒