（应用数学专业论文）enumeration+on+set+partitions+and（km）ary+trees.pdf

摘要 本文主要研究了几类带限制的集合分拆以及( ，m ) 一叉树的计数 首先我们给出了集合【n 】= 1 ，2 ，n ) 上的m 正则分拆的一个约简算 法该算法将集合h 上的m 正则分拆转化为集合h l 】上的( m 一1 ) 一正则 分拆我们还证明了分拆的不交性质在这种约简算法下保持不变，从而给出了 s i m i o n u 1 1 m a n 以及k 1 a z a r 的一个组合恒等式的简单证明利用该恒等式我们 还给出了一种广义r n a 二级结构的计数公式对于一般的不交分拆，利用该 算法，我们可以将其转化为一个只包含单点、独立边及自环的图，从而得到一 个将n a r a y a n a 数用c a t a l a n 数表示的恒等式 然后我们介绍了d y c k 路和2 一m o z k i n 路上的标号规则对于任意一个3 长的排列r ，我们都给出了一种d y 矗路上的标号规则，通过这种标号可以建 立长为2 n 的d y c k 路与集合m 上避免r 的有禁排列之间的双射。这些双射还 将排列上的一些统计量转化为d y c k 路上的统计量。对于2 一m o z k i n 路，我们 给出了两种标号规则：最远标号规则与最近标号规则我们可以利用这些标号 规则来研究多种带限制的集合分拆的计数等问题。作为这些标号规则的一个 应用，我们还给出了集合m 上二正则不嵌套分拆( 避免n 6 她的二正则分拆) 和长为n 一2 的2 一m o z k i n 路之间的对应 接下来我们开始研究3 不交匹配和3 不交分拆关于3 不交匹配的计数 是近两年由k l a z a r 提出的问题该问题的更广义的形式是关于不交分拆的 计数我们在本文中指出有三类禁止长度为6 的子序列的2 n 1 上的有禁匹配 均和长为2 n 的不交d y c k 路对的集合之间存在一一对应这三类有禁匹配分 别是3 不交匹配( 避免1 2 3 1 2 3 的匹配) 、3 不嵌套匹配( 避免1 2 3 3 2 1 的匹配) 以及非双嵌套匹配( 避免1 2 3 3 1 2 的匹配) 我们还给出了这三类有禁匹配的计 数公式 本文中关于集合分拆的最重要的结果是引进了一种新的工具：“犹豫杨 表”，并通过它来研究匹配以及分拆上的交叉数与嵌套数。利用集合分拆与 犹豫杨表之间的一个双射，我们证明了如果给定分拆的每个块中的最大和最 小元素，这些分拆的交叉数与嵌套数有对称的交集分布因此对所有的集合 礼】上的分拆以及集合f n = 【2 m 】上的匹配，交叉数与嵌套数也是对称交集分 布的该结论的一个推论就是：女不交分拆( 匹配) 与女不嵌套分拆( 匹配) 的个数相等 在本文的最后我们定义并研究了( k ，m ) 一c a t a l a n 数 c 扯熹( 忡”) ， 它是传统意义的c a t a l a n 数g ( n ) = 击( 哿) 的一个推广。我们还给出了( ，m ) 一c a t a l a n 数的两种组合解释：含有n 个关键点的( ，m ) 一叉树蛆及( m n 十1 ) xk 的“停 车表” 利用( ，m ) 一c a t a l a n 数的这两种组合解释我们给出了它的一些递归关系。 利用这些递归关系我们证明了关于m 叉树以及平面森林的h o o k 长度多项式 的一些公式作为在这些公式的推论，我们还得到了关于m 叉树以及平面森 林上的计数的几个恒等式 关键词：集合分拆，匹配，有禁排列，r n a 二级结构，格路，d y c k 路，m o t z k i n 路，2 一m o t z k i n 路，整数分拆，振荡杨表，犹豫杨表，r s k 算法，k 不交分拆( 匹 配) ，不嵌套分拆( 匹配) ，( k ，m ) 一c a t a l a n 数，( ，m ) 一叉树，( k ，m ) - p a r k i n g t a b l e ，二叉树，m 叉树，平面森林，h o o k 长度多项式 a b s tr a c t 。i 。h i st h e 8 i sc o n c e r n ss e v e r a le n u m e r a t i o nr e s u l t so ns e tp a r t i t i o n s 0 u r 丘r s tr e s u i ti sar e d u c t i o na l g o r i t h mw h i c ht r a n s f o r m s ? n 。r e g u l a rp a r t i t i o n s o ff n j = f l ，2 ，n ) t o ( m 一1 ) 一r e g u 】a rp a r t i t i o n so f n 一1 ，1 肌s h o wt h a tt h i s a l g o r i t h mp r e s e r v e st h en o n c r o s s i n gp r o p e r t y t h i sy i e l d sas i i n p l ee x p l a n a 土i o l lo fa n i d e n t i t yd u et os i m i 。n u 1 1 m a na n dk 1 a z a ri nc o n n e c c i o nw i t he l l u l n e r a n 。np r o b l e m s o nn o n c r o s s i n gp a r t i t i o n sa n dr n as e c o n d a r ys t r u c t u r e sf o ro r d i 工1 a r yn o n c r o s s i n g p a r t i c i o n s ，t h er e d u c t i o na l g o r i t h ml e a u d st oar e p r e s e n c a c i o no fn o n c r o s s i n gp a r t i t i o n s i nt e r m so fj n d e p e n d e n ta r c sa n dl o o p s ，a sw r e a sa ni d e n t i t yo fs i m i o n8 n du l l m a n w h i c he x p r e s s e st h en a r a 弘n an u m b e r si nt e r m so ft h ec a t a l a nn u m b c r s n e x tw ei n t r o d u c el a b e l l i n gs c h e m e sf b rd y c kp a t h sa n d2 一m o t z k i np a t h st h e l a b e l l i n gs c h e m e sf o rd y c kp a t h 8g i v eb 幻e c t i o n sb e t w e e nd y c kp a t h so fi e n g t h2 礼 a n dp e r m u t a t i o n so f 礼】a d i d i n g 下f o re a c h7 - 两，m o r e o v e r ，s o m es t a t i s t i c so n ) y c kp a c l l sa r et r a n s f o r m e dt os t a t j s c i c so np e r m u t a c j o n su n d e r “1 c s eb 玎e c t i o n s t h e l a b e l l i n gs c h e m e sf o r2 一m o t z k i np a t h sp r o v i d ean e wm e t h o dt 。s t u d yr e s t r i c t e dp a r t i t i o n s ，w h i c hc a nb ea p p l i e dt og j v eab i j e c t i o nb e t w e e n2 一r e g u l a rn 6 6 凸一f r e ep a r t i t i o n s o f 孔】a n dc o n n e c t e d 。6 6 0 f r e ep a r t i t i o n so f 礼 ( 2 一m o t z k i np a t h so fl e n g t hn 一2 ) t h e nw eb e g i nt oe n u m e r a t e3 一n o n c r o s s i n g ( o re v e n 角一n 0 1 1 c 1 0 s s i l l g ) m a t c h i n g s ( p a r t i t l o n s ) t h ep r o b l e mo fe n u m e r a t i n g3 一n o n c r o s s i n gm a l c h 儿1 9 s ( 1 2 3 1 2 3 一a v o i d i n g m a t c h i n g s ) w a sr e c e n t l yr a i s e db yk l a z a ra st h ef i r s tu n s o l v e dc a s eo fam o r eg e n e r a l p r o b l e mo fe n u m e r a t i n g 七一n o n c r 0 8 s i n gp a r t i t i o n s 、 毛s h o wt h a ta 1 1t h ef 0 1 l o w i n gt h r e e c l a s s e so fm a t c h i n g sw i t hf o r b i d d e np a t t e r n sa r ei no n e t o - o n ec o r r e s p o n d e n c ew i t h p a i r so fd y c kp a t h sw i t ht h es a m eo r i g i na n dt h es a m ed e s t i n a t i o n ： 3 一n o 【l c r o s s i n g m a t c h i n g s ( 1 2 3 1 2 3 一a v 。i d i n gm a t c h i n g s ) ，3 一n o n n e s t i n gm a t c h i n g s ( 1 2 3 3 2 1 一a v o i d i n g m a t c h i i l g s ) a n dn o n d o u b l e n e s t i n gm a t c h i n g s ( 1 2 3 3 1 2 一a o i d i n gm a t c h l n g s ) t h ee n u m e r a t i o no f3 一n o n n e s t j n gi n a t c h i n g si ss o 】v e db yg o u y o u b e a u c h a j n p s f i n a l l yw ei n t r o d u c ean e wt o o l ，v a c i l l a t i n gt a b l e a u xt os t u d vt 1 1 ee n u m e r a t i o no f c r o s s i n g sa n dn e s l i n g sf o rm a t c h i n g sa n ds e tp a r t i t i o n s u s i n gab u e c t i o nb e t w e e n p a r t i t l o n sa n dv a c i l l a t i n gt a b l e a u x ，、v es h o wt h a ti fw e 疗xt h es e t so f1 n i l l i n l a lb l o c k e l e m e n t sa n d1t l a x i m a lb l o c ke l e m e n t s ，t h ec r o s s i n gn l i m h e ra n d “1 c1 1 e s t l l l gn l l l t l b e r o fp a r t i t i o n sh a v eas y m m e t r i cj o i n td i s t r i b u t i o n i tf o l l ( ) w st 1 1 a tt h ec r o s s i n gn u m b e r s a n dt h en e s t i n gn u m b e r sa r ed i s tr i b u t e ds y m m e r i c a 儿yo v e ra j 】p a r t i t i o n so f n j ，a s w e l la so v e ra 1 1m a t c h i n g so nh j = 2 m a 8ac o r o l l a r y ft h en u m b e r 。f 七一n o n c r o s s i n g p a r t i t i o n si se q u a lt ot h en u m b e ro f 七一n o n n e s t i n gp a r t l t i o n s 1 1 h es a m el sa l s ot r u e f b rm a t c h i n g s a na p p l i c a t i o ni 8g i v e nt ot h ee n u n l e r a t i o no fit l a c c i l i n g sw i t hn o 七一c r o s s i n g ( o rw i t hn o 七n e s t i n g ) i nt h el a s tc h a p t e rw ed e 6 n ea n ds t u d yt h e ( 七，n q ) 一c a t a l a nn u l l l b e r 吼，竹1 ( 礼) = ；再b ( m 等1 七) ，w h i c h i sag e n e r a l i z a t i o no ft h ec a t a l a nn u m b e rg ( n ) = 击( ：) ， a n dg i v et w oc 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 sf o rt h i sn u m b e r ： ( 七，m ) 一a r yt r e e sw i t hn c r u c i a lv e r t i c e sa n d ( m 几十1 ) x 七“p a r k i n gt a b l e s ”u s i n gt h e s ei n t e r p r e t a t i o n sw e g l v er e c u r r e n c ef o r m u i a sf o r 晚，m ( n ) w h i c hc a nb ea p p l i e dt op r o v et o r m u l a sf o rt h e h o d k1 e n g t hp o l y n o m i a l sf o rm a 。yt r e e 8a n dp l a n ef o r e s t s k e y w o r d s ： p a r t m o no fs e t s ，m a t c h i n g ，p e r m u t a t i o nw i t h f o r b i d d e np a t t e r n s ， r n as e c o n d a r ys t r u c t u r e ，l a t t i c ep a t h ，d y c kp a t h ，m o t z k i np a t h ，2 一m o t z k i np a t h ， p a r t i t i o no fi n t e g e r s ，o s c i l i a t i n gt a b l e a u ，v a c i n a t i n gt a b l e a u r s ka i g o r i t h m ，七一 n o n c r o s s i n gp a r t i t i o n ( m a t c h i n g ) ，七一n o n n e s t i n gp a r t i t i o n ( m a t c h i l l g ) ，( 角， 2 ) 一c a t a l a n n u m b e r ，( 七，m ) 一a r yt r e e ，( 七，m ) 一p a rk i n gt a b l e ，b i n a r yt r e e ，一a n tr c c ，p l a l l ef o r e s t ， h o o kl e n g t hp o l y n o m i a l v 8 u 5 8 6 南开大学学位论文版权使用授权书 本人完全了解南开大学关于收集、保存、使用学位论文的规定， 同意如下各项内容：按照学校要求提交学位论文的印刷本和电子版 本：学校有权儇存学位论文的印刷本和电子版，并采用影印、缩印、 扫描、数字化或其它手段保存沦文；学校有权提供目录检索以及提供 本学位论文全文或者部分的阅览服务；学校有权按有关规定向国家有 关部f 1 或者机构送交论文的复印件和电子版；在不以赢琴i 为翻的的前 提下，学校可以适当复制论文的部分或全部内容用于学术活动。 学位论文作者签名：# 砀氤 鹕每f 日 日 经指导教师同意，本学位论文属于保密，在年解密后适用 本授权书。 各密级的最长保密年限及书写格式规定如下 内部5 年( 蠼长5 年，可少于5 年) 秘密1 0 年( 鹾长l o 年，可少于1 0 年) 机密2 0 年( 最长2 0 年，可! 口 2 0 年) 南开大学学位论文原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师指导下，进行研究工作 所取得的成果。除文中已经注明引用的内容外，本学位论文的研究成果不包含 任何他人创作的、已公开发表或者没有公开发表的作品的内容。对本论文所涉 及的研究工作做出贡献的其他个人和集体，均已在文中以明确方式标明。本学 位论文原创性声明的法律责任由本人承担。 学位论文作者签名：4 乙彩霞 力既岁年j 月罗日 i n t r o d u c t i o n i n1 9 7 2 ，g e r m a i nk r e w e r a s 5 4 】i n v e s t i g a t e dn o n c r o s s i n gp a r t i t i o n 8u n d e rt h er e 6 n e m e n to r d e rr e l a t i 。nh i sp a p e rs e tt h es t a g eb o t hf o raw e a l t ho ff u r t h e re n u m e r a t i v e r e s u l t s ，a n df o rn e wc o n n e c t i o n sb e t w e e nn o n c r o s s i n gp a r t i t i o n s ，t h ec o m b i n a t o r i c s o fp a r t i a l l yo r d e r e ds e t s ，a n da l g e b r a i cc o m b i n a t o r i c s n o n c r o s s i n gp a r t n ：i o n s ，a l s oc a l l e d 6 血扯f i e ep a r t i t i o n s ，c a nb ev i e w e da sac l a s s o fs e tp a r t i t i o n sw i t hr e s t r i c t i o n so nt h er e l a t i v ep o s i t i o n i n go ft h eb l o c k s a ss u c h ， t h e ym a yb ec o n s i d e r e d a sr e l a t i v e so fo t h e rc l a s s e so fs e tp a r t i t i o n so c c u r i n gi n t h e1 i t e r a t u r e o n es u c he x a m p i ei st h ec l a s so fn o n n e s t i n g ( 0 6 6 0 一f r e e ) p a r t i t i o n s b o t ht h e s et w oc l a s s e so fs e tp a r t i t i o n sa r o s ei nc o n n e c t i o nw i t hd a v e n p o r t s c h i n z e l s e q u e n c e s w i t ht h i sm o t i v a 土i n ，e x t r e m a lq u e s t i o n sa n de n u m e r a t i o n ( 8 c c o r d i n gt o t h en u m b e ro fb l o c k sa n dam i n i m u md i s t a n c er e q u i r e db e t 、v e e ns u c c e s s i v ee j e m e n t s i nt h es a m eb l o c k ) a r ea d d r e s s e di nf 4 6 ，4 7 1 i nad i f f e r e n td i r e c t i o n ，t h ee n u m e r a t i o no fs e tp a r t i t i o n sa 1 1 0 w e dt oh a v eac o n t r o l l e dn u m b e ro rt y p eo fc r o s s i n g sh a sr e c e i v e da t t e n t i o nf r o ms e v e r a la u t h o r s ，i n c l u d i n gf 9 ，l o ，6 9 ( c 。u n “n gp a r t i t i o n sb yn u m b e ro fc r o s s i n g s ，u s i n gac o u p l e 。fd j 舒b r e n t d e f i n i t i o n sf o rw h a t ( 1 0 n s t i t u t e sac r o s s i n g ) ， 4 3 】( c o u n t i n gm a t c h i n g sb yc r 0 8 s i n g s ) i nt h i st h e s i sw ep r o v i d es o m ee n u m e r a c i o nr e s u l t so ns e tp a r t i l i o n sc o n c e r n i n g m r e g u l a rn o n c r o s s i n gp a r t i t i o n s ，2 r e g u l a rn o n n e s t i n gp a r t l t l o l l s ，a n d 七一n o n c r o s s i n g ( 七一n o n n e s t i n g ) m a t c h i n g sa n dp a r t i t i o n s i nc h a p t e r2w eg i v ear e d u c t i o na l g o r i t h mw h i c ht r a n s f o r m sm r e g u l a rp a r t i t i o n s o f 【n 】= 1 ，2 ，礼 t o ( m 一1 ) 一r e g u l a rp a r t i t i o n so f 扎一l 】w es h o wt h a tt h i s a l g o r i t h mp r e s e r v e st h en o n c r o s s i n gp r o p e r t ft h i sy i e l d sas i m p l ee x p l a n a t i o no fa n i d e n t i t yd u et os i m i o n u 1 l m a na n dk l a z a ri nc o n n e c t i o nw i t he n u m e r a t i o np r o b l e m s o nn o n c r o s s i n gp a r t i t i o n sa n dr n as e c o n d a r ys t r u c t u r e s f o ro r d i n a r yn o n c r o s s i n g p a r t i t i o n s ，t h er e d u c t i o na l g o r i t h ml e a d st oar e p r e s e n t a t i o no fn o n c r o s s i n gp a r t i t i o n s i nt e r m so fi n d e p e n d e n ta r c sa n dl o o p s ，a sw e l la sa ni d e n t i t yo fs i m i o na n du l l m a n w h i c he x p r e s s e st h en a r a y a n an u m b e r si nt e r m so ft h ec a t a l a nn u m b e r s n e x ti nc h a p t e r3w ei n t r o d u c el a b e l l i n gs c h e m e sf b rd y c kp a t h sa n d2 一m o t z k i n p a t h s t h el a b e l l i n gs c h e m e sf o rd y c kp a t h sg i v eb i j e c t l 0 1 1 sb c t w e e l l ) y c kp a t h s 2 o fl e n g t h2 na n dp e r m u t a t i o n so f 几】= l ，2 ，n a v o l d l n g 丁f o re a c h7 _ s 3 ， m o r e o v e r ，s o m es t a t i s t i c so n ) y c kp a h sa r et r a n s f o r m e dt os t a c i s “c so np e r m u t a t i o n su n d e rt h e s eb 巧e c t i o n st h e1 a b e l l i n gs c h e m e sf o r2 一m o t z k i np a t h sp r o v i d ea n e wm e t h o dt os t u d yr e s t r i c t e dp a r t i t i o n s ，w h j c hc a nb ea p p n e dt og i v eab 玎e c t i o n b e t w e e n2 ，r e g u l a rn b b n f r e ep a r t i t i o n so fh 】a n dc o n n e c t e do b b o f r e ep a r t i t i 。n so f n l ( 2 一m o t z k i np a t h so f1 e n g t h 他一2 ) i nc h 印t e r4w eb e g i nt oe n u m e r a t e3 一n o n c r o s s i n g ( o re v e 七一n o n c r o s s i n g ) r r l a t c h i n g s ( p a r t i t i o n s ) t h ep r o b k mo fe n u r n e r a t n l g3 一n o n c r o s s i n gm a t c h i n g s ( 1 2 3 1 2 3 一 a o i d i n gm a t c h i n g s ) w a sr e c e n t l yr a i s e db yk 1 a z a ta st h e 丘r s tu n s o l v e dc a s eo fa m o r eg e n e r a lp r o b l e mo fe n u r n e r a t i n g 舡n o r l c r o s s i n gp a r t i t i o n sw es h o wt h a ta 1 1 t h ef o l l o w i n gt h r e ec l a s s e so fm a t c h i n g sw i t hf o r b i d d e np a t t e r n sa r ei no n e t o o n e c o r r e s p o n d e n c ew i t hp a i r so fd y c kp a 七h sw i t hc h es a m eor - i g i na n dt h es a m ed e s t i n a t i o n ：3 一n o n c r o s s i n gm a t c h i n g s ( 1 2 3 1 2 3 一a o i d i n gm a t c h i n g s ) ，3 一n o n n e s t i n gm a t c h i n g s ( 1 2 3 3 2 l a o i d i n gm a t c h i n g s ) ，n o n _ d o u b l e n e s t i n gm a t c h i n g s ( 1 2 3 3 1 2 一a v o i d i n gm a c c h i n g s ) t h ee n u m e r a t i o no f3 一n o n n e s t i n gm a t c h j n g si ss o l v e db yg o u y o u b e a u c h a m p s i nc h a p t e r5 仉r ei n t r o d u c ean e wt 0 0 1 ，v a c 订i a t i n gt a b l e a u xt os t u d yt h ee n u m e r a t i o no fc r o s s i n g sa n dn e s t i n g sf b rm a t c h i n g sa n ds e tp a r t l t i o n s u s l n gab 珀e c t i o n b e t 、v e e np a r t i t i o n sa n dv a c i i l a t i n gt a b l e a u x ，、v es h o wt h a t1 fw e6 xt h es e t so fm i n i m a lb l o c ke l e m e n t sa n dm a x i m a lb l o c ke l e m e n t s lt h ec r o s s i n gn u m b e ra 1 1 dt h en e s t i n g n u m b e ro fp a r t l t i o n sh a v eas y m m e t r i cj o i n td i s t r i b u c i o n i tf 。l l o w st h a ct h ec r o s s i n g n u m b e r sa n dt h en e s t i n gn u m b e r sa r ed i s t r i b u t e ds y m m e t r i c a l i yo v e ra 1 1p a r t i t i o n s o f 几 ，a sw e l la so v e ra 1 1m a t c h i n g so nm = 【2 m 卜 a sac o r o l l a r y ，l h en u m b e ro f 七一n o n c r o s s i n gp a r t i t i o n si se q u a lt ot h e 肌m b e ro f 七一n o n n e s t l n gp a r t i t i o n s t h es a m e i sa l s ot r u ef o rm a t c h m g s a na p p 王i c a t i o ni s 百v e nt ot h ee n u m e r a t i o no fm a t c h l n g s w i t hn o 七一c r o s s i n g ( o rw i t hn o 七一n e s t i n g ) f i n a l l yi nc h a p t e r6 、v ed e 矗n ea n ds t u d yt h e ( 七，m ) 一c a t a l a nn u m b e r = 熹( 沏n ) ， w h i c hi sag e n e r a l i z a t i o no ft h ec a t a l a nn u m b e rc ( n ) = 击( 翟) ，a n dg i v et w oc o m b i n a t o r i a li n t e r p r e l a t i o n sf o rt h i sn u m b e r ： ( 七，7 n ) 一a r yt r e e sw i t hnc r u c j a lv e r t i c e s a n d ( m 礼十1 ) 七”p a r k i l l gt a b e s ” t h i sg e n e r a l i z a t i o nc o i l l c i d e sc ot h ef j 屺ct h a t ( c o m p l e t e ) b i n a r yt r e e sw i t hni n t e r n a lv e r t i c e sa r ec o u n t e db yc ( n ) a n d ( c o m p l e t e ) 7 n a r yt r e e sw i t h 仡i n t e r n a lv e r t i c e sa r ec o u n t e db y 嘶，= ；( ? 。) = 熹( m ? 1 ) u s l n gt h e s ei n t e r p r e t a t i o n sw eg i v er e c u r r e n c ef o r m u l a sf o r 、m ( n ) w h i c hc a nb e a p p l i e dt op r o v ef o r m u l a s 曲rt h eh o o kl e n g t hp o l y n o n l l a l sf o r7 n a r yt r e e sa n dp l a n e 3 f o r e s t sg i v e na nm a r yt r e e 丁，f o ra n yi n t e r n a lv e r t e xu ，c 1 1 eh 。o 七f e n 夕矾ko f 甜i s d e 矗n e da so n ep l u st h en u m b e ro fi n t e r n a lv e r t i c e sb e l o wu t h es t u d vo ft h eh o o k l e n g t hp o l y n o m i a li sm o t i v a t e db ys e e k i n gas i m p l eb 巧e c t i v ep r o o fo ft h ef o l l o w i n g i d e l l t i t y ： c r 1 r 蠹，筹。辱，( ，+ 去) ，r 死( n )u z ( r ) 、 “7 w h i c hw a s 行r s td e r i v e db yp o s t n i k o vf 6 1 1 ，w h oa l s oa s k e df o rac o m b j n a t o r i a id r o o f o ft h i sl d e n t i t 矿 a sc o n s e q u e n c e so ft h ef o r m u l a sf o rh o o kl e n 昏hp o l y n o m i a i sg i v e ni 1 1t h i sp a p e r ， w ea l s op r o v e dm a n yi d e n t i t i e so nm a r yt r e e sa n dp l a n ef b i e s t s c h a p t e r1 。、 ，1 j1 、1 u e n n l tl o n sa n d l ，r e n m l n a r l e s 1 1p e r m u t a t i o n sa n dp a r t i t i o n s l e t6 nb et h es e to fp e r m u t a t i o n so n 【n ：= l ，2 ，几) ，n 1 w er e g a r da p e r m u t a t i o n7 r 6 na sas e q u e n c eo f 凡e l e m e n t s ：丌= 7 ( 1 ) 7 r ( 2 ) 丌( n ) f b ras e q u e n c e 盯o f 七p o s i t i v ei n t e g e r s ，t h ep 口“e zo r 可p eo f 盯i sd e 矗n e da sa p e r m u l a t i o n7 _ o f 陋1o b t a i n e df r o m 盯b ys u b s t i t u e i n gt h em i n i l l l u me j e m e l l tb yl ，t h e s e c o n dm i n i m u me l e m e n tb y2 ，a n ds oo n n o t et h a ti t i sp o s s i b l ef o ra ni n t e g e rt oa p p e 盯m o r et h a no n c ei nt h ep a t t e r n f b re x a m p l e ，t h ep a t t e r no f6 8 2 5 4i s4 5 1 3 2 ，a n dt h ep a t t e r no f2 5 7 2 4i s1 3 4l 2 d e f i n i t i o n1 1 f b rc w op e r m u t a t i o n s 丁& a n d 丌。兔，、 ，es a yt h a t 丌2 5r a o z d i 礼9 i f t h e r ei sn os u b s e q u e n c e 丌 1 仉2 一丌 t ( i 1 i 2 一 i ) w h o s ep a t t e r nl s7 - w bw r i t e6 n ( r ) f 。rt h es e to f7 _ 一a v o i d i n gp e r m u t a t i o n so f 礼 e x a m p i ei 1 t h ep e r m u t a t i o n7 r = 5l6 273849b e 【o n g st os ( 3 2 i jb e c a u s e a l l i t ss u b s e q u e n c e so fl e n g t h3a r en o to fp a t t e r n3 2 lt h i sp e r l n u t a t i o nd o e