（应用数学专业论文）匹配与对合中的有禁模式.pdf

摘要 本文主要研究了几类有禁匹配和有禁对合的计数问题。本论文由三部分组成。 第一部分主要研究类有禁匹配的计数问题。匹配是没有不动点的对合。笕 部分主要研究有禁对合问题。最后一部分主要是关于不完整m o t z k i n 路的等式 和关于对称三叉树和不交图的等式的组合解释问题。 第一部分由第二章和第三章组成。在第二章中，我们感兴趣的问题是类 有禁匹配的计数问题。我们得到下面的结论。 1 在【2 n j 上避免1 2 3 1 2 模式的包含m 个相交的匹配数等于 去( 扎：m ) ( 絮：? ) 2 在f 2 n 上避免1 2 3 1 2 模式的匹配数等于3 一g a t a l a n 数g ，3 。 3 同时避免1 2 3 1 2 模式和1 2 1 3 2 3 模式的匹配与在第一层没有峰的s c h l o ( 1 e l 路 之间有一个一一对应。他们的计数与s u p e r _ c a t a l a n 数是一致的。 4 在 2 n 1 上的同时避免1 2 3 1 2 模式和1 2 1 3 2 3 模式的包含m 个相交的匹配数是 i ( 珊： 这是s u p e 卜c a t a l a n 数的一个细化。 5 通过运用s t a n l e y 的振荡杨表与避免1 2 3 1 2 模式的匹配之间的一一对应，我 们刻划了对应于避免1 2 3 1 2 模式的匹配的振荡杨表。 6 。在【2 n 1 上避免1 2 3 1 2 模式的匹配与从( o ，o ) 到( 2 n ，n ) 的走e = ( 1 ，o ) 和= ( o ，1 ) 步的不穿过线= z 2 的格路之间存在一个对应。 7 通过对生成树的研究，我们证明了1 2 1 3 2 ，1 2 1 2 3 ，1 2 3 2 1 ，1 2 2 3 1 ，1 2 2 1 3 模式 和1 2 3 1 2 模式是w 1 1 f 等价的。 在第三章中，我们开始研究避免1 1 2 3 模式和1 1 3 2 模式匹配的计数问题。我 们得到了下面的结论。 8 在 2 7 叫上避免1 1 2 3 模式的匹配与从( o ，2 ) 到( 2 n ，o ) 的非负格路之间存在一个 一对应。 9 在 2 叫上避免1 1 2 3 模式的匹配数等于从( o ，2 ) 到( 2 n ，o ) 的非负格路数 即熹( 2 。) 。 1 0 避免1 1 2 3 模式的匹配的计数问题可以缩减为某些格路的计数问题。 n 在 2 n 上避免1 1 3 2 模式的匹配与从( o ，o ) 到( 2 n ，o ) 的以向上步开始的可以通 过x 轴的格路之间存在一个一一对应。 1 2 在 2 n 上避免1 1 3 2 模式的匹配数等于；( 哿) 。 第二部分由第四章和第五章组成。在第四章中，我们给出了在 n 】上的避 免3 2 1 4 模式的对合与长为n 的m o t z k i n 路之间的一个一一对应。由于模式3 2 1 4 和 模式1 4 3 2 在翻转取补的运算下是等价的，从而我们解决了g u i b e r t 提出的猜 想，即在i n j 上避免1 4 3 2 模式的对合数等于m o t z k i n 数 靠。我们的构造在特殊情 况下导出了下面的一些结果。 1 3 在 扎j 上避免3 2 1 模式的对合与n 长的在x 轴上没有水平步的m o t z k i n 路之间 存在一个一一对应。 1 4 在c n j 上避免3 2 1 模式的对合数等于( 【；j ) 。 1 5 在h 上避免3 2 l 模式的包含k 个固定点的对合数露( 3 2 1 ) 等于 物，= 掣蓑淼 1 6 在 2 n 】上避免3 2 l 模式的没有固定点的对合数等于c a t a l a n 数c k 。并且这样 的对合对应于长为2 n 的d y c k 路。 在第五章中，我们从另外一个角度来考虑有禁对合的问题。我们研究了 有n 个字母的恰好包含r 0 个2 3 1 模式的对合的生成函数。我们给出了求包含 了给定数目个2 3 l 模式的对合的生成函数的明确表达式的一个算法。我们得到 下面的结论。 1 7 对于给定的r ，要找到这样的生成函数只需考虑最多在2 r + 2 个字母上的对 合。 1 8 通过把这个算法运用到包含了给定数目个2 3 1 模式的避免1 2 ( 2 1 ) 模 式的对合与包含了给定数目个2 3 1 模式的偶( 奇) 对合上面，我们导出了 他们的生成函数的明确表达式。 在本文的最后一个部分，通过给出具有多条提升线的不完整的2 一m o t z k i n 路与自由的3 一m o t z k i n 路之间的一个一一对应，我们得到了一个最近由c a m e r o n 和n k w a n t a 导出的等式的组合解释。我们还给出了在不交树 的一个改变奇 偶性的对合。通过这个对合我们导出了一个关于不交树和对称的三叉树 的公式的组合解释。从而解决了h o u 幽提出的公开问题。我们用p a n h o l z e r 和p r o d i n g e r 的表示方式来表示不交树。我们还找到了一类不交树与对称的三叉 树之间的一个列+ 应。关于不交树的另外一个结果是通过在连通的不交图上的对 合来得到了给定边数与下降数的不交树和给定了点数与边数的连通不交图之间 的一个关系，就是说我们可以用有n + 1 个点m 条边的连通不交图的数目来表示 有n 条边k 个下降的不交树的数目。 关键词：匹配，对合，有禁模式，格路，d y c k 路，m o t z k i n 路，不完整m o t z k i n 路，自由m o t z k i n 路，s c h r 6 d e r 路，振荡杨表，r s k 算法，七一c a t a l a n 数，s u p e r - c a t a l a n 数，生成树，不交树，连通不交图，对称三叉树 u 1 a b s t r a c t a b s t r a c t 工、h i st h e s i sc o n c e r n ss e v e r a le n u m e r a t i v er e s u l t so nm a t c h i n g sa n di n v o l u t i o n s w i t hr e s t r i c t l o n st h et h e s i sc o n s i s t so ft h r e ep a r t s t h e6 r s tp a t tc o n t l i b u 【e st o t h ee n u m e r a t i o np r o b l e mo fm a t c h i n g s ( i n v o l u t i o n sw i t h o u tf i x e dp o i n t s ) a v o i d i n gp a r t i a lp a t t e r n s t h es e c o n dp a r tc o n t r i b u t e st ot h ep r o b l e mo fi n v o i u t i o n s w i t hf o r b i d d e np a t t e r n s w h i l et h ei a s tp a r tc o n t r i b u t e st ot h ec o m b i n a t o r i a le x - p l a n a t i o 玎so fa nj d e n t i t yo np a r t i a lm o t z k j np a t h sa n dj d e n 钮t i e so nn o n c r o s s i n g t r e e s ，s y m m e t r i ct e r n a r yt r e e sa n dn o n c r o s s i n gg r a p h s t h e 矗r s tp a r tc o n s i s t so fc h a p t e r2a n dc h a p t e r3i nc h a p t e r2w ea r e i n t e r e s t e di nt h ee n u m e r a t i o no fac l a s so fm a t c h i n 毫sa v o i d i n gc e r t a i np a r t i a l p a t t e r n s t h ef o l l o w i n gr e s u l t sa r eo b t 越n e d 1 t h en u m b e ro f l 2 3 1 2 一a o i d i n gm a t c h i n g so n 【2 几】w i t he x a c t l ym c r o s s j n g s i sg i v e nb y ；( 礼：m ) ( 麓：? ) 礼 n 一1几+ 1 2 t h en u m b e ro f l 2 3 1 2 一a v o i d i n gm a t c h j n g s o n 【2 n 】i se q u 出t o3 一c a t a l a nn u m - b e r g3 3 m a t c h i 】1 9 sa v o 试i n gb o t hp a t t e r n s1 2 3 1 2a n d1 2 1 3 2 3a r ei no n e - t o o n ec o r r e s p o n d e l 】c ew i t hs c h r 6 d e rp a t h sw i t h o u ta j 】yp e a ka tl e v e lo n e s u c hp a t h s a 1 ec o u n t e db yt h es u p e r - c a t a l a nn u m b e r so rt h el i t t l es c h r 6 d e rn u m b e r s 4 t h en u i n b e ro fm a t c h i n g so n 2 n 】a o i d i n gb o t hp a t t e r n s1 2 3 1 2a n d1 2 1 3 2 3 w i t hm c r o s s j u g si se q u a lt o ：( 撒：? ) ， w h i c hi sar e 6 n e m e n to ft h es u p e r c a t a l a nn u m b e r s 5 b ya p p l y i n gs t a n l e y sb 玎e c t i o nb e t w e e no s c i l l a t i n gt a b l e a u xa n d1 2 3 1 2 一 a ，o i d i n gm a t c h i n g s ，w ed e r i v eac h a r a c t e r i z a t i o no ft h eo s c i l l a t i n gt a b l e a u x f o r1 2 3 1 2 一a v o i d i n gm a t c h i n g s 1 v a b s 打a c 6 t h e r ei sab 巧e c t i o nb e t w e e nt h es e to f1 2 3 1 2 一a o i d i n gm a t c h i n g so n 2 n a n dt h es e to j 】a t t j c ep a t h sf r o m ( o ，o ) t o ( 2 n ，佗) u s j n gs t e p s 占= ( 1 ，o ) a n d = ( o 、1 ) a n dn e v e r1 y i n ga b o v et h en n e 可= z 2 7 b yu s i n gt h eg e n e r a t i n gt r e e s ，w es h o wt h a tt h ep a t t e r n s1 2 1 3 2 ，1 2 1 2 3 ， 1 2 3 2 1 ，1 2 2 3 1 ，1 2 2 1 3a r ee q u i v a l e n tt o1 2 3 1 2i nt h es e n s eo fw i l f - e q u i v 缸e n c e i nc h a p t e r3 ，w eb e g i nt os t u d ym a t c h i n g sa o i d i n gp a r t i a lp a t t e r n s1 1 2 3 a 皿d1 1 3 2 t h ef o l l o w i n gr e s u l t sa t eo b t 甑n e d 8 t h e r ei sab l j e c t i o nb e t w e e nt h es e to f1 1 2 3 一a o i d i n gm a t c h i n g so n 2 札 a n d t h es e to fn o n n e g a t i v e1 a t t i c ep a t h sf r o m ( o ，2 ) t o ( 2 n ，o ) 9 t h en u n l l ) e 】1o f1 1 2 3 一a v o i d i n gm a t c h i n g so n 2 n i se q u a lt ot h en 1 1 m b p ro f n o n n e g a t i v el a t t i c ep a t h sf r o m ( o ，2 ) t o ( 2 礼，o ) ，w h i c hi se q u a lt o 熹( n 孙 几+ 2 n l ， l o t h er e 最n e de n u m e r a t i o no f1 1 2 3 一a v o i d i n gm a t c h i n 9 8c a nb er e d u c e dt ot h e e n u m e r a t i o no fc e r t a i nl a t t i c ep a t h s 1 1 t h e 工 ei sab 巧e c t j o nb e t w e e nt h es e to f1 1 3 2 a o i d i n gm a t c h i n g so n 2 札ja n d t h es e to f1 a t t i c ep a t h sf r o m ( o ，o ) t o ( 2 礼，o ) s t a r t i n gw i t ha nu ps t e p ，w h i c h m a yg ob e l o wt h ez a x i s 1 2 t h en u m b e ro f1 1 3 2 一a o 讨i n gm a t c h i n g so n 【2 叫e q u a l sj ( 哿) t h es e c o n dp a r tc o n s i s t so fc h a p t e r4a n dc h 印t e r5 i nc h a p t e r4 ，w e g i v eab i j e c t i o nb e t w e e n t h es e to f3 2 1 4 - a o i d i i 培i n v o l u t i o n so nf 叫a n dt h es e to f m o t z k i np a t h so n e n g t hnl na n s w e rt oac o n j e c t u r eo fg u m e r ti nt h es e n s et h a tb y r e v e r s e dc o m p l e m e n t ，3 2 1 4 - a o i d i n gi n v o l u t i o n sa r ei no n e t o o n ec o r r e s p o n d e n c e w i t h1 4 3 2 一a v o i d i n gi n v o l u t i o n s 0 u rc o n s t r u c t i o nh a ss e v e r a lc o n s e q u e n c e sa s f o l 】o w s 1 3 t h e r ei sab 蛆e c t i o nb e t 、v e e nt h es e to f3 2 1 一a v o i d i n gi n v o l u t i o n so nh 1a n d t h es e to fm o t z k j np a t h so fl e n 酗hnw i t h o u th o r i z o n t a ls t e p so n 弘a x i s v a b s t r a c t 1 4 t h en u m b e r 。f3 2 l _ a v 。i d i n gi n v 。1 u 鼢s 。nnl e t t e r si sc 。u n t e d b y ( 【渺 1 5 t h en u m b e r 增( 3 2 1 ) o f3 2 1 一a v o i d i n gi n v o l u t i o n so n 他l e t c e r sw i t h 忽a x e d p o i n t s l sg l v e nb y 相，= f 掣篡焉 1 6 ，t h en u m b e l o f3 2 1 一a v o i d i n gi n v o l u t j o n so n2 凡l e t t e r sw i t h o u tn x e dp o i n t s i st h en t hc a t a l a nn u m b e rg m o r e o v e r ，s u c hi n v 0 1 u t i o n sc o r r e s p o n dt o t h es e to f d y c kp a t h so f l e n 舒h2 n i nc h a p t e r5 ，f r o l na n o t h e rd i r e c t i o n jw eb e g i nt os t u d yt h eg e n e r a t i n gf u n c t i o n f o rt h en u m b e ro fi n v o l u t i o n so n 他1 e t t e r sc o n t a i n i n ge x a c t l yr oo c c u r r e n c e so f 2 3 1 w bg i v ea na l g o r i t h mt og e tt h ee x p l i c i tf o r m u i af o rt h eg e n e r a t i n gf u n c t i o n f o rt h en u m b e ro fi n v o l u t i o n sc o n t a j n i n gap r e s c r i b e dn u m b e ro fo c c u r r e n c e so f 2 3 1 t h ef 0 】l o w i n gr e s u l t sa r eo b t a i n e d 1 7 i ti ss h a w nt h a t6 n d i n gt h i sf u n c t i o nf o rag l v e nra m o u n t st oar o u t i n e c h e c ko fa l li n v o l u t i o n so na tm o s t2 r + 2l e t t e r s 1 8 b ya p p l y i n g 咖ea l g o r i t h mt oi n v o l u t i o n sw i t hap r e s c r i b e dn u m b e ro fo c c u h e n c e so f2 3 1a n da v o i d i n gt h ep a t t e r n1 2 3 七( 七 2 1 ) a n de v e n ( o d d ) i n v o l u t i o n sw i t hap r e s c r i b e dn u m b e ro fo c c u r r e n c e 8o f2 3 l ，w ed e r i v et h e e x p l i c i tf o r m u l a sf o rt h e i rg e n e r 8 t i n gf u n c t i o n s i nt h et h i r dp a r t ，b yg i v i n gab 幻e c t j o nb e t w e e np a r t i a l2 一m o t z k i np a t h sw i t h m u l t i p l ee l e v a t i o n1 i n e sa n df r e e3 一m o t z np a t h s ，、ep r a v i d eac o m b i n a t o r i a l e x p l a n a t i o no fa ni d e h t i t yr e c e n t l yo b t a i n e db yc a m e r o na 皿dn k w a n t a w ba l s o g i v eap a r i t yr e v e r s i n gi n v o l u t i o no nn o n c r o s s i n gt r e e st h a 土l e a d st oac o m b i n a t o _ r i a li n t e r p r e t a ti o no faf o r m u l ao nn o n c r o s s j n gt r e e sa n ds y m m e t r i ct e r n a r yt r e e s i na n s w e rt oap r o b l e mp r o p o s e db yh o u g ht h et h i r dr e s u l to ft h i sc h a p t e ri s ap a r i t yr e v e r s i n gi n v o l u t i o no nc o n n e c t e dn o n c r o s s i n gg r a p h sw h i d l1 e a d st oa r e l a t i o nb e t w e e nt h en u i n b e ro fn o n c r o s s i gt r e e sw i t hne d g e sa n d 后d e s c e r l t s a n dt h en u i n b e ro fe o n n e c t e dn o n c r o s s i n gg r a p h sw i t hn + 1v e r t i c e sa n dm e d g e s v l a b s 打a c t k e y w o r d s ：m a t c h i n g ，i n v o l u t i o n ，f o r b i d d e np a t t e r n ，l a t t i c ep a t l l ，d y c kp a t h ， m o t z k i np a t h p a r t i a lm o t z k i np a t h ，f r e em o t z k i np a t h ，s c h r 6 d e rp a t h ，o s c i l 1 a t i n gt a b l e 趴l ，r s ka l g o r i t h m ，七一c a t a l a nn u m b e r ，s u p e 卜c a t a l a nn u 瑚b e r ，g e n e r a t i n gt r e e ，n o n c r o s s i n gt r e e ，c o n n e c t e dn o n c r o s s i n gg r a p h ，s y m m e t r i ct e r n a r y t r e e 南开大学学位论文版权使用授权书 本人完全了解南开大学关于收集、保存、使用学位论文的规定， 同意如下各项内容：按照学校要求提交学位论文的印刷本和电子版 本；学校有权保存学位论文的印刷本和电子版，并采用影印、缩印、 扫描、数字化或其它手段保存论文；学校有权提供目录检索以及提供 本学位论文全文或者部分的阅览服务；学校有权按有关规定向国家有 关部门或者机构送交论文的复印件和电子版；在不以赢利为目的的前 提下，学校可以适当复制论文的部分或全部内容用于学术活动。 学位论文作者签名：子尊夸 p 。占年4 月1 j p 日 经指导教师同意，本学位论文属于保密，在年解密后适用 本授权书。 【指导教师签名：学位论文作者签名： 梦慧畜 i 解密时间：年 月日 各密级的最长保密年限及书写格式规定如下 内部5 年( 晟长5 年，可少于5 年) 秘密l o 年( 最长1 0 年，可少于1 0 年) 机密2 0 年( 晟长2 0 年，可少于2 0 年) 南开大学学位论文原创- l 生声明 本人郑重声明：所呈交的学位论文，是本人在导师指导下，进行研究工作 所取得的成果。除文中已经注明引用的内容外，本学位论文的研究成果不包含 任何他人创作的、已公开发表或者没有公开发表的作品的内容。对本论文所涉 及的研究工作做出贡献的其他个人和集体，均已在文中以明确方式标明。本学 位论文原创性声明的法律责任由本人承担。 学位论文作者签名：予慧亳 伽口年斗月韵日 c h 印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 1 b a c k g r o u n d s m a t c h i n g sw i t hf b r b i d d e np a 上t e r n sh a eb e e ns t u d i e db yd em 6 d i c j sa n dv i e n n o t 5 9 ，d es a i n t e c a t h e r i n e 【6 9 ，g e s s e la n dv i e n n o t 【3 9 ，g o u y o u - b e a u c h a m p s 4 1 ，4 2 1 ，s t e i n 8 2 1 ，r 工b u c h a r d 9 2 】，a n dr e c e n t l yb yk 1 a z a r 5 2 ，5 3 ，5 4 ，c h e n ，d e n g ， d u ，s t a j l l e ya n d1 y 音m 1 6 i ti sw e l lk n o w n t h a tb o t h1 2 1 2 一a 舯i d i n g ( n o n c r o s s i n g ) m a t c h i n g sa n d1 2 2 1 一a v o i d i n g ( n o n n e s t i n g ) m a t c h i i 培s 缸ei no n e - t o - o n ec o r r e - s p o n d e n c ew i t hd y c kp a t h so f1 e n 昏h2 n 【8 1 卜h e n c et h e yc a nb ec o u n t e db yt h e c a t a l a 皿n u m b e r g = 熹( 翟) i na d d i t i o nt ot h e s er e 8 u l t s ，t h ed i s t r i b u t i o no ft h en u m b e ro fc r o s s i n g sh a sb e e n s t u d i e db y b u c h a r d 9 2 ，a n dl a t e rm o r ee x p l i c i t l yb yr j o r d a n 【6 6 w h og a v ea g e n e r a t i n gf u n c t i o n i tw a ss h o w nb yd es a i n t e c a t h e r i n e 6 9 1t h a tc r o s s i n g sa n d n e s t i n g sa r ei d e n t i c 出l yd i 8 t r i b u t e da v e ra l lm a t c h i n g so n 2 礼】，i e ，t h en u m b e ro f m a t 曲i n 摩奶t brc r o s s j n g sbe q u a j 幻曲e 删m b e fd fm 8 t c j 】j n g sw i t brn e s t 抽g s t h ee n u n l e r a t i o no f1 2 3 3 2 1 一a v o i d i n g ( 3 一n o n n e s t i n g ) m a t c h i n g sw a sf i r s t s t u d i e db ydg o u y o u b e a u c h a m p s 4 1 】，i nw h i c hh eg a v eab 巧e c t i o nb e t w e e n i 1 1 v o l u t i o n sw i t hn od e c r e a s i n gs e q u e n c eo f1 e n g t h6a n dp a i r so fn o n c r o s s i n g d y c kl e f tf a c t o r sb yar e c u r s i v ec o n s t r u c t i o n h i sb 巧e c t i o ni se s s e n t i a l l yac o r r e s p o n d e n c eb e t w e e n1 2 3 3 2 1 一a v o i d i n gm a t 出i n g sa n dp a i r so fn o n c r o s s i n gd y c k p a t h s ，w b e r eai n a t c h i n gc a n8 l s ob e n s i d e r e da sa 丘x e d p o i n t f r e ei n v o l u t i o n 1 c h a p t e rl 、i n t r o d u c t i o n r e c e n t l yc h e l j ，d e l l g ，d u ，s t a l l l e ya n dy a n 【1 6 g e n e r a l i z e dt h i sr e s u l ta n d o b t a i n e dt h e 。1 1 u 1 1 1 e r a t i o no f ( 1 2七1 2 七) 一a o i d i n g ( k n o n c r o s s i n g ) 】n a t c h i n g sa n d ( 1 2 盎七 2 1 ) 一a v o i d i n g ( k - n o n n e s t i n g ) m a t c h i n g s f u r t h e r m o r e ，t h e y p r o v e dt h a tk c r o s s j n g sa n dk _ n e s t i n g sa r ej d e n t i c a l i yd i s t r j b u t e do v e r “lm a t c h i n g so n 2 7 t ，ie ，c h en u m b e ro fm a t c h i n g sw i t hrk c r o s s i n g si se q u a lt ot h e n u m b e ro fl n a t c h i n g sw i t hrk n e s t i n g s i n v o l u t j o n sw i t hf o r b i d d e np a t t e r n so c c u r r e di nt h es t u d yo ft h er o b i n s o n _ s c h 锄s t e d k n u t hc o r r e s p o n d e n c e d e n o t eb y 矗( _ ) t h es e to f 丁一a v o n gi n v l u t i o n so n n a n dl e t 厶( 7 _ ) b ei t sc a t d i n a l i t 矿w ew r i t e 盯，盯7i ff o ra l ln ， 厶p ) = 厶( 口，) i nt h i sc a s e ，w ea l s os a yt h a t 盯a n d a r e 厂e g “而o f e 礼s i m i o n a n ds c h m i d t 7 5 f 。u n dt h ec a r d i n a l i t yc l a s s e so ft 兔a 肌dp r o v e dt h ef 0 1 l o w i n g p r o p o s i t i o n s p r o p o s i t i o n1 1 ( s i m i o na n ds c h m i d t 7 5 df b rr 1 2 3 ，1 3 2 ，2 1 3 ，3 2 1 a n d n 1 ， u r ) = ( 黝 p r o p o s i t i o n1 2 ( s i m i o na n ds c h m i d t 7 5 ) f b r 丁 2 3 1 ，3 1 2 ) a n d 礼1 ， 厶( t ) = 铲 m a n yo f t h es e q u e n c e s 厶( r ) ) a r ek n o w nf o r7 _ = 1 2 尼，i nw h j c hc a s et h e s e q u e n c ec o u n t st h en u l n b e ro fs t a n d a r dt a b l e a u xo fs i z enw i t ha tm o s t 七一1 c o l u m n sat h e o r e mo fr e g e vc o v e r s 七= 4a sf 0 1 1 0 w s p r o p o s i t i o n1 3 ( r e g e vf 6 5 ) 硝搦。，= 警( 煎) 击 l ( 1 2 3 4 ) = ( 关) ( ：) 击 i = 0 。 i e 、t h en t h 凡i o t z k i nn u m b e r 。 靠 r e g e va l s og a 怡a na s y m p t o t i cv 出u eo f 厶( 1 2 惫)g o u y o u _ b e a u c h a m p s s t u d i e dy o u n gt a b l e a u xo fb o u n d e dh e i g h ti n 4 l 】a n do b t a i n e df o r m u l a sf b rt h e n u i d b e r so fi n v o l u u o n sa v o i d i n gt h ep a t t e r n1 2 3 4 5o j1 2 3 4 5 6 2 c h a p t e r1 i n t r o d u c t i o n p r o p o s i t i o n1 4 ( g o u y o u b e a m c h a m p s 4 1 ) 厶( 1 2 3 4 5 ) w h e r eq = 击( 棼) ，t h ek t hc a t a l a nn u m b e r n = 2 七一1 n = 2 七 p r o p o s i t i o n1 5 ( g o u y o u b e a u c h a m p s 4 l 】) ，、i 裂 31 几吻+ 2 ) ! “1 2 3 4 5 6 卜f 丽笨 g e s s e l 【3 8 】n t h e ro b t 虹n sa 0 r m u l af o rt h eg e n e r a lp a t t e r n1 2 k w b r ko fg u i b e i ta n do t h e r sh a sa l m o s tc o m p l e t e l yd e t e r m i n e dt h ec a r d i n “i t y c l a s s e so fs 4 s y m m e t r yo ft h er s ka l g o r i t h mi m p l i e s1 2 3 4 4 3 2 1 g u i b e r t b 巧e c t i v e l yo b t 出n e dt h ef 0 1 1 0 w i n gr e s u l t si nh i st h e s l sf 4 4 p r o p o s i t i o n1 6 ( g u i b e r t 4 4 】) 3 4 1 2 i4 3 2 1 p r o p o s i t i o n1 7 ( g u i b e r t 4 4 ) 2 1 4 3 1 2 4 3 g u i b e l ta l s oc o l l j e c t u r e dt h a tb o t h 厶( 2 1 4 3 ) a n d 厶( 1 4 3 2 ) a r ee q u a lt o f o r 礼4 g u j b e t t ，p e r 9 0 1 a ，a n dp i n z a n i 4 6 】p r c v j d e da na 塌r m a t i v ea n s w e r t ot h ef i r s tc o n j e c t u r eb yg i v i n gab 巧e c t i o nb e w t e e nl 2t r e e sw i t h 几e d g e sa n d v e x m 缸yi n v o l u t i o n s ( i 息，2 1 4 3 _ a v o i d i n gi n v o l 砒i o n s ) o nnl e t t e r s p r o p o s i t i o n1 8 ( g u i b e r t ，p e r g o l a ，p i n z a n i 4 6 ) 1 2 3 4 ，2 1 4 3 m o r er e c e n t l y ，ja g g a r dg a v ea na 币r m a t i v ea n s w e rt ot h es e c o n dc o n j e c t u r e b yi n t r o d u c i n gt h ee q u i v a l e n c eo ft h ep a t t e r n1 2 3 4a n dt h ep a t t e m3 2 1 4i n 5 0 i nt h es e n s et h a t3 2 1 4 ，1 4 3 2b yt h eo p e r a t i o no ir e v e r s e dc o m p l e m e n ta n d + 伉q q g ，、l c h a p t e r1 i n t r o d u c t i o n j 。( 1 2 3 4 ) i sk n o 、r nt ob et h en t hm o t z k l nn u 工i l b e r 霸c o m b i n i n ga 1 1o ft h e s e r e s u l t s ，w e6 1 1 dt h a t 厶( 1 2 3 4 ) = 厶( 1 2 4 3 ) = 厶( 1 4 3 2 ) = k ( 2 1 4 3 ) = 厶( 3 4 1 2 ) = k ( 4 3 2 1 ) = 厶 i nad i 丘色r e n td i r e c t i o n ，m a n ya u t h o r ss t a r t e dt oc o n s i d e rt h ee n u m e r a t i o n p r o b l e m