（应用数学专业论文）四角链的一些极值问题.pdf

中文摘要 摘要 在组合图论中有一个所谓的“细胞生长”问题，它与动物的发育 很类似：从一个特定的正多边形( 相当于一个细胞) 开始，在平面上一 步步向外“生长”，每生长一步即在其外围添加一个相同的细胞且 至少有一条边完全重合。如果细胞是一个正方形，则称生成的动物 为p o l y o m i n o e s 。p o l y o m i n o e s 的研究拥有很悠久的历史，早在2 0 世纪初人 们就开始研究它，其中有关数学方面的研究主要集中在覆盖问题、非 同构计数问题、匹配计数与排序问题等方面。迄今为止，人们在这些 方面已经取得了很多成果。- - r p o l y o m i n o 同时也是由方点阵中有限多个 以边相连接的正方形的并所组成的一个平面几何图形。在统计物理学 中，m 竹阶方点阵和m n 阶六角点阵中独立集的计数分别被称为h a r d 四 角问题和h a r d 六角问题。 本文我们考虑一类特殊的方点阵四角链( p o l y o m i n oc h a i n ) 关于k 一匹 配数和舡独立集数等参数的极值问题。设磊表示所有含n 个正方形的四 角链的集合。对任意四角链磊，分别用m ( ) 和i k ( 死) 表示的虹 匹配数和缸独立集数。本文我们证明了对任意四角链五和任 恿k 0 ，m k ( l 。) m k ( t 。) m s ( 磊) ，i k ( l 。) i s ( 品) 如( 磊) ，且左 边的等式对所有k 成立当且仅当死= “，右边的等式对所有k 成立当且 仅当晶= 磊，这里k 和磊分别表示线性四角链和锯齿四角链。最后 我们分别给出四角链的h 0 8 0 y a 指标( 即m ( 死) ) 和m e r r i f i e l d - s i m m o n s 指 标( 即 砝( 晶) ) 的上下界及其递推式。 关键词：四角链；舡匹配数；k 独立集数。 英文摘要 a b s t r a c t c o m b i n a t o r i a lp r o b l e mk n o w na sc e l l g r o w t hp r o b l e mw h i c hc o m e sf r o m8 n a n a l o g yw i t ht h eg r o w t ho fa n i m a l sc a nb ep r e s e n t e da sf o l l o w s ：s t a r t i n gf r o m as i n g l es p e c i f i e dr e g u l a rp o l y g o n a ls h a p e ( s a yac e 叻，g r o w ss t e pb ys t e pi nt h e p l a n eb ya d d i n ga te a c hs t e pan e w c e l lo ft h es a l i l es h a p et oi t sp e r i p h e r ys u c h t h a tt h e r ei sa tl e a s to n ec o i n c i d e ds i d e i ft h eb a s i cs h a p ei sa s q u a r e ，t h ea n i m a l s a r ec a l l e dt h ep o l y o m i n o e s p o l y o m i n o e sh a v ea l o n gh i s t o r y , g o i n gt ot h es t a r to f t h e2 0 t hc e n t u r y t h em a t h e m a t i c a lr e s e a r c ha b o u tp o l y o m i n o e sf o c u s e sm a i n l y o np r o b l e m s ：t i l i n gw i t hp o l y o m i n o e s ，p o l y o m i n o e se n u m e r a t i o n s ，m a t c h i n g s c o u n t i n g ，o r d e r i n gp o l y o m i n o e sa c c o r d i n gt os o m ep a r a m e t e r s ，e t c s of a r ，m a n y r e s u l t sh a v eb e e na c h i e v e do nt h e s ea s p e c t s ap o l y o m i n oi sa l s oag e o m e t r i c p l a n ef 培u r em a d eo ft h eu n i o no ff i n i t e l ym a n ye d g e - c o n n e c t e ds q u a r e sf r o mt h e r e g u l a rs q u a r el a t t i c e i ns t a t i s t i c a lm e c h a n i c s ，t h ee n u m e r a t i o no fi n d e p e n d e n t s e t so fm ns q u a r el a t t i c e sa n dm nh e x a g o n a ll a t t i c e sa r ek n o w na sh a r d s q u a r ep r o b l e ma n dh a r dh e x a g o np r o b l e m ，r e s p e c t i v e l y i nt h i sp a p e rw ew i l lc o n s i d e rs o m ee x t r e m a lp r o b l e m sc o n c e r n i n gk - m a t e h i n g s a n dk - i n d e p e n d e n ts e t sa n do t h e rp a r a m e t e r so fas p e c i a lk i n do fs q u a r el a t t i c e ， t h ep o l y o m i n oc h a i n d e n o t eb y 磊t h es e to fp o l y o m i n oc h a i n sw i t hns q u a r e s f o ra n y 磊，d e n o t eb ym k ( t n ) a n di k ( 瓦) t h en u m b e ro fk - m a t c h i n g s a n dk - i n d e p e n d e n ts e t so f 品，r e s p e c t i v e l y i nt h i sp a p e r ，w es h o wt h a tf o r a n yp o l y o m i n oc h a i n 霸a n da n yk 0 ，m k ( l n ) i n k ( 晶) i n k ( z n ) a n di k ( l n ) si k ( ) si k ( 磊) ，w i t ht h el e f te q u a l i t i e sh o l d i n gf o ra l lko n l yi f = l n ，a n dt h er i g h te q u a l i t i e sh o l d i n gf o ra l lko n l yi f 死= 磊，w h e r el n a n d 磊a r et h el i n e a rp o l y o m i n oc h a i na n dt h ez i g - z a gp o l y o m i n oc h a i n ，r e s p e c - t i v e l y a tl a s tt h eu p p e ra n dl o w e rb o u n d so ft h eh o s o y ai n d e x ( 女m ( r ) ) a n d m e r r i f i e l d - s i m m o n si n d e x ( i k ( ) ) o fp o l y o m i n oc h a i n sa n dt h e i rr e c u r s i o n s a r e 百v e n ，r e s p e c t i v e l y k e yw o r d s ：p o l y o m i n o e s ；k - m a t c h i n g s ；k - i n d e p e n d e n ts e t s i i 厦门大学学位论文原创性声明 兹呈交的学位论文，是本人在导师指导下独立完成的研究成 果。本人在论文写作中参考的其他个人或集体的研究成果，均在 文中以明确方式标明。本人依法享有和承担由此论文产生的权利 和责任。 声明人( 签名) ：暗抱袱 瑚6 年f 月2 f 日 厦门大学学位论文著作权使用声明 本人完全了解厦门大学有关保留、使用学位论文的规定。厦 门大学有权保留并向国家主管部门或其指定机构送交论文的纸 质版和电子版，有权将学位论文用于非赢利目的的少量复制并允 许论文进入学校图书馆被查阅，有权将学位论文的内容编入有关 数据库进行检索，有权将学位论文的标题和摘要汇编出版。保密 的学位论文在解密后适用本规定。 本学位论文属于 1 、保密() ，在年解密后适用本授权书。 2 、不保密( ) ( 请在以上相应括号内打“4 ”) 作者签名：喏艳张 导师签名： 日期：沙0 6 年j 月玎日 日期：年月日 第一章引言 曲凸田廿 图1 熟悉俄罗斯方块游戏的人对图1 中由4 个相同的正方形以边相连接所 组成的几何形状一定不会陌生，他们又称为四阶p o l y o m i n o e s 。进一步 地，我们将所有由数个相同的正方形以边相连接所组成的几何形状都称 为p o l y o m i n o e s 1 1 。为方便起见，我们将- - 个p o l y o m i n o e sg 所包含的正方 形个数称为g 的阶数，记作o ( c ) ；而将n 阶p o l y o m i n o e s 称为n - o m i n o e s 2 1 。 p o l y o m i n o e s 是组合数学中“细胞生长”( c e l l g r o w t h ) 问题的一个研究 对象。“细胞生长”问题与动物的发育很类似：从一个特定的正多 边形( 相当于一个细胞) 开始，在平面上一步步向外“生长”，每生长 一步即在其外围添加一个相同的细胞且至少有一条边完全重合。如 果细胞是个正方形，则称生成的动物为p o l y o m i n o e s ；如果细胞是一 个正六边形或等边三角形，则分别称生成的动物为h e x a g o n a la n i m a l s 或t r i a n g u l a ra n i m a l s ( 参见图2 ) 3 1 。 匝田p0 0 0 1 ) p o l y o m i n o e s ( 2 ) lr i a n g u l a r a n i m a l s 图2 s i m p l y c o n n e c t e da n i m a l s p o l y o m i n o e s 拥有很悠久的历史，起源可追溯到2 0 世纪初，但它们是现 代才被g o l o m b 和g a r d n e r 在他主编的s c i e n t i f i ca m e r i c a n 的“m a t h e m a t i c a l g a m e s ”专栏中普及。之后许多关：于- p o l y o m i n o e s 的文章和问题出现在杂 r e c r e a t i o n a lm a t h e m a t i c s j ： 3 。 p o l y o m i n o e s 不仅可以做出好玩的游戏，它更与数学上的几何学、组 合学与图论等有着密切的联系。在验证一些图形是否能拼出时，我们经 第章引青 常用到归纳法、反证法、抽屉原理和对偶原理等数学技巧( 1 l o 后来人们 发现它也有很强的统计物理背景，可以作为气体分子在固体表面上吸附 的模型，也可以作为二维的气体分子模型。 下面我们用图论观点来阐述一下p o l y o m i n o e s 。 p o l y o m i n o e s 是一个有限2 _ 连通平面图，它满足： 1 每个内部面都是一个单位正方形； 2 两个正方形若相邻，则他们的公共部分必须是一条完整的边。 比如在图3 中，只有( 1 ) 才是p o l y o m i n o e s 4 。 胡品寸 ( 1 ) ( 2 )( 3 ) 图3 这里我们要说明两点： 第一，一般提到的p o f 可d m m o e s 都包括带“洞”的情形，即允许其内部 面被挖空，并称这样的p o l y o m i n o e s 奠3 多连通的( m u l t i p l y c o n n e c t e d ) 反之 称那些不带“洞”的p d f 鲈晰“彻e 8 为单连通的( s i m p l y - c o n n e c t e d ) ( 4 ) 3 。 本文只对s i 唧f 扩c d n 礼e d e d p o l y o m i n o e s ( 又称为平面四角系统) 进行讨论。 匝田 口 s i m p l y - c o n n e c t e dp o l y o m i n o e sm u l t i p l y c o n n e c t e dp o l y o m i n o e s 图4 第二，在组合问题中一般所指的p o l y o m i n o e s 是f r e ep o l y o m i n o e s ，它 允许旋转、翻转和平移，o p o l y o m i n o e s 被看成是不同的，如果它们具有 不同的形状，而与它们在平面上的方位和位置无关。另外还有o n e - s i d e d p d f 可d m i n d e s ( 只允许旋转和平移) 和f i x e dp o l y o m i n o e s ( 只允许平移，与方位 有关) f 2 】。比如图5 ( 1 ) ( 2 ) 两个图为相同的f r e ep o l y o m i n o e s ，为不同的f i x e d p o l y o m i n o e s 3 1 。不加说明的话下文的p o i y o m i n o e s 均指f r e ep o l y o m i n o e s 。 且若两个图g l 、g 2 相同则记为g 1 = g 2 ，不同则记为g 1 g 2 。 第一孥引言 口 图5 上述两点其实是对p o l y o m i n o e s 进行计数的两个标准。 从数学角度来看，有关p o l y o m i n o e s 的研究主要集中在以下几个方面： 第一，覆盖问题( t i l i n gw i t hp o l y o m i n o e s ) 。 这是最基本的组合问题，起源于人们对卵f ! ，d 删礼o 拼图谜题的研究， 即利用所给一些低阶p o f 掣d m 讯。e s 能否不重不漏地恰好盖住指定区域( 通常 为一些特殊形状，如一个m n 的矩形) ? 如果能的话，共有几种覆盖 方法? 例如用1 2 个衅疵d m i n d e s ( 即5 - d 删礼o e s ) 能否恰好盖住一个2 3 0 ，3 2 0 ，4 1 5 ，5 1 2 或6 1 0 的矩形? 关于这方面的问题还有很多，具体可 参见 5 ，6 】，其中有些问题已得到完美解决，有些问题仍未得到解决。 第二，非同构计数问题( e n u m e r a t i o n ) 。 即给定了n 个细胞，共可以产生多少个不同的a n i m a l s ? 对此我们按上述提到的两个标准分别给予回答。 对于第一种标准，2 6 阶以内单连j l 匿p o l y o m i n o e s 计数的结果可参 见序y l j a 0 0 0 1 0 4 1 7 ，2 3 阶以内多连j l 萄l p o l y o m i n o e s 计数的结果可参见序 y l j a 0 0 1 4 1 9 1 7 。虽然l u n n o n 、r e d e l m e i e r 、c o n w a y 和o h v e i r aes i l v a 等人在 算法的设计改进及其在计算机的实现上做出重要贡献f 8 ，9 1 ，但是随着阶 数n 的增大，单连通和多连j 遵p o l y o m i n o e s 的具体数值也越来越难确定，于 是人们退而求其次寻找它的上下界f 3 】。 记i p ( n ) 为n 阶多连通叫妒d m 豫粥s 所有非同构形状的总数。 d a v i da k l a r n e r 在1 9 6 6 年证明了存在一个常数刖即k l a r n e r 常数1 ，使 得当n 趋于无穷时，p ( 几) 的增长近似于j p ，即l i m ( p ( 扎) ) ：= k 。 经过不断改进，目前关于k l a r n e r 常数k 下界的最好结果是3 9 + ( k l a r n e r 和w a d es a t t e r f i e l d ) ；而关于上界的最好结果是4 6 4 9 5 5 1 ( k l a r n e r 和r o n a l dr i v e s t ) ，但k 的精确值仍不得而知。 3 第一章引言 公开问题：猜想l i m 旦g 肄= k 是否成立? n 。、， 对于第二种标准，我们用，r e e ( 礼) 来表示包含n 个细胞的f r e ea n i m a l s 的数目，) 3 日f i x e d ( n ) 来表示包含n 个细胞的f i x e da n i m a l s 的数目f 3 】。 表l 2 4 阶以内的，括引( n ) 和，r e e 加) p o f 驷仃“n 卯8 的值 f i x e d ( n )f r e e ( n )缸e d ( ) 丘( n ) 1ll1 31 9 03 8 帅2 38 5 9 1 2211 47 2 04 3 7 49 01 9 7 1 3621 52 7 3 94 6 6 63 4 26 5 7 6 41 951 610 4 5 92 9 3 71 3 0 79 2 5 5 56 31 21 740 0 7 95 8 4 45 0 1 07 9 0 9 6 2 1 63 51 81 54 0 8 20 5 4 219 2 6 22 0 5 2 77 6 01 0 81 95 9 如7 38 6 7 674 2 6 24 2 3 2 8 2 7 2 5 3 6 9 2 02 2 96 4 7 7 9 6 6 02 87 0 6 7 1 9 5 0 99 9 1 01 2 8 52 18 8 98 3 5 12 7 8 31 1 12 3 0 60 6 7 8 1 0 36 4 4 64 6 5 52 23 4 5 53 2 5 72 6 7 84 3 l9 1 8 57 6 8 8 1 11 35 2 6 817 0 7 32 313 4 4 37 2 3 35 5 2 41 6 8 04 7 0 07 7 2 8 1 25 05 8 6 163 6 0 02 452 3 9 98 8 7 70 2 6 86 5 4 99 9 7 00 4 0 3 从1 9 6 2 年舶a d 得到许多关于加l y o m i n o e s 计数的理论结果至今，人们虽 然花费了大量精力去寻找一个f i x e dp o l y o m i n o e s 的计数公式，但都失败 了，而只是得至l i f r e e ( n ) 和f i x e d ( n ) p o l y o r n i n o e s 的一些界如下【3 】： k l a m e r ：盥：1 8 必茎f r e e ( n ) f i x e d ( n ) 。 e d e n ：对于充分大的n ， ( 3 1 4 ) n f i x e d ( n ) 4 n 。 但e d e 给出的上界的证明很可疑，后来被k l a r a e r 和r i v e s t 改进了。 e d e n ，k l a r n e r ，r e a d ：l i m ( f i x e d ( n ) ) 1 n = 0 存在，且3 8 7 0 4 6 5 。 l u n n o n 8 最成功算出1 8 阶内，r ee f i x e d ，s y m m e t r i cp o l y o r n i n o e s 数。 r e d e l m e i e r 9 算出t 2 4 阶内f r e e ，f i x e d p o l y o m i n o e s 的数目( 见表1 ) 。他的 算法会产生一个接一个的f i x e dp o l y o m i n o e s 并自动计数，但这个算法的 时间复杂性很不理想。现在对于3 0 阶以上f i x e dp o l y o m i n o e s 的计数还很 难。k l a r n e r 1 0 给出了一些关于p o l y o m i n o e s 计数的公开问题如下： 问题1 ：f i x e d ( n ) 的计算是否存在多项式算法? 一d 一 第一章引苦 问题2 ：是否能找到一个多项式算法，对每个帆，e 的近似值9 。满足： 1 0 一礼 l e 一e i 1 0 一n + 1 7 问题3 ：定义某个趋向于0 的递减序列卢= ( 8 1 ，屈，) ，且对每个n ，给 出一个算法来计算阮。 问题4 ：证明对所有的n ，( f i x e d ( n ) ) 1 n 兰( f i x e d ( n + 1 ) ) 1 肋+ 1 ) 。 i ；1 题5 ：证明对所有的n ，r ( 礼) 7 - + 1 ) ，这里r ( 几) = 等塞涤擎。 问题6 ：生成函数t ( z ) = f i x e d ( n ) z ”是不是有理函数? 或者更进一 步地，t 是代数的吗? 第三，匹配计数与排序等相关问题。 图的完美匹配在量子化学中称为k e k u l d 结构，在统计物理学中称 为d i m e r 构形。人们已经证明了四角系统的完美匹配与统计物理学中 的d i m e r 亩 题( 即用2 m n 个d o m i n o e s 不重不漏地恰好覆盖一个2 mx2 n 矩形 共有多少种不同的覆盖方法) 有直接的联系 1 l 一1 5 】。四角系统完美匹配的 存在性问题已经得到解决【1 6 】o 另外有关四角系统的匹配计数也已经有了 许多重要结果 1 5 ，1 7 - 2 0 。 而图关于匹配数的排序，尤其是关于匹配数的极图，在早期文章已 有研究 2 1 2 5 1 ，相应的研究结果在化学方面的应用很大。对于图的许多 其它不变量，如全丌一电子能量和独立集数，类似的排序或极值问题也有 所研究 2 5 - 3 2 。- - 个p o l y o m i n o 同时也是由方点阵中有限多个以边相连接 的正方形的并所组成的一个平面几何图形。在统计力学中，m n 阶方 点阵和mx 礼阶六角点阵的独立集数的计数分别被认为是h a r d 四角问题 和h a r d 六角问题。最近几年里，物理学者和组合论学者对这些问题产生 很大兴趣 3 3 - 3 s 。 本文我们将考虑一类特殊的方点阵四角链( p o l y o m i n oc h a i n ) 关于舡 匹配数和缸独立集数的极链。前面我们已经定义了平面四角系统， 而一个四角链是指这样一个平面四角系统，连接其相邻两个单位正 方形的中心构成一条路c l c 2 c 。( v n n ) ，这里q 是第i 个正方形的中 心0 = 1 ，2 ，佗) 。 让我们回想一些基本概念。一个六角系统是一个有限2 一连通平面图， 5 且每个内部面都是一个单位正六边形。而一个六角链是指满足以下两个 性质的六角系统：( 1 ) 它没有一个顶点属于三个六边形；( 2 ) 它没有一个六 边形与多于两个的六边形相邻f 2 5 1 。 在参考文献【2 5 l 中，l z h a n g 和f z h a n g 确定了六角链关于缸匹配数 $ 1 k 一独立集数的极链。在参考文献f 3 9 1 中，l z h a n g 和f t i a n 确定了树 状六角系统的h o s o y a 指标和m e r r i f i e l d - s i m m o n s 指标的上下界。在参考文 献 3 0 ，3 1 1 中，l w a n g 、z l i 和f ，z h a n g 确定了六角链关于全开电子能量 的极链。 由于四角链和六角链本身所具有的相似性每个六角链或四角链都 可被归纳地构造，且在每一步中粘贴一个新的细胞到前面的那个细胞， 我们将对四角链考虑类似的问题，即确定四角链关于珏匹配数和缸独立 集数的极大极小链。注意到这个问题并不像乍看起来那么简单，四角 链和六角链在本质上还是有些差别的六角链中相继粘贴的边是不交 的，而四角链中相继粘贴的边可能是相交的( 参照图1 ( b ) 中的锯齿链) 。这 个性质使得六角链中数学归纳法比较容易实现，而四角链中数学归纳法 的实现则比较困难。为了解决这个困难，本文引进一个“双重”标号来 表示死中的粘贴边，这个我们将在下一章解释。进一步地，我们分别给 出了四角链的h 。8 0 y a 指标( 即四角链的所有匹配数) 和m e r r i f i e l d - s i m m o n s 指 标( 即四角链的所有独立集数) 的上下界及其递推关系式和部分一般表达 式。另外我们指出，为了确定四角链关于全什电子能量的极链，我们将 面临着更为严重的困难，而这个困难目前我们还无法克服。 6 第二章预各知识 第二章预备知识 为了证明本文的主要结论，我们先给出一些定义和引理。 设五表示所有礼阶四角链的集合。 定义2 1 设死磊，若死由三度顶点导出的子图恰好构成n - 2 个正 方形，则称为线性链，记为l 。；若由大于二度的顶点导出的子图构 成n - 1 条边的路，则矗称为锯齿链，记为磊。图6 ( 1 ) 1 和图6 ( 2 ) 2 分别图解 了k 和磊。 a o a 1 a n 2 a n 1a n b ob ， b 。2b 。，b 。 v 1 ( 1 ) l 。 图6 v n 一， u n - i n n u ov 2 ( 2 ) z 。 定义2 2 2 5 ，2 9 1 设g 是个无环无重边的图。对任意一个正整 数k ，m k ( g ) 表示g 中的b 匹配数，即g 中舡元独立边集的个数。另外， 对所有的图g ，我们一致地定义：啪( g ) = 1 ，m k ( o ) = o ( k 0 ) 。 定义2 3 1 2 5 设g 是个无环无重边的图。对任意一个正整数k ，i k ( g ) 表 示g 中k 一元点独立集的个数。另外，对所有的图g ，我们一致地定 义：i o ( g ) = 1 ，i k ( g ) = o ( k 0 ) 。 1 将在第一章提刊的路。1 c 2 “一捌的点依次标i d 为a o ，b 1 ，另一侧的点依次标i d a h o ，b l ，h - 2 酋先将由大于二崖的顶点导出的m 1 条边的路依次标记为如“1 “。一1 ，且连续地将枉第r i 叶i f 方形中与“。一1 相 邻且未标记的点标记为u 。对任意 1 ，n - 将住第f 个正方形中与m 相邻且来标记的点标 己为“a 7 第章预各知识 定义2 4 2 5 ，3 9 】根据定义2 ，2 ，图g 的互( 计数) 多项式，t 扫h o s o y a 定义为 z ( g ) = m k ( a ) z ， 当。= 1 时即为图g 的h o s o y a 指标( g 的所有匹配数) ，记为 p = m k ( g ) 南 显然两者在本质上具有相同的组合内容。 定义2 5 2 5 ，3 9 1 根据定义2 3 ，图g 的y - 多项式定义为 y ( g ) = i k ( a ) z 2 ， 当卫：1 时即为 g i 举j m e r r i e f i e l d - s i m m o n s 指标( g 的所有独立集数) ，记为 拶一i ( g ) t 显然两者在本质上具有相同的组合内容。 定义2 6 1 2 5 设，( z ) ：苎矿，g ( 卫) ：釜b k 矿为z 的两个多项式。我 七；ok = o 们定义两个偏序如下： ( 1 ) 若对每个( o 南n ) 有a k b k ，则称，( 嚣) ! g ( $ ) ，即，( z ) 一g ( z ) - a _ o ； ( 2 ) 若，( z ) ! g ( 茁) ，且存在某个k 使得o , k - y ( l 。) ， ( b ) 若晶磊，则y ( 靠) - ( l n a n 一1 ) = ( l n 一6 n 1 ) ， ( b ) l 。一1 = ( l 。一a 。一k ) _ ( 五。一一a n - - 1 ) = ( l n k k 1 ) ， ( c ) ( 磊一) ( 磊一一1 ) ， ( d ) ( 二k 一嘶。) 卜( z k 一嘶t ) ( 竹3 ) ， ( e ) ( 一z ( ”) 一( ”) ) _ ( 死一z ( ”) 一x n 1 ) 。 证明 ( a ) 参照图6 ( 1 ) ，我们显然有旺1 a 1 ) = ( l 1 0 0 ) 。对于n22 ，因 为( k l a 。一1 ) = ( l n 一1 一k 1 ) ，由( 3 2 2 ) 矢日 ( l 。一a 。) 一( l n a n 一1 ) = ( 1 + z ) ( 厶。一1 一a n 一1 ) + ( 三。一1 一a r z - i 一6 n 一1 ) + z ( 三n 一1 一n n 一1 一a n 一2 ) 一“1 + z ) ( 三n 一1 一a n 一1 ) + z ( l n 一1 一a n - 1 6 h 1 ) = z ( k 一1 一a n - 1 一a n 一2 ) - 0 ， 从而( _ l 。一b n ) = ( l 。一a 。) - ( l 。一a n 一1 ) = ( 厶。一b n 一1 ) 。 1 2 第三章四角链的主要结论 ( b ) 显然( l l a 1 6 1 ) = ( l 1 一a l n 0 ) 。对n 2 ，由( 3 2 5 ) 知 l n 一1 一( l n a n a n 一1 ) = ( k 一1 一a n - 1 ) + z ( l n 一1 一a n 一1 一k 一1 ) + x ( l n 一1 一a n - 1 一a n - 2 ) 一 ( l n 一1 一一1 ) + z ( l n 一1 一一1 一b n 1 ) ) = x ( l n 一1 一a n l a n 一2 ) y - 0 ， 从而l n 一1 = ( l n a 。一) 卜( 厶一a n o 。一1 ) = ( 厶一b 。一b n 1 ) 。 f c ) 用归纳法证明。 ( i ) 礼= 2 1 a ，由弓i 理3 1 ( a ) ，( z 2 一u 2 ) = ( l 2 - a 2 ) 卜( l 2 - - a i ) = ( z 2 - u , ) 。 n = 3 时，因为( 磊一u 1 ) = ( z l 一撕) ，由( 3 2 4 ) 易得 ( z 3 一珏3 ) 一( z 一2 ) = 。( z 1 一钍1 ) + z ( z l t 1 一u o ) - o ， 因此( c ) 当礼= 2 ，3 时成立。 ( i i ) 设( c ) 对所有含少于n 24 ) 个正方形的锯齿链成立。则由归纳假设 我们有( 磊一2 一一2 ) 卜( 磊一2 一一3 ) ，因此由( 3 2 4 ) 知 ( 磊一札。) 一( 磊一u n 一1 ) = x 2 f ( 磊一2 一u n 一2 ) 一( 磊一2 一t t n - - 3 ) j + 茁( 一2 一撕l 一2 ) + x 2 ( k 一2 一u n 一2 一u n 一3 ) - 0 ， 即命题对n 阶锯齿链亦成立，从而由归纳假设知命题成立。 ( d ) n 3 时，由( 3 2 2 ) 和引理3 1 ( c ) 知 ( z 。一 。) 一( 互。一乱。) = 磊一1 + z ( 磊一1 一u n 一1 ) 一 磊一1 + z ( 磊一1 一一2 ) ) = 霉 ( 五一1 一u n 一1 ) 一( z 矗一l t k 2 ) ) 卜o ( n 1 2 ) ， 即( z 巍一t ) 卜( 磊一“。) ( 犯3 ) 。 ( e ) n 2 时，由( 3 2 3 ) 和引理2 2 ( a ) 知 ( 一茁( ”) 一鲈( ”) ) 一( 2 k z ( ”) 一x n - 1 ) = ( 丁k 一1 一z n l y n 一1 ) + z ( j 一i z n 一1 一y n 一1 ) 一 ( 一1 一1 ) + z ( 一1 一x n i 一一1 ) ) = ( 一1 一x n - - l y n 一1 ) 一( 毛一l x n - 1 ) 卜0 ， 从而我们有( 霸一茁m ) 一( n ) ) 卜( 一笫( ”) 一x i i - - i ) 。 引理3 1 证毕。 口 1 3 第三章9 _ q 角链的主要结论 为了用归纳法证明定理3 3 ，我们将证明包含更多内容的如下定理。 定理3 5 对任意整数n 3 t x 任意四角链r 瓦， ( a ) ( l 。一1 一。，1 ) + ( 厶一1 一k 一1 ) 三( 死一1 一一1 ) + ( 死一1 一y n 一1 ) 兰( 磊一1 一 t h 一1 ) + ( j k 一1 一缸n 一2 ) ， ( b ) ( l 。一1 一a n - 1 一b n 一1 ) 兰( 霸一1 一x , n 一1 一y n 一1 ) 至( 磊一1 一撕i 一1 一u n 一2 ) ， ( c ) ( i k z ( 而) 三( j 一t | 。) ，( 7 k 一箩t 砷) 卜( 2 。一氍n ) ， ( d ) l n 三兰磊。 并且只有当四角链矗= k 时，( a ) ( d ) 左边的等式才能成立：只有当四角 链矗= 磊时，( c ) 和( a ) ( b ) ( d ) 右边的等式才能成立：对于( b ) 左边的等式， 四角链死= k 只是一个充分条件。 证明首先我们易发现若四角链矗= 玩，则( a ) ( b ) ( d ) 左右不等式显 然成立：若四角链死= 磊，则( c ) ( 由引理3 1 ( d ) ) 和( a ) ( b ) ( d ) 右边的不等式 成立。因此，当我们证明( a ) ( b ) ( d ) 左边的不等式时，我们不妨假设四角 链矗l 。；当我们证明( c ) 和( a ) ( b ) ( d ) 右边的不等式时，我们不妨假设四 角链矗磊。 下面我们用归纳法来证明定理3 + 5 。 ( i ) 首先考虑当几= 3 时的情况。此时磊= ( 五3 ，z s 。 ( a ) 由假设知我们只要证明 ( 己2 8 2 ) + ( 三2 6 2 ) 卜( 历一钍2 ) + (