（应用数学专业论文）关于推广的catalan数与类fibonacci数的若干研究.pdf

摘要 摘要 c a t a l a n 序列g = 击( 哿) 在组合数学中出现非常频繁。人们已经发现了差 不多1 0 0 种结构可以由这些数来计数，并且新的能由c a t a l a n 数计数的组合结构 的发现也从未停止。另外，关于c a t a l a n 数的数字特征及性质的研究也广泛存在 于文献资料中。比如，它们之间的各种递推关系，模关系以及因子等等。 在这篇论文紧接着介绍部分的头两章，我们将对推广的c a t a l a n 数 倪，7 ( 竹) = 志( = 7 ) 以及其向量形式的推广做一些研究。我们首先直接从 l a g r a n g e 反演定理推导出一个c a t a l a n 数向量推广形式满足的卷积并给予应用。 接着，我们给出一个染色k 叉树上的对合，并且从这个对合我们证明了一组符 号交替变化的含有推广的c a t a l a n 数及其向量推广形式的恒等式。最后，根据得 到的恒等式和r i o r d a n 阵列理论，我们重新提炼出k 叉树的计数公式和非常漂 亮且重要的g o u l d v a n d e r m o n d e 卷积公式 f i b o n a c c i 序列r 是满足条件兄= r 一1 + r 一2 和f 0 = 0 ，f 1 = l 的序列， 它是组合数学中另一个极为重要的序列。人们发现这些数和自然界有着密切的 联系。在本文最后一章，我们研究一组类f i b o n a c c i 序列g n ，它们满足递推关 系：g n = ( d + 2 ) g n 一1 一g 佗一2 。注意当d = 1 和适当初始条件，我们分别得到 瓯= 易n ，钆 1 和g n = 易n + 1 ，n 0 对这一类序列及其相关性质，我们将用 一类有序树给出组合描述解释。同时，我们还将给出与这类序列相关的组合结 构之间的双射以及研究与其相关的其他序列。 关键词：染色树组合恒等式f i b o n a c c i 数c a t a l a n 数对合r i o r d a n 阵列 卷积公式 一 n 眈瓯虮瓯 n ：l | | 佗 眈 + 虮瓯 a b s t r a c t t h ec a t a l a ns e q u e n c e ( 麓= 赤( 哿) o c c u r su b i q u i t o u s l yi nc o m b i n a t o n c s p e o p l e h a v ef o u n dd b o u to n eh u n d r e dc o m b i n a t o r i a ls t r u c t u r e se n u m e r a t e db yt h e s e 肌m b e r s a n dn e wd i s c o v e r so fs t r u c t u r e sc o u n t e db yt h e m h a v en e v e rc e a s e d f u r t h e r m o r e ，t h e n u m b e rm e o 枷c a lp r o p 耐e s ，s u c ha sr e c u r s i v er e l a t i o n s ，c o n g r u e n c e r e l a t l o n s ，t a c t o r s ， e t c 0 ft h ec 甜a i ln u m b e r sa n d t h e i rg e n e r a l i z a t i o n sh a v ea l s ob e e nw i d e l ys t u d l e dm t h el i t e r a t u r e h lm e 丘r s tt w oc h 印t e r sf o l l o w i n gi n t r o d u c t i o no ft h i st h e s i s ，w ew i l ls t u d y t h e g e n c r a l i z e dc a t a l a nn u m b e r s 瓯，叮( 礼) = 上k n + 7 ( 詹) a n d i t sv e c t o rg e n e r a l i z a t l o mw e f i r s tp r c i v eac o n v o l u t i o no fv a n d e r m o n d et y p es a t i s f i e db yt h ev e c t o rg e n e r a l l z a t l o n o ft h ec a t a l a nn u m b e r sd i r e c t l yf r o ml a g r a n g ei n v e r s i o nf o r m u l a s o m ei n t e r e s t i n g a p p l i c a t i o n sa r e a l s od e v e l o p e dt h e r e n e x t ，w ep r o v eas i g na l t e r n a t i n gc o m b m a t o n a l s u mi n v o l v i n gt h eg e n e r a l i z e d c a t a l a nn u m b e r sb yi n t r o d u c i n g a ni n v o l u t i o no nc o l o r e d 惫a “蜘s f i n a l l y , b a s e do nt h e c o m b i n a t o r i a ls u ma n d r i o r d a na 1 1 r a yt h e o 巧w er e n n e m ef o r m u l ac o u n t i n gt h en u m b e ro fk - a l yt r e e sa n d t h ee l e g a n tg o u l d - v a n d e n n o n d e s c o n v o l u t i o n q m + q 。( 礼) = 瓯肌( t ) 瓯恕n z ) i = 0 t t l ef i b o n a c c is e q u e n c ers a t i s f y i n gr = r 一1 + r 一2 a n df 020 ，f 1 = 1 i sa i l o t h e rs e q u e n c eo fg r e a ti m p o r t a n c e i nc o m b i n a t o r i c s t h e s en u m b e r sh a v eb e e n f o u n dc l o s e l yc o n n e c t i n gt ot h en a t u r a lw o r l d i n t h el a s tc h a p t e r , w ew i l ls t u d ya c l a s s 0 ff i b o n a c c i l i k es e q u e n c e sg 礼s a t i s f y i n g 瓯= ( d + 2 ) 瓯一1 一g 竹一2 n o t e t h a tt h e f i b o n a c c i 聃m b e r sg 礼= 玛竹，佗 1a n dg n = 而礼+ 1 ，n 0 o c c u rw h e nd21 w i t hs u i t a b l ei n i t i a lc o n d i t i o n s w ep r e s e n tag e n e r a li n t e r p r e t a t i o nf o rt h i sc l a s so f s e q u e n c e sa n dt h e i rp r o p e r t i e si nt e r m so fs o m e k i n do fo r d e r e dt r e e s a sw e l l , s o m e b i i e c t i o n sa l n o n gs t r u c t u r e sr e l a t e dt ot h e s en u m b e r sa n d s e v e r a lo t h e rr e l a t e di n t e g e r s e q u e n c e s a lea l s os t u d i e d k e v w o r d s ：c 0 1 0 r e dt r e e s ，c o m b i n a t o r i a li d e n t i t i e s ，f i b o n a c c in u m b e r s ，c a t a l a i ln u m - b e r s i n v o l u t i o n ，r i o r d a na r r a y s ，c o n v o l u t i o n l l 南开大学学位论文版权使用授权书 本人完全了解南开大学关于收集、保存、使用学位论文的规定， 同意如下各项内容：按照学校要求提交学位论文的印刷本和电子版 本；学校有权保存学位论文的印刷本和电子版，并采用影印、缩印、 扫描、数字化或其它手段保存论文；学校有权提供目录检索以及提供 本学位论文全文或者部分的阅览服务；学校有权按有关规定向国家有 关部门或者机构送交论文的复印件和电子版；在不以赢利为目的的前 提下，学校可以适当复制论文的部分或全部内容用于学术活动。 学位论文作者签名：陈小锋 0 08 年5 月p 乡日 经指导教师同意，本学位论文属于保密，在年解密后适用 本授权书。 指导教师签名：学位论文作者签名： 解密时间：年月日 各密级的最长保密年限及书写格式规定如下： 南开大学学位论文原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师指导下，进行 研究工作所取得的成果。除文中已经注明引用的内容外，本学位论文 的研究成果不包含任何他人创作的、已公开发表或者没有公开发表的 作品的内容。对本论文所涉及的研究工作做出贡献的其他个人和集 体，均己在文中以明确方式标明。本学位论文原创性声明的法律责任 由本人承担。 学位论文作者签名：陈夕八锋 b d 黾年5 只29b c h a p t e r1 i n t r o d u c t i o n 1 1g e n e r a l i z e dc a t a l a ns e q u e n c e s t h ec a t a l a ns e q u e n c eg = 击( 哿) o c c u r s u b i q u i t o u s l yi nc o m b i n a t o r i c s p e o p l e h a v ef o u n da b o u to n eh u n d r e dc o m b i n a t o r i a ls t r u c t u r e se n u m e r a t e db yt h e s en u m b e r s s e eg o u l d sc a t a l o g 9 】a n ds t a n l e y sc o l l e c t i o n 2 9 t h et h e s i s 【19 】a l s oc o n t a i n s 31c o m b i n a t o r i a ls t r u c t u r e se n u m e r a t e db yc a t a l a nn u m b e ra n d15 8b i j e c t i o n sa m o n g t h e m h o w e v e r , n e wd i s c o v e r so fs t r u c t u r e sc o u n t e db yt h e mh a v en e v e rc e a s e d t h e r e a r ea l s om a n yg e n e r a l i z a t i o n so ft h ec a t a l a nn u m b e r sa n dt h e i r c o r r e s p o n d i n gc 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 s s e eq - c a t a l a ns e q u e n c e 7 】a n dq ，t - c a t a l a ns e q u e n c e 8 ，1 5 ，2 0 】 a n dr e f e r e n c e st h e r e i n f u r t h e r m o r e ，t h en u m b e rt h e o r e t i c a lp r o p e r t i e s ，s u c ha sr e - c u r s i v er e l a t i o n s ，c o n g r u e n c er e l a t i o n s ，f a c t o r s ，e t c ，o ft h ec a t a l a nn u m b e r sa n dt h e i r g e n e r a l i z a t i o n sh a v ea l s ob e e nw i d e l ys t u d i e di nt h el i t e r a t u r e 【6 , 8 ，1 5 ，1 6 ，2 0 ，2 3 i nt h ef i r s tt w oc h a p t e r sf o l l o w i n gt h i si n t r o d u c t i o n ，w ew i l ls t u d yt h eg e n e r a l i z e d c a t a l a nn u m b e r sg ，7 ( 几) = 南( 七= 7 ) a n di t sv e c t o rg e n e r a l i z a t i o nq ( 亿；p ；7 ) t h e v e c t o rg e n e r a l i z a t i o nq ( 扎；p ；7 ) i sd e f i n e da s q ( 佗；p ；7 ) = 佗p + 7( ，n ：t 善艺p i1 h ) ， m - ， 几1 ，他( 一) + ，y 、“叫 w h e r et h en o t a t i o n si n v o l v e dm e e tf o l l o w i n ge x p l a n a t i o n s ： f o ra n yv e c t o r sa = ( a l ，a t ) a n db = ( b l ，6 t ) ，w ed e f i n eb a = ( b 1 一 a l ，玩一吼) a n da b = ：1a k b k ；a su s u a l ，a n yd i m e n s i o nv e c t o rw i t hc o n s t a n t e n t r i e sk sw i l lb ed e n o t e db ykf o rs h o r ti ft h e r ei sn oc o n f u s i o n ；w ea l s od e n o t ea b i fa i b if o ra l l1 i 亡；f o rx c ，：1m i = za n dm l ，m t 一1 n ，w e i n t e r p r e tt h eg e n e r a lm u l t i n o m i a lc o e f f i c i e n ta sf o l l o w s ： ( m ，二。一，m 。) = ( 主。) ( z ：了1 ) ( z m 1 ：二j m 卜2 ) ， w h e r e ( ：) = 坐业掣f o rk n + a n d ( ：) = 1 a n di n t h i st h e s i s ，u n l e s s s p e c i f i e da 1 1n u m b e r sa l et r e a t e da si n t e g e r s 1 c h a p t e r1 i n t r o d u c t i o n w ef i r s td e d u c eac o n v o l u t i o no fv a n d e r m o n d e t y p es a t i s f i e db yq ( n ；p ；7 ) d i r e c t l y f r o m l a g r a n g ei n v e r s i o nf o r m u l a t h i sc o n v o l u t i o ns t a t e s q ( 佗；p ；q 1 + 0 1 2 ) =q ( 主；p ；a x ) q ( n 一主；p ；q 2 ) ( 1 2 ) o 0o c c u rw h e nd = 1w i t hs u i t a b l e i n i t i a lc o n d i t i o n s w ep r e s e n tag e n e r a li n t e r p r e t a t i o nf o rt h i sc l a s so fs e q u e n c e sa n d t h e i rp r o p e r t i e si nt e r m so fs o m ek i n do fo r d e r e dt r e e s w ep r e s e n tb i j e c t i o n sb e t w e e n l a t t i c ep a t h s ，f i l i n g sa n dt h e s eo r d e r e dt r e e sa sw e l l f u r t h e r m o r e ，s e v e r a lo t h e rr e l a t e d i n t e g e rs e q u e n c e sa r ea l s os t u d i e d 3 c h a p t e r2c o n v o l u t i o n ( 1 2 ) a n dc o u n t i n go r d e r e dt r e e s c h a p t e r2c o n v o l u t i o n ( 1 2 ) a n dc o u n t i n go r d e r e dt r e e s 2 1n o t a t i o n sa n dl a g r a n g ei n v e r s i o nf o r m u l a aw e a kc o m p o s i t i o no fan o n n e g a t i v ei n t e g e r 礼i n t okp a r t si sa no r d e r e d 南t u p l e o fn o n n e g a t i v ei n t e g e r s ，s a y ( 8 1 ，s ) ，w h o s es u mi sna n di su s u a l l yw r i t t e na s s 1 + + s k = n s u p p o s ea ( x ) = a l x + a 2 x 2 + ，f ( x ) = a x + a x 2 + z k z 】 ， w h e r ek m 】d e n o t e st h es e to ff o r m a lp o w e rs e r i e so v e raf i e l dkw i t hc h a r k = 0 u s u a l l y , i fa ( f ( x ) ) = zo r 厂( a ( z ) ) = z ，w es a yt h a ta ( x ) a n df ( x ) a r ec o m p o s i t i o n a l i n v e r s e st oe a c ho t h e r w ed e n o t et h ec o m p o s i t i o n a li n v e r s eo ff ( x ) b yf ( z ) i t i sw e l lk n o w nt h a tf ( x ) h a sac o m p o s i t i o n a li n v e r s ei fa n do n l yi f 0 t h ef a m o u s l a g r a n g ei n v e r s i o nf o r m u l as u p p l i e sas y s t e m a t i cm e t h o dt oc a l c u l a t et h ec o e f f i c i e n t so f t h ec o m p o s i t i o n a li n v e r s eo fag i v e nf o r m a lp o w e rs e r i e s ( i fi th a s ) a su s u a l ， z n 九( z ) d e n o t e st h ec o e f f i c i e n th ni nt h ee x p a n s i o nh ( x ) = nh n x 竹 t h e o r e m2 1 1 ( l a g r a n g ei n v e r s i o nf o r m u l a 【2 9 】) l e tf ( x ) = z + 如z 2 + z j r z 1 】，w h e r e 0f a n dc h a r k = o j ，a n d l e tk ，佗z t h e n 州扩i f “ ( z ) 惫= k x 心】( 南) 死= k x - k f ( z ) 一 ( 2 1 ) c o r o l l a r y2 1 2 ( 【2 9 】) p r e s e r v et h en o t a t i o ni nt h et h e o r e m2 j j f o ra n yp o w e r s e r i e sh ( x ) k 捌】w eh a v e n i x 佗】日( 厂 ( z ) )= x n - 1 h 钕) ( 南) n ( 2 2 ) p r o o f b yl i n e a r i t y ( f o ri n f i n i t el i n e a rc o m b i n a t i o n s ) i ts u f f i c e st op r o v eh ( x 、= z 七 b u tt h i si se q u i v a l e n tt oe q u a t i o n ( 2 1 ) _ c o r o l l a r y2 1 3 l e tl ( x ) b ea f o r m a ll a u r e n t s e r i e sc o n t a i n i n go n l ya f i n i t en u m b e r o f n e g a t i v ep o w e r so f x ，a n dl e tf ( x ) b ea f o r m a lp o w e r s e r i e sw i t h o u tc o n s t a n tt e r m s 驴w ee x p a n dl ( x ) i np o w e r so f j p ( z ) ， l ( z ) = c n ，( z ) n ， 4 c h a p t e r2c o n v o l u t i o n ( 1 2 ) a n dc o u n t i n go r d e r e dt r e e s t h e n , t h ec o e f f i c i e n t sc na r eg i v e nb y p r o o f s i n c ea n = 扩 n f r o mt h ec o r o l l a r y2 1 2 = 烈1x - 1 m z ) m ) 一 ( 2 3 ) a n f ( f ( z ) ) n = z 住 l ( 厂 ( z ) ) ，t h ep r o o ff o l l o w s 2 2d e d u c t i o no f ( 1 2 ) f r o ml a g r a n g ei n v e r s i o nf o r m u l a l a p p l y i n gt h el a g r a n g ei n v e r s i o nf o r m u l a ，w ee a s i l yo b t a i nt h ef o l l o w i n gp r o p e r t y o ff o r m a lp o w e rs e r i e s p r o p o s i t i o n2 2 1 s u p p o s ea ( x ) = a o + a l x + a 2 x 2 + a n da o 0 t h e n ，f o ， 礼k l + k 2 1 ， 半 x n - a l - k 2 a ( z ) n ： 礼 8 1 + s 2 = n - - 2 k li x s l + l - k l 】a ( z ) 8 l + 1 k 2x s 2 + l - k 2 a ( z ) 8 2 + 1 ( 8 1 + 1 ) ( s 2 + 1 ) ( 2 4 ) w h e r et h es u mi so v e ra l lw e a kc o m p o s i t i o n so f n 2i n t ot w o p a r t s p r o o f s e ta o ( x ) = x a ( x ) f r o ml a g r a n g ei n v e r s i o nf o r m u l a ，w eh a v e n x 札】a 手- - 1 ( z ) h + 幻= 佗 矿1 烯彤( z ) 七1x 8 2 k 彤( z ) 知2 k l x 8 l + l - k 1 ( z 4 0 ( z ) ) 8 ，+ 1k 2x s 2 + l - k 2 ( x a o ( z ) ) 8 2 + 1 s 1 + 1s 2 + 1 k l x 8 ，+ 1 一七一】( a ( z ) ) 8 z + 1k 2 x s 2 + l - k 2 】( 4 ( z ) ) 8 。+ 1 s 1 + 1s 2 + 1 = ( k 1 + k 2 ) i x n 一七- 一七z ( x a o ( z ) ) n = ( k 1 + k 2 x n - k l - k 2 a ( z ) n t h i sc o m p l e t e st h ep r o o f - l e m m a2 2 2 t h en u m b e ro f w e a k c o m p o s i t i o n so f n i t l + + n k t ki n t on ip a r t so f t i f o r1 i ki s ( n 嘉? ) w en o t et h a tt h ee x p a n s i o n so fb o t hs i d e so fe q u a t i o n ( 2 4 ) a r em u l t i n o m i a l so ft h e f o r m u a o t o , t l l ， 5 扩翁冒 斗0 斗 斗 他 仃 = = w h e r et i ss a t i s f y i 0 t 产n ，i t 产礼一k 1 一忌2 t 0 h e n c e ，f o rf i x e dt o ，t a ，t h er e s p e c t i v ec o e f f i c i e n t so ft h et e r ma t o o a t l o nb o t h s i d e sm u s tb ee q u a l t h e r e f o r e ，e q u a t i o n ( 2 4 ) i sj u s ta l li m p l i c i tf o r mo fa s y s t e mo f c o m b i n a t o r i a li d e n t i t i e s b a s e do nt h i sf a c t ，w eo b m i nt h ef o l l o w i n gv a n d e r m o n d e t y p e c o n v o l u t i o ns a t i s f i e db yq ( 钆；p ；7 ) t h e o r e m2 2 3 f o r 佗= ( n l ，n t ) o ，p = ( p l ，p t ) 0 ，t 1a n d q 1 ，q 2 c ，t h e r eh o l d s q ( n ；p ；a 1 + q 2 ) = ：q ( 主；p ；a 1 ) q ( n i ；p ；q 2 ) ( 2 5 ) o 1 ) a n dt h es e to f f o r e s t sw i t hu n m a r k e dr o o t so fns m a l ll a b e l e dk - a r yt r e e so n ( 忌+ 1 ) n 】i nw h i c hk n + 2 ，( 七+ 1 ) na r em a r k e dv e r t i c e s e q u i v a l e n t l y , t h en u m b e r o f k - a r yt r e e so f n ( n 1 ) i n t e r n a lv e r t i c e si s 丽1 ( 七= 1 ) p r o o f l e tt b ea n yl a b e l e dk - a r yf l e e so n k n + 1 c o n s i d e rt h es m a l ll a b e l e dk - a r y t r e ed e c o m p o s i t i o n ：t h e r ea l e ( 惫= 1 ) w a y st oc h o o s et h eu n m a r k e dr o o t so fs m a l lk - a r y 9 t r e e sa n d ( 恐礼) ! w a y st oa r r a n g et h er e m a i n i n gk nv e r t i c e s t h u s ，t h en u m b e ro f l a b e l e d k - a r yt r e e so fn i n t e r n a lv e r t i c e si s ( 七= 1 ) ( 七佗) ! d i v i d i n gt h i sn u m b e rb y ( 扎+ 1 ) ! w i l l c o m p l e t et h ep r o o f i c o r o l l a r y2 3 3 t h en u m b e ro f o r d e r e df o r e s t so fk a r yt r e e sw i t ht o t a l l y 佗i n t e r n a l v e r t i c e sa n d y 七一a r yt r e e si s k n + 7 ( 南宁) p r o o fb y i n d u c t i o no n7a n dt h eg o u l d - v a n d e r m o n d e sc o n v o l u t i o nt h ep r o o f f o l l o w s c o r o l l a r y2 3 4 t h en u m b e ro f o r d e r e dt r e e sw i t h7 2 ii n t e r n a lv e r t i c e so fo u t d e g r e ep i 坫 q i i n ；p ；1 ) ：击( ，n p + 1 l np + 鼎) q i ) 2 南l ，1 一；：。码j p r o o f l e tt b ea n ys u c hal a b e l e do r d e r e dt r e e f o l l o w i n gc h e n sd e c o m p o s i n ga l g o r i t h m tc o r r e s p o n dt oaf o r e s tw i t hn is m a l ll a b e l e dp i a r yf l e e sw i t hu n m a r k e d r o o t s t h e r e a r e ( m + n p + 帆1 ) w a y st oc h o o s e t h er o o t sa n d ( 佗p ) ! ( 篙意2 ) w a y st oa r r a n g et h e r e m a i n i n gv e r t i c e s d i v i d i n gt h eo b t a i n e d n u m b e ro fl a b e l e ds u c hf l e e sb y 。p + 1 ) ! w i l lc o m p l e t et h ep r o o f i c o r o l l a r y2 3 5 t h en u m b e ro fo r d e r e d f o r e s t sw i t ht o t a l l