（应用数学专业论文）格子系统的独立集的计数.pdf

中文摘要 摘要 四角系统和六角系统在统计物理和化学上有着广泛的应用，本文主要研究 格子系统的( 点) 独立集的计数本文一共分为两章，其中第一章研究四角形格 子图的独立集的计数，在第一章中我们介绍了转移矩阵的概念，并且利用转移 矩阵的方法得到柱面和环面格图的独立集数目的计数公式，同时列出了若干数 值结果利用这个结果，我们用一种新的方法估计了极限r = l i mi ( m ，佗) 赤 比较精确的上界其中f ( m ，住) 表示mxn 阶平面格图g m n 的独立集数 在第二章中我们介绍z i g z a g 型纳米管和a r m c h a i r 型纳米管的转移矩 阵，得到一些数值结果，且推导了它们独立集的计数公式 关键词。转移矩阵；z i g z a g 纳米管；a r m c h a i r 纳米管 英文摘要 a b s t r a c t s q u a r es y s t e ma n dh e x a g o n a ls y s t e m sa r ew i d e l ya p p l i e di ns t a t i s t i c a l p h y s i c sa n dc h e m i s t r y t h i sa r t i c l em 蔚i 坶s t u d y i e st h en u m b e ro f ( v e r t e x ) i n d e p e n d e n ts e t so fl a t t i c es y s t e m t h e r ea r et w oc h a p t e r s ，t h ef i r s tc h a p t e r s t u d i e st h en u m b e ro fi n d e p e n d e n ts e t so fs q u a r el a t t i c es y s t e m i nt h i sc h a p t e r w ei n t r o d u c et h en o t i o no ft r a n s f e rm a t r i x ，a n du s et h et r a n s f e rm a t r i xm e t h o d t og e tt h ef o r m u l a eo ft h en u m b e ro fi n d e p e n d e n ts e t si ns q u a r el a t t i c es y s t e m o nc y l i n d e ra n dt o r u s ，a n dl i s ts o m en u m e r i cr e s u l t sa tt h es a m et i m e u s i n g t h i sr e s u l t ，w eg i v ean e ww a yt oe s t a b l i s ht h eu p p e rb o u n d e rf o rt h ed o u b l e l i m i t ，7 = l i m ( m ，死) 志，w h e r ef ( m ，仃) i st h en u m b e ro fi n d e p e n d e n ts e t s i nt h em 死g r i dg r a p hg m j i 。 t h es e c o n dc h a p t e ri n t r o d u c e st h et r a n s f e rm a t r i xo fz i g z a gn a n o t u b e s a n da r m c h a i rn a n o t u b e s ，s o m en u m e r i cr e s u l t sa r ep r o v i d e d ，a n da l s od e d u c e s t h ef o r m u l a eo fi n d e p e n d e n ts e t so ft h e m k e y w o r d s ：t r a n s f e rm a t r i x ；z i g z a gn a n o t u b e s ；a r m c h a i rn a n o t u b e s 厦门大学学位论文原创性声明 兹呈交的学位论文，是本人在导师指导下独立完成的研 究成果。本人在论文写作中参考的其他个人或集体的研究 成果，均在文中以明确方式标明。本人依法享有和承担由 此论文而产生的责任。 声明人( 签名) ： 年月 日 厦门大学学位论文著作权使用声明 本人完全了解厦门大学有关保留、使用学位论文的规 定厦门大学有权保留并向国家主管部门或者指定机构送 交论文的纸质版和电子版，有权将学位论文用于非赢利目 的的少量复制并允许论文进入学校图书馆被查阅，有权将 学位论文的内容编入有关数据库进行检索，有权将学位论 文的标题和摘要汇编出版。保密的学位论文在解密后适用 本规定。 本学位论文属于 1 、保密() ，在年解密后适用本授权书。 2 、不保密( ) ( 请在以上相应括号内打”，) l 储繇铆脚啡 导师签名：7 绯旋 日期： 年月 日 年月日 格子系统的独立集的计数 格子系统的独立集的计数幸 己i 古 ji口 1 我们将所有由数个相同的正方形以边相连接所组成的几何形状都称为 p o l y o m i n o e s p o l y o m i n o e s 是组合数学中。细胞生长。( c e u - g r o w t h ) 问题的 一个研究对象如果细胞一个正方形，则称生成的动物是p o l y o m i n o e s ；例如 俄罗斯方块游戏中由四个相同的正方形以边相连接所组成的几何形状他们称 为四阶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 p o l y o m i n o e s 拥有很悠久的历史，起源可以追溯到上个世纪初，但它们是 现在才被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 lg a m e s 专栏中普及p o l y o m i n o e s 不仅可以做出好玩的游戏，它更与 数学上的几何学，组合学与图论等有着密切的联系后来人们发现它也有很强 的统计物理背景，可以做为气体分子的模型 p o l y o m i n o e s 是一个有限参连通平面图，它满足 1 每个内部面都是一个单位正方形； 2 两个正方形相邻，则他们的公共部分必须是一条完整的边 这里要说明两点t 第一，一般提到的p o l y o m i n o e s 都包括带洞的情形，即允许其内部被挖 空，并称这样的p o l y o m i n o e s 为多连通的( m u l t i p l y c o n n e c t e d ) ；反之称那些 不带洞的p o l y o m i n o e s 为单连通的( s i m p l y c d 礼舭砖甜) 【3 】，本文只考虑单连 通的情形 第二，在组合问题中一般所指的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 ，它允 许旋转，翻转和平移，即p o l y o m i n o e s 被看成是不同的，如果它们具有不同的形 国家自然科学基金资助项目( 项目批准号。1 0 6 7 1 1 6 2 ) 格子系统的独立集的计数 2 状，丽与它们在平面上的方位和位置无关另外还有o n e - - s i d ep o l y o m i n o e s ( 只 允许旋转和平勘和f i x e dp o l y o m i n o e s ( 只允许平移，与方位有关) 【2 】 上述两点其实是对p o l y o m i n o e s 进行计数的两个标准从数学角度来看， 有关p o l y o m i n o e s 的研究主要集中在以下几个方面t 第一，覆盖问题( 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 s 拼图谜题的研究，即 利用所给一些低阶p o l y o m i n o e s 能否不重不漏地恰好盖住指定区域( 通常为 一些特殊形状，如m 扎的矩形) ? 如果能的话，共有几种覆盖方法? 例如用 1 2 个p e n t o m i n p e s ( 即5 一o r n i n e s ) 能否盖住个2 3 0 ，3 2 0 。4 1 5 ， 5 1 2 或6 1 0 的矩形? 关于这方面的问题还有很多，具体可见f 5 ，6 】， 其中有些问题已得到完美解决，但有些问题仍未得到解决 第二，非同构计数问题( e n u m e r a t i o n ) 即给定了1 1 个细胞，共可以产生多少个不同的a n i m a l s ? 按照上述提到的两个标准分别给予回答 对于第一种标准， 2 6 阶以内单连通p o l y o m i n o e s 计数的结果可参见序 列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 l i v e i r a 等人在算法的设 计改进及其在计算机的实现上做出重要贡献( 8 ，9 】，但是随着阶数1 1 的增 大，单连通和多连通p o l y o m i n o e s 的具体数值也越来越难确定，于是人们希 望去探究它的上下界【3 】 d a v i d a 。k l a r n e r 在1 9 6 6 年证明了存在一个常数k ( i i 0k l a r n e r 常数) ， 使得当1 1 趋近于无穷时，尸( n ) 的增长近似于k n ，即l i mp ( 礼) 寺= 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 ) ；而关于k 上界的最好结果是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 的精确值仍然无能为力 公开猜想。猜想l i m 苦蒜上= k 是否成立? 对于第二种标准，我们用f r e e ( n ) 来表示包含1 1 个细胞的f r e ea n i m a l s 的数目，用f i x e d ( n ) 来表示包含1 1 个细胞的f i x e da n i m a l s 的数目【3 】 从1 9 6 2 年r e a d 得到许多关于p o l y o m i n o e s 计数的理论结果至今，人们 格子系统的独立集的计数 3 花费了大量精力去寻找一个f i x e dp o l y o m i n o e s 的计数公式，都以失败告终， 只是得到f r e e ( n ) 和f i x e d ( n ) p o l y o m i n o e s 的一些界【3 lt e d e n ，k l a r n e r ，r i v e s i l i m ，t z e d ( 礼) 吉= 0 存在，且3 8 7 0 n 4 6 5 r e d e l m e i e r 9 算出了2 4 阶内f r e e ，f i x e d ，s y m m e t r i cp o l y o m i n o e s 数 目 第三，匹配计数与排序等相关问题 在量子化学中图的完美匹配称为k e k u l d 结构，而在统计物理学中称为 d i m e r 构形目前已经证明了四角系统的完美匹配与统计物理学中的d i m e r 问题( 即用2 m n 个d o m i n e s 不重不漏地恰好覆盖一个2 m 2 n 矩形共有多 少种不同的覆盖方法) 有直接的联系四角系统完美匹配的存在性问题已经得 到解决【1 6 】另外有关四角系统的匹配计数也已经有了许多重要结果 而图关于匹配数的排序，尤其是关于匹配数的极图，在早期文章已经有 过研究，相应的研究结果在化学方面的应用很大对于图的许多其它不变量， 如全7 r 一电子能量和独立集数，类似的排序或极值问题也有所研究 图g 中，设y 是g 的点集，y 的子集j 如果满足i 中没有两个点 在g 中相邻，那么称i 为v 的独立集我们把图g 的独立集的数目称之为 m e r r i f i e l d - s i m m o m s 指标图关于独立集的计数相应的研究结果不仅在化 学方面的应用很大，而且在物理中同样有重要应用，最近几年里，物理学者和 组合论学者对计算的数目这个问题产生了很大兴趣。l e g a lm a t r i c e s 是0 - 1 矩阵，两个元素如果称为相邻的如果他们处于( t ，歹) 位置和( i + 1 ，j ) ，或者处 于( i ，歹) 和( i ，歹+ 1 ) 位置在。l e g a lm a t r i c e s 中不允许有两个1 相邻 在统计物理中，有如下著名的 1 ，h a r d 四角问题：在一个s q u a r el a t t i c e 中独立集的数目是多少? 2 ，h a r d 六角问题：在一个h o n e y c o m bl a t t i c e 中的独立集的数目是多少? 我们定义g ( m ，n ) 为在n 边的s q u a r el a t t i c e 中含有m 个点的独立集 的数目。 格子系统的独立集的计数4 下面介绍c a n o n i c a l 分拆函数定义”g r a n dc a n o n i c a l 分拆函数为 e n ( z ) = g ( m ，g ) z m m 其中z 是一个任意的实( 复) 变量，如果z 是正实数，我们得到具有物理意义 的极限 ，c ( 名) = 。l ，i m 【一( z ) 】青 存在并且和不依赖于s q u a r el a t t i c e 的形状因此s q u a r el a t t i c e 可以是无限 延伸的 组合学家对三( 1 ) 和k ( 1 ) 非常感兴趣，当z = l 时却被统计物理学家所关 心在【3 3 】和【3 4 】中估计出1 5 0 3 0 仡( 1 ) 1 5 0 3 0 4 8 0 8 2 ，它的上下界分别是 1 5 0 3 2 6 3 和1 5 1 7 5 1 3 1 3 1 】组合学家e n g e l 得到估计值1 5 0 3 0 4 8 0 8 1 1 8 】，c a l k i n 和w i l l 得到1 5 0 3 0 4 8 0 8 2 4 7 5 3 3 2 3 【2 1 】，得到上下界分别为1 5 0 3 0 4 7 7 8 2 和 1 5 0 3 5 1 4 8 这个估计被m c k a y 推广到1 5 0 3 0 4 8 0 8 2 4 7 5 3 3 2 2 6 【3 2 】，r j b a x t e r 利用c o r n e r 转移矩阵的方法计算出得到的估计值是 k ( 1 ) = 1 5 0 3 0 4 8 0 8 2 4 7 5 3 3 2 2 6 4 3 2 2 0 6 6 3 2 9 4 7 5 5 5 3 6 8 9 3 8 5 7 8 1 0 并且相信所给出的小数点后4 3 位都是正确的 而对于t r i a n g u l a rl a t t i c e 我们称之为h a r d 六角，m e t c a l f 和y a n g 在 1 9 7 8 年猜想l o g ，i ：( 1 ) = 这个猜想被b a x t e r 和t s a n g 推广到更加精确的 数值 3 0 】他们虽然没证明m e t c a l f 和y a n g 的猜想，但是用y a n g b a x t e r 方法把问题解的更精确 对于s q u a r el a t t i c e 和h o n e y c o m bl a t t i c e ，问题还没有被解决得更精确， 运用y a n g b a x t e r 方法去计算仡( 1 ) 的数值时，目前只能分别计算得到小数 点后4 2 和3 9 位，但对于t r i a n g u l a rl a t t i c e 时的k ( 1 ) 的值目前最好的结果 是精确到小数点后5 5 位 函数尤( 名) 主要通过级数展开和数值计算进行深入研究，在 3 5 ，3 6 】中 g s g a u n t 和m e f i s h e r 得到以下幂级数的展开，这里我们只给到1 3 次 格子系统的独立集的计数 5 t r i a n g u l a rl仡= 1 + 名一3 + 1 6 2 3 1 0 6 2 4 + 7 8 9 2 5 6 3 1 8 z a + 5 3 1 9 8 2 7 4 6 4 6 7 3 z s + 4 1 7 4 0 8 8 2 9 3 8 3 3 2 5 0 0 z l o + 3 5 8 3 7 1 3 4 5 z u3 4 0 0 2 3 8 4 1 9 2 1 2 + 3 2 6 6 4 0 6 2 7 4 0 z l a + o ( z 1 4 ) s q u a r el 代= l + z - 2 2 2 + 8 2 3 4 0 2 4 + 2 2 5 z s 一1 3 6 2 2 6 + 8 6 7 0 2 7 - 5 7 2 5 3 2 8 + 3 8 8 8 0 2 2 9 2 6 9 9 2 0 2 z m + 1 9 0 7 6 0 0 6 2 1 1 1 3 6 8 1 5 2 8 2 2 1 2 + 9 9 3 4 6 5 2 4 8 z l a - o ( z 1 4 1 h o n e y c o m b ：舻= 1 + 2 z 一2 2 2 + 6 z a 一2 3 2 4 + 1 0 0 2 5 4 6 9 2 6 + 2 3 1 4 z t 一 11 8 4 1 z s + 6 2 2 8 6 2 9 3 3 4 8 0 4 2 1 0 + 1 8 3 1 3 5 8 z n 一1 0 1 6 2 6 7 9 2 1 2 + 5 7 0 8 0 8 4 0 2 1 3 + o ( z 1 4 ) 碳纳米管是1 9 9 1 年由日本电子公司饭岛博士在高分子透射镜下观察 结构是发现的碳纳米管在场发射器件，电子晶体管，储氢，太阳能利用，高 效催化剂以纳米生物系统等方面应用以及纳米材料科学与技术本身均会带来 革命性的变化 碳纳米管按照手性分类可分为：非手性型和手性型其中非手性型管是 指单壁碳纳米管的镜像同它本身一致本文只关心非手性型的单壁纳米管即 锯齿型( z i g z a g ) 和扶手椅型( a r m c h a i r ) 他们可以表示如下： f i g u r e1 ：z i g z a g 型纳米管 格子系统的独立集的计数 f i g u r e2 ：a r m c h a i r 型纳米管 第一章格图上的独立集的计数 1 1转移矩阵 6 在这一节里，我们首先介绍转移矩阵，为后面的计算作准备 设g m 。n 是m 佗的格子图，即为g m ，n 中有( m + 1 ) m + 1 ) 个点( t ，j ) 其中( 0 i m ，0 j 竹) 它的边是由所有满足l i 一引+ l j j = 1 的点 对( i ，j ) ，( t 7 ，j 7 ) 组成由积图的定义知道格子图g m ，n 其实是两条m 长的路 和1 1 长的路的积图，因此g m 。n 也可以记为g m ，n = l mxl n ，由此定义我们 把日m = g n xk 称为柱面格图，把2 1 m m = c k g 称为环面格图 f i g u r e3 g 3 4 = 1 3 1 4 令，( 仇，n ) 为g m ，n 中独立集的数目显然g m ，竹包含规模大于警的独 格子系统的独立集的计数 7 立集该集有大于等于2 等个子集，因此叩= y l m ( m ，住) 去讵在 m n + 【2 】，k f e w e b e r 证明了极限h m ( m ，佗) 志和极限l i m ，( m ，几) 者的存 在性并估计了它的值在 1 1 中，k e n g e l 证明了关于这些数目的一些不等 式，推断出1 5 0 3 0 4 7 7 8 2 ? 7 = l i mf ( m ，死) 焘1 5 1 3 1 6 0 6 7 并猜 想? 7 = 1 5 0 3 0 4 0 8 在【3 】，w i l f 证明双重极限叩= l i m ，( m ，礼) 志存在， 且1 5 0 3 0 4 7 7 8 2 ，7 1 5 0 3 5 1 4 8 ，而目前最好的结果是r j b a x t e r 在 1 9 9 9 年利用c o r n e r 转移矩阵估计出 7 = 1 5 0 3 0 4 8 0 8 2 4 7 5 3 3 2 2 6 4 3 2 2 0 6 6 3 2 9 4 7 5 5 5 3 6 8 9 3 8 5 7 8 1 0 首先我们介绍转移矩阵的概念，设s 是g m n 中的独立集，考虑s 在图 g 中某一固定列中的部分它可看成一个m + l 维的啦! 向量其中1 表示 点在s 中，0 表示点不在s 中这样的m + 1 维的o - 1 向量存在s 中那么 就必须满足没有两个1 连续出现 例如：g 3 4 中的独立集s s 在列中的部分都是下面的4 维向量之一 ( o ，0 ，0 ，o ) ，( 1 ，o ，o ，o ) ，( 0 ，1 ，o ，o ) ，( 0 ，0 ，l ，o ) ，( 0 ，0 ，0 ，1 ) ，( 1 ，0 ，l ，0 ，) ，( 1 ，0 ，0 ，1 ) ，( 0 ， l ，0 ，1 ) 易知每个垂维向量都具有这个性质：没有两个相继的1 出现对于固 定的i n ，1 1 ，用c k 记为所有满足没有相继1 出现的m + l 维皿1 向量z ，易 知c m 中元素的个数为昂冲2 菲波那契数在g 名行中的独立集中相邻两列 魄，屹满足没有1 出现在相同的位置即其内积魄地= 0 定义转移矩阵t = 7 1 仇如下。设t 是个j m + 2 b 。+ 2 的m 1 对称矩 阵，它的行列都由c f m 中的元素按照相同的顺序排列t 中( n ，忱) 位置是l 如果魄和圪是正交，否则为o 。t 是依赖于1 1 1 ，而与n 无关 对m = 3 来说，排列岛中的元素按照以上顺序排列我们得到转移矩阵 格子系统的独立集的计数 t 32 l1lll 1l1o 0 01ll1 10l01 l10 1 o 1o100 llo o o 01010 1 2平面格图上独立集的计数 8 设f ( m ，n ，钍) 定义为最右边的列向量为u 的g m 。n 中的独立集的数目 显然f c m ，r t , 移) = e f ( m ，n ，u ) l ，付川o ；t i ) 由矩阵向量表示 厶+ 1 = t f 其中f o = 1 ，1 为全1 向量因此对所有他0 都有厶= p 1 g m ，住中的独立集数是向量厶的所有元素之和即f ( m ，n ) = 1 t n l 即 f ( m ，他) 是矩阵p 中所有元素之和 由于，( m ，佗) 是p 中所有元素之和我们可知若m 固定，f ( m ，n ) 的 数可以看成是矩阵( ，一z t ) - 1 元素和中幂级数展开中护的系数项 对m - - - 2 ，在独立集中可能的列向量是 ( 0 ，0 ，o ) ，( 0 ，0 ，1 ) ，( 0 ，1 ，o ) ，( 1 ，0 ，o ) ，( 1 ，0 ，1 ) 我们排列行列由以上顺序，得转移矩阵 t 2 = 1 1 o 1 o 1 0 0 1 o l l 1 0 0 1 1 _ 1 1 1 上 1 1 _ 1 1 1 、liilliiii-、 l 0 l 0 0 l 1 1 0 0 l 1 o l 1 1 o l 1 o 格子系统的独立集的计数 而对于m - - - - 4 时。得转移矩阵 t 4 = 11l1 111ll l1ll 101111o o 0l11o l101llll1 o o 1l l1l0l1 0lll1oo 1l11011o1 0ll1 l111l0l1ol0 0 0 1olo110o ol10 0 l 0 1l01o0o0110 1olll0o0 o 1o0 0 ll01o11o 1 o ol1 1 1 01l01l0o0 0 0 l1l0 1 001o10 0 0 1 0l0l00o o 1 000 根据求独立集的公式得到下表 表l当m ，n 取较小值时g n 的独立集数 m 123456 03581 32 13 4 l71 74 19 92 3 95 7 7 21 76 32 2 78 2 72 9 9 91 0 8 9 7 34 12 2 71 2 3 46 7 4 33 6 7 8 72 0 0 7 9 8 49 98 2 76 7 4 35 5 4 4 74 5 4 3 8 53 7 2 9 0 9 1 52 3 92 9 9 93 6 7 8 74 5 4 3 8 5 一 65 7 71 0 9 8 72 0 0 7 9 83 7 2 9 0 9 1 - 9 格子系统的独立集的计数 1 3柱面格图上独立集的计数 1 0 在【2 1 1 中w i t f 证明了极限，7 = l i mf ( m ，死) 赤的存在性，且得到 一一 m g - - - o o r = l i m ，( m ，n ) 志：l i ma 嘉 h i , n + m _ 其中a m 为转移矩阵2 k 的最大特征值并且利用最大性原则给出了，7 比较 精确的上下界，本章通过利用柱面格图独立集的计数公式给出7 7 上界的另一 种估计方法同时我们还得到环面格图上独立集的计数 卜卜，。) 。i j ) 。? ，j j 。，了 r j 1 、。j 。 ： ： 1 1 一 f i g u r e4 ：c 8 1 4 下面计算c , nxk 的独立集数目设s 是c m k 中的独立集，考虑s 在 图王n 中某一固定列中的部分它可看成一个仍维m 1 向量其中1 表 示点在s 中，0 表示点不在s 中这样的m 维的m 1 圈向量存在s 中就必 须满足没有两个1 在该圈中连续出现记为所有这样的m 维的m 1 圈向 量的集合，显然k 中元素的个数为j m + b 。一2 菲波那契数 c ，lx 中的任意一独立集都是由k 中某一向量开始依次在右边连上个 与其正交的向量，直到n + 1 个向量确定为止我们定义+ j k 一2x 昂，+ j k 一2 阶转移矩阵，其中矩阵的行是由中的向量按相同的顺序排列例如：当p = 2 ， 在一独立集中所有可能的列向量是 ( 0 , 0 ，0 ，o ) ，( 1 ，0 ，0 ，o ) ，( o ，l ，0 ，o ) ，( 0 ，0 ，1 ，o ) ，( 0 ，0 ，0 ，1 ) ，( 1 ，0 ，1 ，o ) ，( o ，1 ，0 ，1 ) 格子系统的独立集的计数 如果我们以此顺序排列行列，得到转移矩阵b = 五m b 4 = l1l11 1l 10l o11l0 l01o1 1l0lo 10 1 01 o10 l o 设g ( m ，n ，u ) 定义为最右边的列向量为u 的c ，lxk 中的独立集的数目 显然g ( m ，佗，口) = u g ( m ，7 1 , 一1 ，u ) 玩一o ；v ) 由矩阵向量表示 鲰= b g 一1 其中9 0 = 1 ，1 为全1 向量因此对所有礼0 都有如= b 竹1 c ，i j n 中的独立集数就是向量鲰的所有元素之和即 夕( m ，n ) = 1 b n l 即夕( m ，佗) 是矩阵b n 中所有元素之和 表2当m ，n 取较小值时k 的独立集数 m n 1234 56 271 74 l9 92 3 95 7 7 31 34 31 4 24 6 91 5 4 95 1 1 6 43 51 8 19 3 34 8 1 12 4 8 0 71 2 7 9 1 3 58 16 2 14 7 4 13 6 2 1 12 7 6 5 6 12 1 1 2 2 4 1 61 9 92 3 0 92 6 6 6 03 0 7 9 8 33 4 0 4 3 7 33 8 9 9 1 4 11 下面我们来研究，7 的上界，这个上界将和m ，n 无关，而依赖与一个新的 正整数参数p ，对于个正整数p 都可以得到一个准确的上界对于任意正 整数p ，转移矩阵t 的最大特征值a m 显然满足 k t r o c e ( 产) 专 l o 1 1 l 0 l 1 工 1 1 l 1 工1 工 l 格子系统的独立集的计数 1 2 因为t r a c e ( t a p ) = l 。声。疋。声。瓦。，一。栅由转移矩阵的定义我们 知道x o ，：t 1 ，z 2 p 一1 表示都表示c m 中的元素，所以t r a c e ( t 2 p ) 的 数目就等于第一列和最后一列取相同独立集时所有g 仇2 p 的独立集的数目 由此显然我们得以下性质。 性质1t r a c e ( t a p ) 的迹等于试管图c a p k 的独立集的数目 同理可得 性质2 t r a c e ( b 2 p ) 的迹等于轮胎图c a p 的独立集的数目 表3 当1 1 1 ，n 取较小值时c m c n 的独立集数 m n l23456 2371 33 58 1 1 9 9 341 33 41 2 1 3 7 11 3 0 0 473 51 2 17 4 3 3 5 6 11 8 9 9 5 51 18 13 7 13 5 6 1 2 5 5 3 11 9 9 8 2 1 61 81 9 91 3 0 01 8 9 9 51 9 9 8 2 12 2 8 6 0 1 2 因为b 2 p 含非负元素，故它的主特征向量不与全1 向量正交，因此对任 意p ，有l i m9 ( 2 p ，m ) 去存在，且等于转移矩阵岛p 中的最大特征根r 2 p 。 l v r # , - - - - * 3 0 。 因此对任意给定的一个正整数p ，有 + a m t r a c e ( t a p ) + = ( 1 b m l ) 专 两边同时开h 1 次根并取m _ ，得到 ，7 = l i m ，( 编，冠) ；轰= h ma 磊l i m ( 1 b m l ) 南= l i mg ( 2 p ，m ) 南 m ，n - - _ o o l r n , - - - * o ol r n - - , - - * 0 0m - - - - * 0 0 上 = r 荔 格子系统的独立集的计数 当p = 3 时。 b 6 = 11l1ll11l1lll 1l1ll 10l1llloo 0ll111l0l 110111l111o 0 0 o1110 1l101ll0l l1l 100lol l1llol11o10l1 ll0l0 l 1l1 1011l01010110l 111l110l1l1l010 01o lol01l1o00llloo1o1 101lo1lo0 0 0111100 0 lol11o1000101011ol 1l01olll0l0 o 0l1010 l101l011l0 o00 0l1o0 1l011l01ll0 0 01o0l0 1110l0lo10lo10 o101 11l0110011010 0 0 0 o 0 111l0101010l0100l0 l0l0lo1o0010l0 01o1 l10lo101ol0 o 010ol0 1 3 其中r 6 = 1 1 5 5 1 7 0 9 5 6 6 0 4 8 1 4 5 0 9 所以表示所有满足该性质的2 m 维0 - l 圈向量的集合集合中元素的个数为f 2 2 + 菲波那契数 叩= l i mf ( m ，n ) 去11 5 5 1 7 0 9 5 6 6 0 4 8 1 4 5 0 9 m n = 1 5 0 3 5 1 4 8 0 9 4 7 5 9 0 3 0 2 3 ， 格子系统的独立集的计数 1 4 第二章z i g z a g 型纳米管和a r m c h a i r 型纳米管独立 集的计数 个六角系统把是一个有限2 一连通的平面图，且每个内部面都是一个单 位正六边形六角系统在理论化学中有重要作用，因为它们是苯的衍生物的自 然的图的表示六角系统的m e r r i f i e l d s i m m o m s 指标在一些相关化学拓 扑问题上被广泛的研究下面我们对z i g z a g 型纳米管z r m n 和a r m c h a i r 型纳 米管k n 的m e r r i f i e l d s i m m o m s 指标进行研究( 其中m 表示行数，n 表示每行中单位正六边形的个数) 设f ( m ，几) 和g ( m ，仃) 分别表示二个图的 独立集的数目 2 1z i g z a g 型纳米管独立集的计数 由前面知识我们知道，设s 是n 上的一个独立集，考虑s 中在图中 固定的一列( 圈) 可以把它看成是2 m 维0 - 1 圈向量其中1 表示该点在s 中，否则为o 这样的2 m 维m 1 圈向量存在必须满足以下性质。在圈中没有 相继的l 出现p m 表示所有满足该性质的2 m 维m l 圈向量的集合集合中 元素的个数为一2 + 兄m 菲波那契数 对胁中的两个向量i t i ，u 2 ，若它们表示z m ，n 中相继的两列，那么它们 必须满足在偶数位置或者奇数位置没有相同的l 出现，即t l 。t 2 e = 0 或者 u l o 牡2 d 。0 对z i g z a gn a n o t u b e sz r 仇竹我们也可以类似定义转移矩阵d m l 和d 仇2 分别记为d l 和现d l 是( 如m 一2 + 局m ) ( f 2 m 一2 + f 2 m ) 的0 - 1 矩阵，其 中行列是p m 中的向量按照相同的顺序排列d t 中在( u l ，让2 ) 位置上元素是 1 如果t l 口u 2 0 = 0 ，否则为0 同样我们可以定义忱；玩中在( u l ，u 2 ) 位置上元素是1 如果1 。蚍= 格子系统的独立集的计数 0 ，否则为0 当m 为2 时，转移矩阵d 2 1 ，如如下t d 2 l2 d 2 2 = 111 01l 111 l1o 1l1 010 ll1 111 1ol 11 1 l01 11l l01 l1l 1llll l111l 011lo 1111l 1l0lo 1 1l1l 01ol0 1 5 令f ( m ，佗，p ) 表示图，n 中最右边列向量为t 的独立集的数目因此 我们得到 ，c m ，佗+ l ，移卜 - u e m , f ( m , n , u ) d 1 ；i f f 曲n i s 。e v 以e n 用矩阵向量表示得到。 厶+ 1 = d l f n i i f fn ni i 8 s 。e v d e d n 1 上，工 l 1 工1 1 1 工 1 1上1工，上1工1上1工 1 格子系统的独立集的计数 其中o = 1 , 1 为全1 向量因此 扣d 2 d , d 2 d i f 0 1 如i i f f n ni 8 i s 。e v d d e n n 中独立集的数目就是向量厶中元素之和因此 厶，n = 1 ( d 2 d 1 ) - 2 i 叭i f i fn ni i s 8 。e v d d e n 表4当m ，n 取较小值时2 ，m n 的独立集数 m n 1234567 182 15 51 4 43 7 79 8 72 5 8 4 2 4 2 2 4 51 4 2 18 2 3 24 7 6 7 72 7 6 1 1 51 5 9 9 0 6 6 7 34 9 4 8 99 2 9 6 5 3 4 一 一一 2 2a r m c h a i r 型纳米管独立集的计数 1 6 设s 是a m 。n 的个独立集( 其中m 为偶数) ，考虑s 在图中的一固定 列，它可以看成是m 维的0 - 1 向量，其中1 表示该点在s 中，否则为0 这 样的n 维向量存在必须满足忱七一1 u 2 k = 0 ，表示口的第i 个位置表 示所有满足该性质的m 维向量的集合该集合中元素的个数为3 等中 的向量口7 ，矿如果要在s 中相继出现则必须满足 复口幺+ l = 0 我们定义转移矩阵l ，2 ，分别记为蜀，易蜀，毋都是3 量3 詈 的阻1 矩阵，它的行列都是把七m 中的元素按相同的顺序排列毋中( 口7 ，御) 位置元素是1 如果一l = 0 且t ，i 屹n = 0 ，否则为0 易中( 钉，v ) 位置元素是l 如果吒+ l = 0 且秽钐f = 0 ，否则为0 格子系统的独立集的计数 当m - - - - 4 时 e 4 1 = e 4 2 = 111l1111l l111l10 o 0 10llo 111 0 llol10101 1lol0 0 0 0 0 10ol0 010 0 1l1oo0ll1 101o 001l0 ll1o0oo00 11llll1l1 110110l0 1 ll10 0 0l1l 11111 10 0 0 1l0110 0 0 0 ll10 0 0 0 0 0 l0l111l10 10l000ll0 l1010 0l0 0 令g ( m ，佗) 表示图，n 中独立集的数目因此我们得到 9 ( m ，n + 1 ) = g ( m ，n ) e 2 e 1 1 7 用矩阵向量表示鲰+ 1 = 鲰e 2 e 1 ，由于g t = e 1 e 2 e 1 1 ，1 为全l 向量 因此g n = e 1 e 2 e 1 易e l l ，厶，n 中独立集的数目就是向量鳜中元 素之和所以 夕m n = 1 n l ( n 2 n 1 ) n 1 格子系统的独立集的计数 表4当m ，n 取较小值时厶，n 的独立集数 m n 1234567 24 12 3 9 1 3 9 38 11 94 7 3 2 12 7 5 8 0 71 6 0 7 5 2 1 4 1 6 0 75 4 1 7 01 8 2 4 3 8 66 1 4 3 9 4 8 4 1 8 一一 一一堑王墨丝笪塾童塞丝盐墼 1 9 - - - _ _ _ - _ _ i _ 。_ - _ _ _ _ _ - _ 。- - - - 。一 参考文献 1 孙文先编译，p o l y o m i n o e s ：多方块的数学问题，拼图谜题与游戏 m 】，台 北市。九章出版，民9 1 1 2 0 0 2 【2 】e w w e i s s t e i n ，p o l y o m i n o z ，f r o mm a t h w o r l d - aw o l f r a mw e br e - s o u r c e h t t p ：m a t h w o r l d w o l f r a m c o m p o l y o m i n o h t m l 【3 】e v k o n s t a n t i n o v a , as u r v e yo ft h ec e l l - g r o w t hp r o b l e ma n d s o m ei t s v a r i a n t i o n s z h t t p ：c o m m a c p o s t e c h a c h p a p e r s 2 0 0 i 0 1 0 6 p d f 【4 1c l a n i u s ，p o l y o m i n o e si n t r o d u c t i o n z h t t p ：m a t h r i c e e d u l a n i u s 博 s o n p o l y s p o l y l h t i i d 【5 】s w g o l o m b ，p o l y o m i n o e s ：p u z z l e s ，p a t t e r n s ，p r o b l e m s ，a n dp r o b l e m s a n dp a c k i n g s ，2 n d e d n m 】p r i n c e t o n ，n j ：p r i n c e t o nu n i v e r s i t yp r e s s ， 1 9 9 4 【6 1g e 。m a r t i n ，p o l y o m i n o e s ：ag u