（应用数学专业论文）fine格路和有禁错排.pdf

大连理工大学硕士学位论文 摘要 随着计算机科学技术的发展，组合数学的重要性日渐凸显许多理论学科和应用学 科向组合数学提出了大量的具有理论和实际意义的课题，促使组合数学产生了许多新理 论，如组合优化，组合算法等而组合计数理论是组合数学中一个最基本的研究方向，许 多理论研究和实际模型的建立都是以此为基础组合数学中有很多重要的组合数，例如 f i b o n a c c i 数，c a t a l a n 数，m o t z k i n 数和s c h r s d e r 数人们对这些组合数的研究已经很 成熟，其中研究最多的是c a t a l a n 数c a t a l a n 数和一些重要的组合对象，如格路，有序 树，y o u n g 表等密切相关，人们在研究c a t a l a n 数的时候主要基于c a t a l a n 数和格路的关 系计算机科学技术的发展丰富了算法的理论知识，而排序是算法的重要内容排序和 重要的组合对象有着紧密的联系，比如人们最初用有禁排列研究排序的一些性质。随着 有禁排列研究的深入，人们发现3 长的有禁排列的计数是c a t a l a n 数后来人们用几种 不同的方法研究c a t a l a n 数和有禁排列的关系。本文建立在c a t a l a n 数的基础上，研究一 种新的组合数即f i n e 数f i n e 数有很多重要的性质，本文的主要成果有： 1 在第二章，根据f i n e 数和c a t a l a n 数之间的关系，对f i n e 数的定义和性质给予归 纳总结，同时研究了f i n e 数的一些重要的恒等式和f i n e 数的一些组合解释。并且对这些 恒等式用发生函数的方法给予证明，对这些组合解释通过建立一一对应给予证明。 2 在第三章，对有禁排列和错排的定义及性质给予归纳总结，同时证明了错排的两 个重要的恒等式此外，本章给出两个算法，即标准约合分解法和标号法，并分别用这 两个算法建立f i n e 格路和避免3 2 1 模式的错排之间的双射，同时得到了避免3 2 1 模式的 错排的一些统计量的性质 关键词：f i n e 格路；f i n e 数；有禁排列；错排；标准约合分解 1 f i n e 格路和有禁错排 f i n ep a t h sa n dr e s t r i c t e dd e r a n g e m e n t s a b s tr a c t 、矾t ht h ed e v e l o p m e n to fc o m p u t e rs c i e n c ea n dt e c h n o l o g y , t h ei m p o r t a n c eo fc o m b i n a t o - r i a lm a t h e m a t i c sb e c o m em o r ec l e a r l y m a n yt h e o r ys u b j e c t sa n da p p l i e ds u b j e c t sp r o p o s e da l a r g en u m b e ro ft h e o r e t i c a la n dp r a c t i c a lp r o b l e m s ，w h i c hp r o m o t e dc o m b i n a t o r i a lm a t h e m a t i c s p r o d u c em a n yn e wt h e o r y , f o re x a m p l e ，c o m b i n a t o r i a lo p t i m i z a t i o n ，c o m b i n a t o r i a la l g o r i t h m a n ds oo n h o w e v e r ，c o m b i n a t o r i a lc o u n t i n gt h e o r yi st h em o s tb a s i sa s p e c to fc o m b i n a t o r i a l m a t h e m a t i c s ，m a n yt h e o r yr e s e a r c ha n dp r a c t i c a lm o d e lb a s e do ni t c o m b i n a t o r i a lm a t h e - m a t i c si n c l u d e sm a n yi m p o r t a n c ec o m b i n a t o r i a ln u m b e r s ，s u c ha st h ef i b o n a c c in u m b e r s ，t h e c a t a l a nn u m b e r s ，t h em o t z k i nn u m b e r sa n dt h es c h r s d e rn u m b e r s t h er e s e a r c ho nt h e s en u m - b e r sa r em a t u r ea n dm o s tp e o p l ed or e s e a r c ho nt h ec a t a l a nn u m b e r s t h e r ea r ec l o s el i n k s b e t w e e nt h ec a t a l a nn u m b e r sa n dl a t t i c ep a t h s ，l a b e l e dt r e e s ，t a b l e a u xa n ds oo n p e o p l ed o r e s e a r c ho nt h i sa s p e c tm a i n l yb a s eo nt h er e l a t i o nb e t w e e nt h ec a t a l a nn u m b e r sa n dl a t t i c e p a t h s t h ed e v e l o p m e n to fc o m p u t e rs c i e n c ea n dt e c h n o l o g ye n r i c hk n o w l e d g eo fa l g o r i t h m s t h e o r y , a n ds o r ti sa ni m p o r t a n ta s p e c to fa l g o r i t h m s t h e r ea r ec l o s el i n k sb e t w e e ns o r ta n d c o m b i n a t o r i a lo b j e c t s ，f o re x a m p l e ，p e o p l ef i r s tu s e dr e s t r i c t e dp e r m u t a t i o ns t u d ys o r t w i t h t h ed e v e l o p m e n to fr e s e a r c h ，p e o p l ed i s c o v e r e dt h ec o u n to f3 2 1 - a v o i d i n gp e r m u t a t i o ni st h e c a t a l a nn u m b e r s t h i sp a p e rb a s eo nt h ec a t a l a nn u m b e r sa n du s et w om e t h o d st oe s t a b l i s h t h eb i j e c t i o n sb e t w e e nf i n ep a t h sa n dr e s t r i c t e dd e r a n g e m e n t 1 i nc h a p t e r2 ，w eb a s eo nt h er e l a t i o nb e t w e e nt h ef i n en u m b e r sa n dt h ec a t a l a nn u m b e r s ， s ow es u m m a r yt h ed e f i n i t i o na n dp r o p e r t i e so ft h ef i n en u m b e r s f u r t h e r m o r e ，w ep r o v es o m e i d e n t i t i e sa n dc o m b i n a t o r i a le x p l a n a t i o no ft h ef i n en u m b e r s w eu s eg e n e r a t i n gf u n c t i o nt o p r o v et h ei d e n t i t i e s ，a n de s t a b l i s hs e v e r a lb i j e c t i o n sf o rt h ef i n en u m b e r s 2 i nd m p t e r3 w es u m m a r yt h ed e f i n i t i o na n dp r o p e r t i e so fr e s t r i c t e dp e r m u t a t i o n sa n d d e r a n g e m e n t s ，a tt h es a t n et i m e ，w ep r o v et w oi n d e n t i t i e so fd e r a n g e m e n t f u r t h e r m o r e ，w e i n t r o d u c et w oa l g o r i t h m so fc a n o n i c a lr e d u c e dd e c o m p o s i t i o na n dl a b e l l i n gs c h e m e s ，a n dw eu s e t h e s et w oa l g o r i t h m se s t a b l i s ht h eb i j e c t i o u sb e t w e e nf i n ep a t h sa n d3 2 1 一a v o i d i n gd e r a n g e m e n t s r e s p e c t i v e l y , a n dw eo b t a i ns o m ep r o p e r t i e so f3 2 1 - a v o i d i n gd e r a n g e m e n t s k e y w o r d s ：f i n ep a t h s ；f i n en u m b e r s ；r e s t r i c t e dp e r m u t a t i o n s ；d e r a n g e m e n t s ；c a n o n i c a l r e d u c e dd e c o m p o s i t i o n i i 大连理工大学学位论文独创性声明 作者郑重声明：本硕士学位论文是我个人在导师指导下进行的研究工作 及取得研究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文 中不包含其他人已经发表或撰写的研究成果，也不包含为获得大连理工大学 或者其他单位的学位或证书所使用过的材料。与我一同工作的同志对本研究 所做的贡献均已在论文中做了明确的说明并表示了谢意。 若有不实之处，本人愿意承担相关法律责任。 学位论文题目：亟! 呈堡堕空查翌丝垫 作者签名：嫠鱼拯 e l 期：丝9 l 年鱼月羔生e l f i n e 格路和有禁错排 大连理工大学学位论文版权使用授权书 本人完全了解学校有关学位论文知识产权的规定，在校攻读学位期间论 文工作的知识产权属于大连理工大学，允许论文被查阅和借阅。学校有权保 留论文并向国家有关部门或机构送交论文的复印件和电子版，可以将本学位 论文的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印、或 扫描等复制手段保存和汇编本学位论文。 学位论文题目：臼堕皇整蹬袒匀基篁蠢童! 作者签名：嫠擅 日期：丝1 2年鱼月皇竺日 导师签名：j 铲年一日期毕年丘月牟日 大连理工大学硕士学位论文 1 绪论 1 1 组合序列的研究背景 电子计算机的出现改变了整个世界的面貌，它的出现使各种难题得以解决，同时也 萌生了更多的相关理论问题在这种影响下，组合数学迅速发展起来组合数学是算法 的理论基础，计算机科学就是算法的科学计算机的核心内容就是使用算法处理离散的 数据，所以随着计算机技术的发展，组合数学变得日益重要 组合数学不仅和计算机联系紧密，组合数学还应用在很多领域比如组合数学在编 码学，生物数学，交通规划和经济领域都有着重要的应用在我们的日常生活中也有各种 各样的组合数学问题如生产线上的调度和安排，集装箱问题，交通运输路线的选择， 路面的设置，以及著名的邮递员问题这些问题都是考虑经过怎样的设计才能使整个布 局最合理或经济上达到最节约所以组合数学几乎无处不在，它可以称为一门应用学科， 一门交叉学科 组合数学广义的概念是指离散数学，它研究的内容是离散的数据有时人们把狭义 的组合数学，图论，代数结构，数理逻辑等总称为离散数学但是它们的实质都是一样 的，都说明组合数学是一门研究离散对象的科学组合数学狭义的概念是指组合数学是 一门研究满足一定条件的组合模型的存在，计数以及构造等方面的学科组合数学的主 要内容包括：组合计数，组合优化，组合算法，组合矩阵等 组合计数理论是组合数学的一个最基本的研究方向，组合数学的很多知识都是建立 在组合计数理论的基础上组合数学中有很多重要的组合序列，例如f i b o n a c c i 序列， c a t a l a n 序列，m o t z k i n 序列，s c h r b e r 序列。f i b o n a c c i 序列起源于经典的”兔子问题”， 很多人对f i b o n a c c i 序列做了研究，k n o p f m a c h e r 在文献【l 】中用树的知识研究了f i b o n a c c i 序列的递推关系式b e n j a m i n 在文献【2 】中用组合的方法证明了f i b o n a c c i 序列的一些恒 等式c a t a l a n 序列是组合数学中一个非常重要的组合序列，关于c a t a l a n 序列这一方面 的文献很多，比如s t a n l e y 在他的计数组合学书中给出了c a t a l a n 序列的六十多种组合解 释许多问题都可以使用c a t a l a n 数计数，如格路，平面树，二叉树等b e r n h a x t 在文献 3 1 中综述了c a t a l a n 序列，m o t z k i n 序列的组合结构，递推关系式，发生函数和拉格朗日 反演d e u t s c h 在文献【4 】中用二项式系数证明了c a t a l a n 序列和m o t z k i n 序列满足的关 系式k r e m e r 在文献 1 0 1 中给出1 0 种有禁排列都可以用s c h r s d e r 序列来计数，它主要 1 f i n e 格路和有禁错排 利用生成树的思想 本文研究的对象是f i n e 数，f i n e 数起源于相似关系，它满足自反性，对称性这种 相似关系的实质是用格路来研究带有某些附加条件的c a t a l a n 数f i n e 数方面的文献还 不是很多，d e u t s c h 在文献【2 8 】中介绍了f i n e 数的定义，递推关系式，发生函数和一些重 要的恒等式。m a n s o u r 和d e n g 在文献f 2 2 】中用标准约合分解的方法研究了d y c k 格路和 有禁排列的关系，从而得到了d y c k 格路的一些统计量，其中d y c k 格路对应的排列中不 含固定点的排列的计数是f i n e 数 1 2 有禁排列和有禁错排的研究概况 人们对有禁排列问题的研究开始于2 0 世纪6 0 年代，k n u t h 介绍了栈的排序问题， 它为排列问题的研究奠定了良好的基础但是直到2 0 世纪9 0 年代才开始了有禁排列这 一领域的改进性的工作 对于一些简单问题的计数比如避免3 长的和避免4 长的排列，b o n a 在它的书中都 给出了结果像最简单的避免3 长的排列，它的计数为c a t a l a n 数 随着有禁排列问题的研究的深入，人们开始研究避免一种以上模式的排列例如， a l b e r t ，a t k i n s o n ，h a n d l e y 和h o l t o n 在文献【7 1 中研究了避免多种模式的3 长的排列。 a t k i n s o n 在文献【8 l 中研究了同时避免两种模式的排列，一种是避免3 长的和另一种是避 免4 长的排列s t a n k o v a 在文献【1 6 】中和k r e m e r 在文献【1 0 】中研究了同时避免多种模式 的4 长的排列k r a t t e n t h a l e r 在文献f 6 】，m a n s o u r 和v a i n s h t e i n 在文献1 2 2 】中研究了同时 避免3 长的和k 长的排列 同时，人们又想到研究有禁排列的另外一种形式，即研究一个排列中既包含一种模 式又避免一种模式的排列k r a t t e n t h a l e r 在文献【引，m a n 8 0 u r 和v a i n s h t e i n 在文献【2 2 】中 研究了同时避免3 长的排列和包含r 个某种模式的k 长的排列 我们在前面提到有禁排列和组合数学中一些重要的组合对象有非常紧密的联系，所 以人们就展开了这一方面的研究其中有禁排列和格路之间的一一对应关系就是其中之 一s i m i o n 和s c h m i d t 在文献【1 2 】和w e s t 在文献【13 】中研究了避免3 长的排列的计数等 于c a t a l a n 数。w e s t 在文献【1 3 】和s t a n k o v a 在文献【1 6 j 中研究了避免4 长的排列和格路 之间的双射，并且发现同时避免3 1 4 2 和2 4 1 3 的计数等于s c h r s d e r 数 利用生成树的思想，k r e m e r 在文献1 1 0 中给出1 0 种有禁排列都可以用s c h r & t e r 数 计数f l a j o l e t 在参考文献【1 0 】中把格路的一些统计量用第二类切比雪夫多项式和连分数 表示 关于有禁排列和格路之间的双射关系，已经有很多人在这方面做了研究，因为把有 禁排列中的一些统计量映射到格路上让人们能够更加容易理解这些统计量。之前人们使 用最多的方法就是e c o 方法，这种方法表明有禁排列的一些统计量和格路有同样的生成 树，这方面的知识可以参考 1 5 , 2 0 1 ，从而证明了它们之间存在双射但是这种方法不能建 2 大连理工大学硕士学位论文 立有禁排列和格路之间的直接双射 随着研究的进一步深入，有禁排列和格路之间的一一对应关系又有了新的证明方法 在文献【2 2 】中，m a n s o u r 和d e n g 用标准约合分解的方法建立了d y c k 格路和避免3 2 1 模 式的排列之间的一一对应同时c h e l a 和d e n g 和y a n g 在文献【2 3 】中也用标准分解的理 论建立了r i o r d a n 路径和同时避免3 2 1 ，3 1 4 2 模式的错排之间的一一对应 本文主要研究f i n e 数的性质，给出关于f i n e 数的一些重要的恒等式和组合解释， 用发生函数的方法证明了这些恒等式，同时用建立双射的方法证明了这些组合解释由 于c a t a l a n 数是d y c k 格路的计数，用标准约合分解和标号的方法建立d y c k 格路和有禁 排列的双射已经完成所以本文在d y c k 格路的基础上在第三章借助标准约合分解理论 和标号的方法，研究f i n e 格路从而建立f i n e 格路和错排之间的双射，得到f i n e 数就 是d n ( 3 2 1 ) 的计数 3 f i n e 格路和有禁错排 2f i n e 数 2 1c a t a l a n 数的基本概念和性质 c a t a l a n 数在组合计数中有着十分广泛的应用，许多计数问题都可以直接或间接地使 用c a t a l a n 数解决组合数学中一些重要的组合对象如格路，平面树，二叉树，多边形分 割等都可以用c a t a l a n 数来计数。这一节我们主要用格路的语言来描述c a t a l a n 数的定义 及一些相关的性质我们将用组合的方法证明c a t a l a n 数的发生函数满足的关系式，从而 用发生函数的方法求出c a t a l a n 数的表达式 定义2 1 1 一条2 n 长的d y c k 格路是指在z 2 中，从原点似缈出发到( 2 礼，o ) ，由以，i ， 方向的上升步和以，j ，方向的下降步组成的，始终在z 轴上方的一条路径从似砂出 发到伽，刃的d y c k 格路 i s t 改n - d y c k 格路 为了更好地理解定义，我们画出n = 2 和n = 4 时所有的d y c k 格路 入 图2 1 两条长度为4 的d y c k 格路 f i g 2 1t w od y c kp a t ho fl e n g t h4 从八 八 - 入 图2 2 五条长度为8 的d y c k 格路 f i g 2 2 f i v ed y c kp a t ho fl e n g t h8 我们把长度为2 n 的d y c k 格路的集合记做厶1 c n l 是由c a t a l a n 数来计数的， c a t a l a n 数的初值是1 ，1 ，2 ，5 ，1 4 ，4 2 ，1 3 2 ，4 2 9 ，1 4 3 0 ，4 8 6 2 ，并且c a t a l a n 数岛，g ，满足 下面的递归关系式s 4 大连理工大学硕士学位论文 证明对于任意一条长度为2 几的d y c k 格路d 厶，设d 第一次与z 轴的交点为 ( 2 i ，0 ) 0 1 ) ，则d 被分割成两部分，从( 1 ，1 ) 到( 2 i 一1 ，1 ) 以及从( 2 i ，0 ) 到( 2 n ，0 ) 把 ( 1 ，1 ) 到( 2 t 一1 ，1 ) 的d y c k 格路向( 1 ，一1 ) 方向平移一个单位，就可得到从( 1 ，1 ) 到( 2 i - 1 ，1 ) 的d y c k 格路等价于从( 0 ，0 ) 到( 2 i 一2 ，0 ) 的d y c k 格路，这一部分的计数用式子表示就是 q 一1 ( i 1 ) 而从( 2 i ，0 ) 到( 2 n ，0 ) 的d y c k 格路的计数是瓯一t ( t 1 ) ，从而得到 u c a t a l a n 数 g h o 的发生函数记做c ( z ) ，即c ( z ) = g 扩，其中c ( z ) 满足下 面的关系式： 命题2 1 3 c ( z ) = 1 + z c 2 ( z ) = 1 - f v f f - 4 x 证明对于任意一条长度为2 礼的d y c k 格路d 厶，我们对它进行分解，如图2 3 所示， 图中有礼个上升步和n 个下降步，在这里用z 标注每一个上升步它的发生函数分为两 部分s 如果d 不是空路，它必定从一个上升步开始，从第一个上升步到第一个与z 轴相 交的下降步之间是任意一条d y c k 格路设这个下降步与z 轴的交点为( 2 i ，0 ) ，从( 2 i ，0 ) 到( 2 n ，0 ) 是任意一条d y c k 格路，所以这两部的发生函数用式子表示即是x c 2 ( z ) ；另一 方面，如果d 是空路，它的发生函数就是1 因此 c ( x ) = 1 + x c 2 ( z ) ， 从而得到 c ( z ) = 1 - f v q - - 4 x 口 图2 3 一条非空的d y c k 格路的分解 f i g 2 3t h ed e c o m p o s i t i o no fan o n e m p t yd y c kp a t h 根据c a t l a n 数的发生函数，我们得到c a t a l a n 数的表达式为： 5 ，工 = 岛中其_og “铷 = 幺l幺题 命 一o g 铷 = _og n 汹 = g f i n e 格路和有禁错排 命题2 工4 g = 击( 等) c ( 垆壹g 扎竿1 - v f f - 4 x ， n = 0 。4 把钔忑进行二项式展开得 一= 薹( 沙埘 一薹( 叫七紫( 叫南 = 1 一耋生产陋广 一薹鬻严 = 1 一蚤o o 丽( 2 k - 可2 ) ! ! z 缸 = 1 2 三1 ( 2 k 叫- 2 、以 p = ；o ：o 1 ( 2 ：j ：) 产1 瓯= 击( 翟) 2 2 f i n e 数的基本概念和其性质 口 本文主要研究f i n e 数的相关知识，在前面我们提到f i n e 数和c a t a l a n 数有非常紧密 的联系，对c a t a l a n 数有了一定的了解后，下面我们就来探讨f i n e 数的定义及其相关的 性质 定义2 2 1 在z 2 中，一条2 n 长的f i n e 格路是一条不包含h i l l 的2 n 长的d y c k 格路 一个h i l l 是由以，j j 方向的上升步和以，一砂方向的下降步形成的高度为j 的峰从阳，砂 出发到( 2 n ，叫的f i n e 格路记做n f i n e 格路 为了更好地理解定义，我们画出礼= 2 ，n = 3 和n = 4 时的所有的f i n e 格路 6 大连理工大学硕士学位论文 图2 4 一条长度为4 的f i n e 格路 f i g 2 4af i n ep a t ho fl e n g t h4 图2 5 两条长度为6 的f i n e 格路 f i g 2 5t w of i n ep a t ho fl e n g t h6 图2 6 五条长度为8 的f i n e 格路 f i g 2 6f i v ef i n ep a t ho fl e n g t h8 在这篇文章中，我们用乱来表示上升步，用d 来表示下降步在一条格路中一对连 续的u d 步叫做峰，一个峰中所包含的d 步叫做f a l l 格点指的是每一步的两个端点，我 们把峰所包含的毯d 步中所有格点的纵坐标的最大值叫做峰的高度，一条格路的高度是所 有峰的高度的最大值。 我们把长度为2 礼的f i n e 格路的集合记做矗矗是由f i n e 数r 来计数，f i n e 数的初值是1 ，0 ，1 ，2 ，6 ，1 8 ，5 7 ，1 8 6 ，6 2 2 ，2 1 2 0 ，f i n e 数 r ) n o 的发生函数记做f ( z ) ，即 f ( x ) = ：r 矿f i n e 数的发生函数和c a t a l a n 数的发生函数之间满足如下关系式： n = o ，= 广广 命题2 2 2 f ( z ) = 1 + z ( c ) 一1 ) f ) = 圭导二篙 “o v 上一蚴 证明对于任意一条长度为2 礼的f i n e 格路，我们对它进行分解，如图2 7 所示，图中有 礼个上升步和n 个下降步，在这里用x 标注每一个上升步我们考虑两种情况，如果f i n e 格路是空路，那么它的发生函数是1 ；如果它不是空路，它必定从一个上升步开始，因为 要避免出现一个h i l l ，所以从第一个上升步到第一个与z 轴相交的下降步之间它是一条 非空的d y c k 格路，所以这部分的发生函数是c ( z ) 一1 ，设第一个下降步与z 轴的交点 7 f i n e 格路和有禁错排 为( 2 i ，0 ) ，从( 2 i ，0 ) 到( 2 n ，0 ) 是任意一条f i n e 格路，所以这部分的发生函数是f ( x ) ， 因此， 所以 又因为 因此 f ( x ) = 1 + x ( c ( x ) 一1 ) f ( x ) = 1 + z ( x c 2 ( z ) ) f ( 。) f ( z ) = 1 - l x 2 c 2 ( x ) c ( x ) 1 + x c ( x ) c ( z ) = 1 - f v f f - 4 x ， 砟一1 暑霉 图2 7 一条非空的f i n e 格路的分解 f i g 2 7t h ed e c o m p o s i t i o no fan o n e m p t yf i n ep a t h 命题2 2 3 f i n e 数和c a t a l a n 数满足关系式：g = 2 f + r 一1 证明因为 所以 所以得到 砷) = 而1= 斋， c ( x ) = f ( z ) ( 1 + x c ( x ) ) = f ( x ) + x f ( x ) + f ( z ) 一1 1 + c ( z ) = ( 2 + z ) f ( z ) ， 8 口 大连理工大学硕士学位论文 因为 所以 1 + g ) = 岛z o + g i x n 一1 竹= 1 o o = c x n ( 2 + z ) f ) = 2 r z n + z r i x 竹一1 n = o n - - - - 1 0 0o 。 = 2 f f x n - t - f r 一1 z n 二j 一 q = 2 f + r 一1 2 3 f i n e 数的几个重要的恒等式 根据f i n e 数和c a t l a n 数之间的关系，我们得到f i n e 数的若干性质如下： 性质2 3 1 2 ( n + 1 ) r = ( 7 n 一5 ) r 一1 + 2 ( 2 n 一1 ) f n 一2 证明根据命题2 1 4 得 所以 又根据命题2 2 3 得 所以 g = 击( 翟) ， c n - 1 1 n ( ：二# ) ， n 一上， 倪= 攀半礼+ l = 2 r - t - r 一1 ， c 一1 = 2 f 一1 + j k 一2 ， 2 f + r 一= 塑箬- t 半- ( r 一，+ r 一2 ) nl 把上式整理得到此性质 性肌3 2r = 击( 2 礼i 2 ) + 高( 2 铭i4 ) + 熹( 2 礼i6 ) 一其中喇 9 口 口 f i n e 格路和有禁错排 证明因为 则 又因为 所以 令 那么 所以 f ( x ) 1 一。2 c 2 ( z ) f ( z ) = z 2 伽c ( z ) 陋n i v 8 ( z ) = f ( z ) = f ( x 1 = 对上式展开就能得到此性质 i 0 n 0 i 0 i 0 i 0 i 0 焘( 2 扎n 2 i 2 n + 2 i( 2 n 一一瓤 m = n + 2 i n o n o n o r = t 0 2 暮 2 m 2 i 2 i 2 m 2 i 己一0 ( 2 m m 划- 2 i 、z m ( 2 m ( 2 2 2 ) 少 熹( 2 礼一 性质2 3 3 r = 丢 瓯一言瓯一+ 壶g 一2 + ( 一1 ) 俨2 刍q 证明因为 同理 则 g = 2 f + r 一1 ， g 一1 = 2 r 一1 + r 一2 ， 口 or 一 m 1 2 = r 所以 依次类推，所以得到等式 性质2 3 a 爰一言 证明因为 同理 则 又根据 则 令 所以 即 大连理工大学硕士学位论文 r f 三( 一一r _ ， 马= 互1 ( q 一日) r = l c n 一三( g 二一f n 一2 ) & = 击( 翟) ， 门1 ，2 n 一2 、 - 12 元l n 一1 c k = 2 f + r 一1 ， 1 = 2 爰+ 等 = 2 爱+ 瓦f - i 百c - i 1 ：2 l + k 4 4 l 2 9 1 1 口 口 = 鲁 璺l f i n e 格路和有禁错排 2 4 f i n e 数的一些组合解释 f i n e 数有很多组合解释，它和一些重要的组合对象，比如它和d y c k 格路，y o u n g 表，分拆，平面树，m o t z k i n 格路有比较紧密的联系d e u t s c h 和s h a p i r o 在文献【2 8 1 中 给出f i n e 数的一些组合解释，下面我们通过建立双射的方法来证明这些组合解释。在证 明这些组合解释之前，我们首先给出个重要的引理，下面的很多证明都是以此引理为 基础 引理2 4 1 如果d y c k 格路中第一峰的高度是k ，那么它的发生函数是x k c 知( z ) 证明对于任意一条d y c k 格路，我们画出当k = 2 时的情形，如图2 8 所示我们把这 条d y c k 格路分解，如果d y c k 格路中第一个峰的高度是k ，根据峰的定义，这条d y c k 格 路只能从k 个连续的上升步开始，并且从格点( k ，k ) 到格点( k + 1 ，k 一1 ) 产生第一个下降 步在第一个下降步以后总存在一个高度为k 一1 。的下降步，它和前面的高度为k 一1 的 上升步相对应，从第一个下降步到这个下降步之间是任意一条d y c k 格路，所以它的发生 函数是c ( x ) 同理，从高度为殆一1 的下降步到高度为七一2 的下降步之间也是任意一 条d y c k 格路，它的发生函数也是c ( z ) 依此类推，直到最后一个下降步到达z 轴所 以从格点( k ，k ) 到z 轴之间这一部分的发生函数是萨( z ) ，因为k 个连续的上升步的发生 函数是扩，所以第一个峰的高度是k 的d y c k 格路的发生函数是扩c 知( z ) 口 图2 8 一条非空的d y c k 格路的分解 f i g 2 8t h ed e c o m p o s i t i o no fan o n e m p t yd y c kp a t h 下面给出f i n e 数的一些组合解释： 性质2 4 2 从左往右看，满足第一个峰的高度是偶数的长度为2 礼的d y c k 格路的计数是 r 证明根据引理2 4 1 ，我们得到满足条件的d y c k 格路的发生函数为 l + z 2 c 2 ( z ) + $ 4 c 4 ( z ) + + x 2 n c 2 n ( z ) 2 i _ 二= ：i 1 雨2f ( z ) 即它和f i n e 数有相同的发生函数，所以满足条件的计数就是f i n e 数 口 那么 设他是个自然数，如果正整数的有序组n 1 ，佗2 ，n 南满足n 1 n 2 n 七 0 ， 住= 7 1 + n 2 + + 忱七 1 2 大连理工大学硕士学位论文 称为礼的一个分割 设n 1 ，n 2 ，佗七) 是n 的一个分割，伴随 n 1 ，n 2 ，竹七) 的一个y o u n g 图是第一行 有礼1 个格，第二行有礼2 个格，第k 行有n 七个格的图若将数字1 ，2 ，n 放入上 述图的格中，这样形成的一个表称为y o u n g 表，称 n 1 ，n 2 ，n k 为该y o u n g 表的型 若y o u n g 表中每一行中的元素是弱增的，每一列的元素是严格递增的，称之为半标准杨 表若杨表中每一行，每一列中的元素都是严格递增的，称之为标准杨表具有型( 佗，几) 的标准y o u n g 表指的是有两行且每行有礼个元素，并且每一行和每一列中的元素都是严 格递增的，其中任一列都不存在的形式的表是指任何上下对应的两格中的数字不 厅十上 z 连续下面给出礼= 4 时具有型( n ，n ) 且每列不出现形式的标准y o u n g 表； 表2 1n = 4 时每一列不出现形式的y o u n g 表 t a b 2 1t h e r ei sn oc o l u m no f t h ef o r m 击w h i l en=4 圈弱圈圈圈 图圈匪圈团圈 性质2 4 3 具有型( 礼，n ) 且每列不出现* 形式的标准y o u n g 表的计数为r = 十l l 证明对于任意一个( 礼，n ) 形式的且不包含* 形式的标准y o u n g 表，从1 到几遍历： 对于每一个i ，如果i 在第一行，它对应一个上升步；如果i 在第二行，它对应一个下降 步因为此y o u n g 表中每列不出现毛形式，所以按照这种对应法则得到的格路中不 包含h i l l ，因此它是一条扎一f i n e 格路，所以满足条件的表的计数是r 反之，对于任 意一条n f i n e 格路，从左往右给第i 步标号i ，那么所有的上升步的标号和所有的下降 步的标号都是递增的把所有的上升步的标号和所有的下降步的标号分别写成一行就得 到一个( 礼，佗) 形式的且不包含的形式的标准y o u n g 表图2 9 给出了一个( n ，礼) 形 厶 尤十上 式且不包含之形式的标准y o u n g 表和f i n e 格路对应的例子 口 图2 9y o u n g 表和f i n e 格路的对应 f i g 2 9 a b i j e c t i o nb e t w e e ny o u n gt a b l e a u xa n df i n ep a t h 1 3 f i n e 格路和有禁错排 m 的一个划分是集合m 的一个子集族b 1 ，岛，鼠使得m = b 1ub 2u u 鼠， 并且对于任意的1 i 七，鼠圣，i 歹时鼠n 日= 西，称鼠是一个块在 n 的所 有划分中，对于m 中的元素a ，b ，c ，d ，当a b c d 时，a 和c 在一个块中，而b 和d 在另一块中的情况不同时出现，满足上述条件的m 的所有的划分称为i n 的不交划 分我们举一个例子来说明第一个块的长度为偶数的不交划分，下面给出礼= 4 时所有 的满足条件的不交划分： 八 、 l 23 4 六 1 23 4 1234 、广叭、 1234l2 、 341234 图2 ，1 04 长的第一块的长度为偶数的不交划分 f i g 2 1 0n o n c r o s s i n gp a r t i t i o n so fl e n g t h4 ，w h e r et h ef i r s tb l o c kh a se v e ns i z e 性质2 4 4 “n 的第一个块的长度是偶数的不交划分的计数是晶 证明对于任意一个 钆 的第一个块的长度是偶数的不交划分，从1 到礼遍历；对于每一 个i ，如果i 不是它所在块的最大元素，t 对应一个上升步；如果i 是它所在块的最大元 素，i 对应一个上升步，再加上m 个下降步，其中m 是这个块的大小。这样就得到一 条第_ 个峰的高度是偶数的n d y c k 格路。根据性质2 4 2 ，满足条件的不交划分和f i n e 数有相同的发生函数，所以它的计数是晶反过来，对于任意一个第一个峰的高度是偶 数的n - d y c k 格路，从左到右给第i 个上升步标号i ，对于每一个下降步，它的标号是和 它对应的上升步的标号，一个下降步对应的一个上升步指的是在同一层上向左数第一个 向上的步从而连续下降步的标号构成不交划分的一个块图2 ，1 1 给出了满足条件的不 交划分和第一个峰的高度是偶数的d y c k 格路对应的一个例子： 口 、 1 23 图2 1 1 第一块的长度为偶数的不交划分和第一个峰的高度是偶数的d y c k 格路的对应 f i g 2 1 1ab i j e c t i o nb 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 ，w h e r et h ef i r s tb l o c k h a se v e ns i z ea n dd y c kp a t h sw h o s ei n i t i a lp e a kh a se v e nh e i g h t 一个单点是只包含一个元素的块，在m 的所有不交划分中，对于【n 】中的元素a ，b ，c ， 当o b c 时，a 在一个块中，b 和c 在另一个块中，a 称为m 的不交划分的可视单 点下面给出扎= 4 时所有的不包含可视单点的不交划分： 1 4 大连理工大学硕士学位论文 瓜六 1234 八、 1234 图2 1 24 长的不包含可视单点的划分 f i g 2 1 2n o n c r o s s i n gp a r t i t i o n sw i t hn ov i s i b l es i n g l e t o n so fl e n g t h4 性质2 4 5 m 的不包含可视的单点的不交划分的计数是晶 证明对于任意一个【n 的不包含可视的单点的不交划分，从1 到n 遍历：对于每一个 i ，如果i 不是它所在块的最大元素，i 对应一个上升步；如果i 是它所在块的最大元素