（应用数学专业论文）关于格路的计数以及均匀分布的一些研究.pdf

摘要 摘要 对不同类型格路的研究在组合数学中一直占有重要地位。方面，格路经 常作为重要的模型来描述其它组合结构如树、有禁排列、对称函数、正交多项 式、连分式等。另一方面，它们常出现在数学的其它领域如概率论、统计学 等。在本文中，我们重点研究了几类格路的计数以及均匀分布问题，其中借助 了徘徊杨表、缺陷引理等重要工具。 振荡杨表与徘徊杨表最初出现在代数学领域，但它们与组合数学中的重要 研究对象匹配与划分有着密切的联系。振荡杨表的概念是由b e r e l e 于1 9 8 6 年 提出的。之后，s t a n l e y 借助r s k 算法建立了振荡杨表与匹配之间的一一 对应，s u n d a r a m 在1 9 9 0 年将这一对应做了扩展。徘徊杨表的概念是2 0 0 5 年 由h a l v e r s o n 和r a m 给出的。2 0 0 7 年，陈永川等人构造了徘徊杨表与划分之间的 一一对应，并且以此为工具解决了经典计数理论中的一个重要问题，即他们用 组合方法证明了在所有划分或匹配中，交叉数与嵌套数是对称联合分布的。目 前，振荡杨表与徘徊杨表已经成为研究匹配、划分等组合结构的性质以及计数 等问题的强有力工具。 著名的c h u n g - f e l l e r 定理是计数组合学中的一个经典结果，其内容可叙述 为：2 n 长的自i 由d y c k 路中缺陷数的分布是均匀的。此结果是m a c m a h o n l 9 0 9 年 首次发现的。而该定理的命名源于c h u n g 与f e l l e r l 9 4 9 年的工作，他们重新 发现并用分析的方法证明了该定理。之后，这个定理被广泛研究。迄 今，自d y c k 路上的c h u n g - f e l l e r 定理已经有了多种不同的证明方法。例 如：r a n e y ，n a r a y a n a ，d e r s h o w i t z 与z a k s 等人分别利用循环引理或循环路 给出了证明；c a l l a n ，j e w e t t 与r o s s 等人通过构造双射加以证明。此外，很 多学者还着力于研究该定理的推广形式。例如：2 0 0 1 年，w o a n 发现了自 i 扫d y c k 路上另一个均匀分布的参数：绝对最小长度；同年，s h a p i r o 研究了特 定的m o t z k i n 路中绝对最小长度的均匀分布问题；游森棚等人2 0 0 5 年通过对不 同格路生成函数泰勒展式的研究，既得到了该定理的一种加细形式又发现了 赋权自由s c h r b d e r 路上的c h u n g - f e l l e r 性质；2 0 0 7 年，陈永川等人定义了双根 平面树中的蝴蝶分解，借此给出j c h u n g - f e l l e r 定理以及赋权自由s c h r s d e r 路 上c h u n g - f e l l e r 性质的另一种全新的证明方法；最近，马君与叶永南又研究了 三类特殊的格路上缺陷数与绝对最小长度这两个参数的均匀分布问题。 摘要 在本篇论文中，我们主要研究了不交自由d y c k 路、自由m - s c h r s d e r 路、不 完整自由k - d y c k 路等不同格路的计数以及它们关于不同参数的均匀分布问题。 在第二章中，我们得到了尼不交自由d y c k 路的计数公式。该公式是通过构 造b 不交自i 扫d y c k 路与有限制的平面分拆之间的一一对应，借助s t a n l e y 给出的 限制行数列数与最大部分值的平面分拆的计数公式得到的。当限定k 取2 时， 我们发现2 不交自 扫d y c k 路与c a l l a n 给出的固定块数的不交划分的计数是相 同的。借助徘徊杨表，我们建立了2 佗长的2 不交自 扫d y c k 路与有佗+ 1 个块 的f 2 佗+ 1 1 上的不交划分这两个集合之间的一个双射。此外，根据l a b e u e 合并算 法，我们找到了与2 不交自i 扫d y c k 路对应的单条d y e k 路的刻画方式。 在第三章中，一方面，我们研究了自由m - s c h r s d e r 路关于缺陷数与绝对 最小长度这两个参数的均匀分布问题。我们的结果统一并且扩展了之前关于 自由d y e k 路、自由k - d y c k 路以及自由s c h r s d e r 路等不同格路的c h u n g - f e l l e r 性 质，有着更为广泛的意义。特别地，我们得到了一个非常简洁直观的结果， 称之为缺陷引理。该引理包含了比循环引理更多的信息，因此可以看作是 循环引理的推广。在本文中，缺陷引理是发现并证明赋权自由m s c h r s d e r 路 上关于缺陷数c h u n g - f e l l e r 性质的有力工具。并且我们找到了限制斜步个数 的m s c h r s d e r 路计数的一个更简单的组合证明。另一方面，我们发现了一种新 的方法来证明自由d y e k 路中绝对最小长度的均匀分布问题。 在第四章中，我们得到了固定类型的不完整k - d y c k 路的计数公式，并且 给出了原始的c h u n g - f e l l e r 定理的另一种加细形式，即在给定类型的自由红 d y c k 路中缺陷数的分布是均匀的。此外，我们建立了泊车函数与集合m 上的有 根森林之间的一个双射，并且借助固定类型的k - d y c k 路的计数公式得到了不交 划分、泊车函数以及有根森林等组合结构中的一系列计数结果。 在第五章中，我们从另外一个角度重新考虑经典的c h u n g f e l l e r 定理，即 将自 扫d y c k 路看作从原点出发最终回到原点且每步取( 1 ，0 ) 或( 一l ，0 ) 的格路， 由此，我们发现并证明了四分之一平面上两种特定的格路上的有趣的c h u n g - f e l l e r 性质。 关键词： 自由d y c k 路，徘徊杨表，不交划分，自m m - s c h r s d e r 路，缺陷弓 理，缺陷数，绝对最小长度，不完整- d y c k 路 i i a b s t r a c t a b s t r a c t l a t t i c ep a t h so fv a r i o u st y p e so c c u p ya ni m p o r t a n tp o s i t i o ni nc o m b i n a t o r i c s o no n eh a n d ，t h e ys e r v ea sa ni m p o r t a n tm o d e lt od e s c r i b em a n yc o m b i n a t o r i a l s t r u c t u r e ss u c ha st r e e s ，p a t t e r na v o i d i n gp e r m u t a t i o n s ，s y m m e t r i cf u n c t i o n s ， o r t h o g o n a lp o l y n o m i a l s ，c o n t i n u e df r a c t i o n s ，e t c o nt h eo t h e rh a n d ，t h e yo f t e n a p p e a ri no t h e rf i e l d so fm a t h e m a t i c si n c l u d i n gp r o b a b i l i t yt h e o r y , s t a t i s t i c s ， e t c i nt h i st h e s i s ，w em a i n l yd e v o t eo u r s e l v e st os t u d y i n gt h ee n u m e r a t i o na n d u n i f o r md i s t r i b u t i o no fl a t t i c ep a t h so fs e v e r a lt y p e sw i t ht h ea i do fv a c i l l a t i n g t a b l e a u x ，f l a w1 e m m a ，e t c o s c i l l a t i n gt a b l e a u xa n dv a c i l l a t i n gt a b l e a u xf i r s ta p p e a r e di nt h ef i e l do f a l g e b r a h o w e v e r ，t h e ya r ec l o s e l yr e l a t e dt om a t c h i n g sa n dp a r t i t i o n sw h i c ha x e t h ei m p o r t a n tr e s e a r c ho b j e c t si nc o m b i n a t o r i c s o s c i l l a t i n gt a b l e a u xw e r ef i r s t d e f i n e d ( t h o u g hn o tw i t ht h a tn a m e ) b y b e r e l ei n1 9 8 6 s t a n l e yc o n s t r u c t e dao n e - t o - o n ec o r r e s p o n d e n c eb e t w e e nt h es e to fo s c i l l a t i n gt a b l e a u xo fs h a p e0a n dt h e s e to fm a t c h i n g sb yu s i n gav e r s i o no ft h er s ka l g o r i t h m ，a n dt h ec o r r e s p o n d e n c e w a se x t e n d e db ys u n d a r a mi n1 9 9 0 v a c i l l a t i n gt a b l e a u xw e r ei n t r o d u c e db y h a l v e r s o na n dr a mi m p l i c i t l yi n2 0 0 5 i n2 0 0 7 ，c h e ne ta 1 e s t a b l i s h e dab i j e c t i o n b e t w e e nv a c i l l a t i n gt a b l e a u xo fs h a p e0a n dp a r t i t i o n s a sa na p p h c a t i o no f t h i sb i j e c t i o n ，t h e ys o l v e da ni m p o r t a n tp r o b l e mi ne n u m e r a t i v ec o m b i n a t o r i c s r o u g h l ys p e a k i n g ，t h e yp r o v e dc o m b i n a t o r i a l l y t h a tt h ec r o s s i n gn u m b e r s a n dt h e n e s t i n gn u m b e r sa x ed i s t r i b u t e ds y m m e t r i c a l l yo v e ra l lp a r t i t i o n sa sw e l la so v e r a l lm a t c h i n g s n o w ，o s c i l l a t i n gt a b l e a u xa n dv a c i l l a t i n gt a b l e a u xh a v eb e c o m ea s t r o n ga n du s e f u lt o o li ns t u d y i n gt h ep r o p e r t i e sa n de n u m e r a t i o no fp a r t i t i o n s ， m a t c h i n g s ，e t c t h ew e l l - k n o w nc h u n g - f e u e rt h e o r e mi sac l a s s i c a lr e s u l ti ne n u m e r a t i o n c o m b i n a t o r i c s ，w h i c hi sm a i n l ya b o u tt h eu n i f o r md i s t r i b u t i o no ff r e ed y c kp a t h s o nf l a wn u m b e r t h i st h e o r e mw a sd i s c o v e r e db ym a c m a h o ni n1 9 0 9 ，b u tn a m e d a f t e rt h ew o r ko fi t sr e - d i s c o v e r sc h u n ga n df e l l e ri n1 9 4 9w h op r o v e dt h er e s u l tb y u s i n ga n a l y t i cm e t h o d o v e rt h ey e a r s ，t h i st h e o r e m h a sb e e ne x t e n s i v e l ys t u d i e d a n dp r o v e di nd i f f e r e n tw a y s f o re x a m p l e ，r a n e y , n a r a y a n a ，r e r s h o w i t z ，z a k s ， i i i a b s t r a c t e ta 1 u s e dt h ec y c l el e m m ao rc y c l i cp a t h st op r o v et h et h e o r e mr e s p e c t i v e l y ； c a l l a n ，j e w e t t ，r o s s ，e ta 1 p r o v e di tb ye s t a b l i s h i n gs t r a i g h t f o r w a r db i j e c t i o n s r e s p e c t i v e l y b e s i d e s ，t h ec l a s s i c a lc h u n g - f e l l e rt h e o r e mh a si n s p i r e dm a n yg e n e r a l i z a t i o n sa n dv a r i a t i o n s f o re x a m p l e ，i n2 0 0 1 ，w o a nf o u n da n o t h e ru n i f o r m l y d i s t r i b u t e dp a r a m e t e ro ff r e ed y c kp a t h s ，i e ，a b s o l u t em i n i m u ml e n g t h ，a n di n t h es a b i n ey e a r ，s h a p i r os t u d i e dt h eu n i f o r md i s t r i b u t i o no fs p e c i a lm o t z k i np a t h s 0 na b s o l u t em i n i m u ml e n g t h ；e ue ta 1 g a v ear e f i n e m e n tf o r mo ft h ec h u n g - f e l l e r t h e o r e mb yu s i n gt h et a y l o re x p a n s i o n so fg e n e r a t i n gf u n c t i o n s ，a n dt h e yf o u n da w e i g h t e dv e r s i o nf o rf r e es c h r 6 d e rp a t h si n2 0 0 5 ；c h e ne ta 1 d e r i v e dt h ec l a s s i c a l c h u n g - f e l l e rt h e o r e ma n d t h ew e i g h t e dv e r s i o nf o rf r e es c h r s d e rp a t h so n c em o r e b yi n t r o d u c i n gt h eb u t t e r f l yd e c o m p o s i t i o no fd o u b l yr o o t e dp l a n et r e e s ；l a t e l y , m aa n dy e hd i ds o m ew o r kt os t u d yt h eu n i f o r md i s t r i b u t i o no ft h r e ec l a s s e so f l a t t i c ep a t h so nf l a wn u m b e ra n da b s o l u t em i n i m u ml e n g t hr e s p e c t i v e l y i nt h i st h e s i s ，w em a i n l yf o c u so ns t u d y i n gt h ee n u m e r a t i o na n du n i f o r m d i s t r i b u t i o no fn o n c r o s s i n gf r e ed y c kp a t h s ，m - f r e es c h r s d e rp a t h s ，p a r t i a lk - f r e e d y c kp a t h s ，e t c o u rp r i n c i p a lc o n t r i b u t i o n sa r es t a t e da sf o l l o w s i nc h a p t e r2 w eo b t a i na ne n u m e r a t i o nf o r m u l af o rk - t u p l e so fn o n c r o s s - i n gf r e ed y c kp a t h s ，w h i c hi sb a s e do nt h ec o r r e s p o n d e n c eb e t w e e nk - t u p l e so f n o n c r o s s i n gf r e ed y c kp a t h sa n dp l a n e e n u m e r a t i o nf o r m u l ao fp l a n ep a r t i t i o n s p a r t i t i o n sw i t hb o u n d e ds i z e ，a n dt h e g i v e nb ys t a n l e y r e s t r i c t i n gkt o2 ，w e f i n dt h en u m b e ri se q u a lt ot h a to fn o n c r o s s i n gp a r t i t i o n sw i t hag i v e nn u m b e ro f b l o c k sw h i c hi sd u et oc a l l a n w i t ht h ea i do fv a c i l l a t i n gt a b l e a u x ，w ee s t a b l i s ha o n e - t o - o n ec o r r e s p o n d e n c eb e t w e e np a k so fn o n c r o s s i n gf r e ed y c kp a t h so fl e n g t h 2 na n dn o n c r o s s i n gp a r t i t i o n so f 2 n + 1 w i t h 几+ lb l o c k s b e s i d e s ，i nt e r m so f l a b e l l em e r g i n ga l g o r i t h m ，w ef i n dac h a r a c t e r i z a t i o no fd y c kp a t h sc o n s t r u c t e d f r o mp a i r so fn o n c r o s s i n gf r e ed y c kp a t h s i nc h a p t e r3 ，o no n eh a n d ，w ed os o m ew o r kt os t u d yt h eu n i f o r md i s t r i - b u t i o no fm - f r e es c h r s d e rp a t h so nf l a wn u m b e ra n da b s o l u t em i n i m u ml e n g t h r e s p e c t i v e l y o u rr e s u l t su n i f ya n dg e n e r a l i z et h ef o r m e rs t u d i e so nt h ec h u n g - f e l l e rp r o p e r t i e so ff r e ed y c kp a t h s ，k - f r e ed y c kp a t h s ，f r e es c h r s d e rp a t h s ，e t c i ti sw o r t hm e n t i o n i n gt h a tw ed e r i v ea ni n t u i t i v eb u te l e g a n t1 e m m a ，n a m e df l a w l e m m a ，i nt h i st h e s i s t h i sl e m m ac a nb e 访e w e da sag e n e r a l i z a t i o no fc y c l e i v a b s t r a c t 1 e n l h l as i n c ei tc o n t a i n sm o r ei n f o r m a t i o nt h a nt h ec l a s s i c a lc y c l el e m m a n o r e t h a tf l a wl e m m ap l a y sac r u c i a lr o l ei np r o v i n gt h eu n i f o r md i s t r i b u t i o no fm - f r e e s c h r s d e rp a t h so i lf l a wn u m b e r m o r e o v e r ，w eg i v ea ne a s i e rc o m b i n a t o r i a lp r o o f f o rt h ee n u m e r a t i o nf o r m u l ao fm - s d l r s d e rp a t h sw i t ha g i v e nn u m b e ro fd i a g o n a l s t e p s o nt h eo t h e rh a n d ，w ef i n dan e wp r o o ff o rt h eu n i f o r md i s t r i b u t i o no ff r e e d y c kp a t h so na b s o l u t em i n i m u ml e n g t h i nc h a p t e r4 ，w et u r nt os t u d yt h ee n u m e r a t i o no fp a r t i a lk - d y c k p a t h s ，a n d o b t a i na n o t h e rr e f i n e m e n tf o r mo ft h ec l a s s i c a lc h u n g - f e l l e rt h e o r e m s p e c i f - i c a l l y , w eg e tt h eu n i f o r md i s t r i b u t i o no fk - f r e ed y c kp a t h sw i t hag i v e nt y p e o nf l a wn u m b e r b e s i d e s ，ab i j e c t i o nb e t w e e np a r k i n gf u n c t i o n so fl e n g t hna n d r o o t e df o r e s t so nt h ev e r t e xs e t 佗】i sg i v e nw i t ht h ea i do fl a b e l e dd y c kp a t h s m o r e o v e r ，as e q u e n c eo fe n u m e r a t i o nf o r m u l a ef o rn o n c r o s s i n gp a r t i t i o n s ，p a r k i n g f u n c t i o n s a n dl a b e l e df o r e s t sf o u o w i nc h a p t e r 5 ，w ea d o p ta n o t h e rv i e w p o i n tt or e - c o n s i d e rt h ec l a s s i c a lc h u n g - f e l l e rt h e o r e m ，t h a ti s ，e a c hf r e ed y c k p a t hi ss e e na sal a t t i c ew a l k f r o mt h eo r i g i n a n db a c kt ot h eo r i g i nw i t ht h es t e p ( 1 ，0 ) o r ( - 1 ，o ) i tm a k e su sb ea b l et of i n d a n dp r o v et w oi n t e r e s t i n gc h u n g - f e l l e rp r o p e r t i e sa b o u tt w oc l a s s e so fl a t t i c e w a l k si naq u a r t e ro fp l a n e k e yw o r d s ：f r e ed y c kp a t h ，v a c i l l a t i n gt a b l e a u ，n o n c r o s s i n gp a r t i t i o n ，m - f l e e s c h r s d e rp a t h ，f l a wl e m m a ，f l a wn u m b e r ，a b s o l u t em i n i m u m l e n g t h ，p a r t i a lk d y c kp a t h a m ss u b j e c tc l a s s i f i c a t i o n ( 2 0 0 0 ) ：0 5 a 0 5 ，0 5 a 1 5 v 南开大学学位论文版权使用授权书 本人完全了解南开大学关于收集、保存、使用学位论文的规定， 同意如下各项内容：按照学校要求提交学位论文的印刷本和电子版 本；学校有权保存学位论文的印刷本和电子版，并采用影印、缩印、 扫描、数字化或其它手段保存论文；学校有权提供目录检索以及提供 本学位论文全文或者部分的阅览服务：学校有权按有关规定向国家有 关部门或者机构送交论文的复印件和电子版；在不以赢利为目的的前 提下，学校可以适当复制论文的部分或全部内容用于学术活动。 学位论文作者签名：涉骨芝史 夕年占月午日 经指导教师同意，本学位论文属于保密，在年解密后适用 本授权书。 指导教师签名：学位论文作者签名： 解密时间：年 月日 各密级的最长保密年限及书写格式规定如下： 一+ ”_ _ “w + _ ” ；内部5 年( 最长5 年，可少于5 年) ：秘密1 0 年( 最长l o 年，可少于1 0 年) 机密2 0 年( 最长2 0 年，可少于2 0 年) l ，。，一j ，。，。一。+ ，+ 。二 南开大学学位论文原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师指导下，进行 研究工作所取得的成果。除文中已经注明引用的内容外，本学位论文 的研究成果不包含任何他人创作的、已公开发表或者没有公开发表的 作品的内容。对本论文所涉及的研究工作做出贡献的其他个人和集 体，均已在文中以明确方式标明。本学位论文原创性声明的法律责任 由本人承担。 学位论文作者签名： 如7 涉屯灸 年毛月午日 c h a p t e r1 i n t r o d u c t i o n c h a p t e r1 i n t r o d u c t i o n 1 1n o t a t i o n sa n db a c k g r o u n d s 1 1 1 p a i r so fn o n c r o s s i n gf r e ed y c kp a t h sa n dn o n c r o s s i n gp a r t i t i o n s a d y c kp a t ho fl e n g t h2 ni sal a t t i c ep a t hf r o mt h eo r i g i nt ot h ep o i n t ( 2 n ，0 ) c o n s i s t i n go fu ps t e p su = ( 1 ，1 ) a n dd o w ns t e p sd = ( 1 ，一1 ) t h a td o e sn o tg o b e l o wt h ez a x i s m o r e o v e r ，al a t t i c ep a t hf r o mt h eo r i g i nt o ( 2 n ，0 ) u s i n gt h e s t e p su a n ddw i t h o u tt h er e s t r i c t i o no nad y c kp a t hi sc a l l e da 加ed y c kp a t ho f l e n g t h2 n u s u a l l y , a ( f r e e ) d y c kp a t ho fl e n g t h2 ni sr e p r e s e n t e da sas e q u e n c e o fnu sa n dnd s f o re x a m p l e ，f i g u r e1 1s h o w sad y c kp a t ho fl e n g t h8 ， t h a ti s ，u u d u d d u d ak o t u p l e ( p 1 ，p 2 ，r ) o f ( f r e e ) d y c kp a t h sf r o mt h e o n s 矗u ( 0 ，0 ) t ot h ep o i n t ( 2 n ，0 ) i sc a l l e dn o n c r o s s i n g i fe a c h 只n e v e rg o e sb e l o w 只+ 1f o r1 i k 一1 f i g u r e1 1ad y c kp a t ho fl e n g t h8 ap a r t i t i o n 盯af i n i t es e tsi sac o l l e c t i o n7 r = b 1 ，岛，玩) o fs u b s e t s o fss u c ht h a ti ts a t i s f i e st h ef o l l o w i n gt h r e ec o n d i t i o n s ： 1 1 鼠0f o re a c hi ； 2 b inb j = 0 i fi j ，a n d 3 b lu 玩u ub k = s e a c hb i se a l u e dab l o c ko f7 r r e c a l lt h a tap a r t i t i o no la 礼i n t e g e r 扎ni s a 8 e q u e n c e 入= ( 入l ，入k ) n 七s u c ht h a t 入i = na n da 1 入南，w h e r en i s t h es e to fn o n n e g a t i v ei n t e g e r s n o t et h a tw er e g a r dt w op a r t i t i o n sa si d e n t i c a li f t h e yd i f f e ro n l yi nt h en u m b e ro f t e r m i n a lo 8 ；f o re x a m p l e ，( 2 ，2 ，1 ) = ( 2 ，2 ，1 ，0 ，o ) a p l a n ep a r t i t i o ni sa l la r r a y6 = ( 如) i j 1o fn o n n e g a t i v ei n t e g e r ss u c ht h a t6 h a s f i n i t e l ym a n yn o n z e r oe n t r i e sa n d i sw e a k l yd e c r e a s i n gi nr o w sa n dc o l u m n s i f 盈，j = n ，t h e nw es a yt h a t6i sap l a n ep a r t i t i o n o f 礼a n dw r i t e1 6 i5 钆ap a r t o fap l a n ep a r t i t i o n6 = ( 如) i sap o s i t i v ee n t r y 0 t h es h a p eo fap l a n e p a r t i t i o n 占i st h ei n t e g e rp a r t i t i o n 入f o rw h i c h 艿h a s 九n o n z e r op a r t si nt h e i - t h r o w o b v i o u s l y , a l lo r d i n a r yi n t e g e rp a r t i t i o n 入o f a ni n t e g e r 佗m a yb er e g a r d e d a 8aw e a k l yd e c r e a s i n go n e - d i m e n s i o n a la r r a y ( a 1 ，a 2 ，) o fn o n n e g a t i v ei n t e g e r s w i t hf i n i t es u p p o r t t h u s ，p l a n ep a r t i t i o n sa r ean a t u r a lg e n e r a l i z a t i o nt ot w o d i m e n s i o n so fo r d i n a r yp a r t i t i o n s t h ep l a n ep a r t i t i o n so fi n t e g e r s0 礼3a r e g i v e nb y a t ，口c i l l a t i n gt a b l e a u 喈竹o fs h a p ek a n dl e n g t h2 ni sas e q u e n c e ( 入o ，入1 ，入2 ”) o fp a r t i t i o n ss u c ht h a t 1 a o = 谚，a n d 入2 n = 入； 2 。a 2 + 1i so b t a j n e df r o ma 班b yd o i n gn o t h i n g ( i e ，入2 + 1 = 入2 ) o rd e l e t i n ga s q u a r e ，a n d 3 入2 ii so b t a i n e df r o m 入2 i 一1b yd o i n gn o t h i n go ra d d i n gas q u a r e a b b r e v i a t et h ep a r t i t i o na = ( a 1 ，a 2 ，) b ya i a 2 a ne x a m p l eo fav a c i l l a t i n g t a b l e a uo fs h a p e1 1a n dl e n g t h1 0i sg i v e nb y 2 1 1 上，上 2 1 l 1 工1 llll 231 1 ll2l n v 0 谚112 22 1 1 11 111 1 l e t 【n 】：= 1 ，2 ，礼) g i v e nap a r t i t i o npo f 叫，t h es t a n d a r dr e p r e s e n t a t i o no ft h ep a r t i t i o n 尸i sag r a p hgo n 【几】s u c ht h a tab l o c k i l ，i 2 ，i 七) 0 fpw r i t t e ni nt h ei n c r e a s i n go r d e ri l i 2 i kc o r r e s p o n d st oap a t h ( i 1 ，i 2 ，i k ) f o re x a m p l e ，t h es t a n d a r dr e p r e s e n t a t i o no ft h ep a r t i t i o n1 3 5 8 - 2 9 - 4 6 - 7i si l l u s t r a t e di nf i g u r e1 2 m e a n w h i l e ，w em a yv i e wt h es t a n d a r dr e p r e - s e n t a t i o no fp a sad i r e c t e dg r a p hb e c a u s ee a c he d g ec a na l w a y sb ec o n s i d e r e da s a na r c ( i ，j ) w i t hi j ，a n dw es a yt h a tii st h ez 啦e n dp o i n ta n dji st h er g h t e n dp o i n t i nt h i st h e s i s ，w eu s ei i nt od e n o t et h es e to fp a r t i t i o n so f 【n 】 123 4 5 6 7 8 9 f i g u r e1 2 t h es t a n d a r dr e p r e s e n t a t i o no f1 3 5 8 - 2 9 4 6 - 7 l e t 忌2a n d 尸i i n d e f i n ea 七一c r o s s i n g ( r e s p 尼一n e s t i n g ) o fp a sas e to fk a r c s ( i l ，j 1 ) ，( i 2 ，j 2 ) ，( i k ，靠) i nt h es t a n d a r dr e p r e s e n t a t i o no fp s u c ht h a ti l i 2 i k j l j 2 j 七( r e s p i l i 2 i k 九 歹2 3 a n db a l e ke ta 1 2 p o i n t e do u tt h a tt h en