（运筹学与控制论专业论文）dyck路motzkin路和schroder路上峰的计数.pdf

煳黻 u n e r s i t yc o d e ：l0 2 6 9 s t u d e n ti d ：5 1 0 8 0 6 0 1 0 5 4 e n u m e r a t i o no fp e a k si nd y c k ，m o t z k na n ds c h r 6 d e rp a t h s d e p a n m e n t ： m a t l l e m a t i c s m 旬o r i 哆： 0 p e r a t i o n a lr e s e a r c ha n dc y b e m e t i c s d i r e c t i o n ： c o m b i n a t o r c s s u p e i s o r ： r u o ) 【i ad u c a i l d i d a t e ：y _ u nd i n g a p m ，2 0 1 1s h a i l 曲a i 本学位论文原创性声明的法律责任由本人承担 作者签名： 丁i日期：别1 年6 月f 日 华东师范大学学位论文著作权使用声明 峰的计 及取得 或撰写 确说明 d y c k 路，m o t z b n 路和s c i l r 6 d e r 路上峰的计数系本人在华东师范大学攻读学 位期间在导师的指导下完成的硕士学位论文，本论文的研究成果归华东师范大学所 有本人同意华东师范大学根据相关规定保留和使用此学位论文，并向主管部门和相 关机构如国家图书馆、中信所和“知网 送交学位论文的印刷版和电子版；允许学位 论文进入华东师范大学图书馆及数据库被查阅、借阅；同意学校将学位论文加入全国 博士、硕士学位论文共建单位数据库进行检索，将学位论文的标题和摘要汇编出版， 采用影印、缩印或其他方式合理复制学位论文 1 经华东师范大学相关部门审查核定的“内部”或“涉密学位论文，于2 0 1 1 年7 月1 日解密，解密后适用上述授权 2 不保密，适用上述授权 导师签名： 榀徙 本人签名：丁之 】0 1 1 年6 月j 日 “涉密”学位论文应是已经华东师范大学学位评定委员会办公室或保密委员会审定过的学位论文( 需附获批 的华东师范大学研究生申请学位论文“涉密”审批表方为有效) ，未经上述部门审定的学位论文均为公开学 位论文此声明栏不填写的，默认为公开学位论文，均适用上述授权 丁云硕士学位论文答辩委员会成员名单 姓名职称 单位备注 任韩教授华东师范大学数学系主席 吕长虹教授华东师范大学数学系 郭军伟副教授华东师范大学数学系 摘要 d y c k 路，m o t z 虹n 路和s c h r 6 d e r 路等格路径作为一类重要的组合结构是近年来计 数组合学研究的一个热点它们与树，有禁排列，正交多项式，连分式等其它结构联系 紧密，并且在统计学，随机过程及生物信息学等领域有着广泛应用在本文中我们主要 研究了这三种格路径上的统计量：峰的个数a r e g e v 在 1 6 】中利用递推关系通过大 量的计算给出了m o t z l ( i n 路上的峰的个数，并发现，l 阶广义m o t z k i n 路的个数等于所 有，l 阶的m o t z l ( i n 路上的峰的个数的两倍加一，并提出公开问题，即寻找这一问题的 双射证明本文的主要结果就是构造了一个双射从而解决了a r e g e v 提出的问题利 用这一双射我们给出了d y c k 路，m o t z l 【i n 路和s c 啪d e r 路上峰的个数，以及n a m y a n a 数的一个新的证明另外通过用两种不同的方法计数广义s c 啪d e r 路的个数，我们还 得到了一个有趣的组合恒等式这个等式即为 2 1 中第1 1 5 页习题3 ( g ) 等式的变形 本文的另一个主要结果就是利用r s k 算法，给出了m o t z 虹n 路和行数不超过3 的 标准杨表之间的一个双射 关键词：格路径，d y c k 路，m o t z l ( i n 路，s c h r 6 d e r 路，峰，标准杨表，r s k 算法 b i n a t o r i a ls t m c 一 o t h e rc o n l b i n a c o n t i n u e df h c t i o n s ，e t c ，m e i ra p p l i c a t i o n sa l s oa r i s ef o mf i e l d sa ss t a t i s t i c s ，啪d o mp r o c e s s e sa n db i o i n f o m a t i c s i nt h i sp a p e rw em a i n l ys t u d yt h es t a t i s t i c “n u m b e ro fp e a k s ”i nt l l e s el a t t i c e p a m s i i l 【l6 】a r e g e vc o m p u t et l l en u m b e ro fp e a k s ( h u m p s ) i nm o t z l ( i np a t l l s ，a i l dn o t i c e t h a tm en u m b e ro fg e n e r a l i z e dm o t z l ( i np a t l l so f0 r d e r ，le q u a l so n e p l u st w i c et h en u m b e r o fp e a l ( si na l lm o t z l ( i np a t h so fo r d e r ，z ，a n da s kf b rab i j e c t i v ep r o o ff o rt l l i si d e n t i t y i n m i sp a p e rw eg i v es u c hab i j e c t i o n ，f 硒mw h i c hw eg i v et h en u m b e ro fp e a k si nd y c kp a t h s ， m o t z k i n p a t h sa n ds c h r 6 d e rp a t h s u s i n gt l l i sb i j e c t i o n ，w eg i v ea n e w p r o o fm a t t h en u m b e r o fd y c k p a t h so fo r d e r ，1w i t l l 七p e a l 【si st h en a r a y a i l an u m b e r b yd o u b l ec o u n t i n gg e n e r - a l i z e ds c h r 6 d e rp a t h s ，w ea l s of i n da ni n t e r e s t i n gi d e n t i t yi i l v o l v i n gp r o d u c t so fb i n o m i a l c o e m c i e n t s ，as l i 曲yd i 能r e n tf o mo f “si d e n t i t ya p p e a r si n 【21 】p a g e1 15e x 3 ( g ) a n o t h e rr e s u l to ft l l i sp 印e ri sa b i j e c t i o nv i ar s ka l g 耐t h mb e t w e e nm o t z k i np a t l l s a n ds t a i l d a r dy i d u n gt a b l e a u xw i t ha tm o s tt b r e er o w s k 色y w o r d s ：l a t t i c ep a t h s ，d y c kp a t h s ，m o t z k i np a t h s ，s c m d e rp a t h s ，p e a k s ，s t a n d a r d y o u n gt a b l e a u x ，r s ka l g o r i m m 目录 摘要i a b s t r a c t 豇 l 引言 1 1 1 m o t z h n 路的概念 1 1 2 研究背景和意义2 1 3 本文研究结构 3 2 常见格路径及相关组合结构 5 2 1 相关概念5 2 2m o t z l ( i n 路及m o t z k i n 数7 2 3 d y c k 路和c a t a l a n 数 9 2 4s c i 嫡d e r 路与s c l l r 6 d e r 数1 0 3m o t z k i n 路上的峰1 3 3 1 峰的概念 1 3 3 2 双射：尹朋n 一5 硝 1 4 3 3m o t z k i n 路上的峰的个数1 7 4 d y c k 路与s c h 而d e r 路上的峰 1 9 4 1 d y c k 路上的峰 1 9 4 2s c m d e r 路上的峰2 3 5m o t z k i n 路与标准杨表2 6 5 1 r s k 算法2 6 1 1 l 2 8 2 9 致谢3 4 虬 勉 l 引言 1 1m o t z k i n 路的概念 在平面直角坐标系中，横坐标和纵坐标都为整数的点称为平面格点，平面格路径 是指在所有的平面格点中，从一点到另一点只走格点的路，格路径的长度是指其所走 的路的步数我们这里研究的都是平面格路径，下面都简称为格路径一条长度为，l 的 格路径也可以看做一个，l 维的向量v = ( v 1 ，屹，) ，这里v f 刃，v f + l v f 表示这条格 路径所走的步法之一 格路径是组合数学中非常重要的一个概念，因而有关格路径的研究在组合数学中 一直占据着非常重要的位置，这是由于格路径不仅可以做为重要的模型来描述其他的 组合统计量，像树，有禁排列，正交多项式，连分式等，也可以做为证明组合恒等式的 重要工具，并且还在其他数学分支比如概率论，统计学，随机过程等有着广泛的应用 见 3 ，1 3 ，1 4 ，2 2 】另外，格路径与生物信息学也有着很密切的联系 在计数组合学的研究中，对格路径所走的步做不同的限制即得到不同类型的格路 径格路计数主要是研究这些不同类型的格路的数目和性质也是我们这篇文章研究 的主要对象m o t z h n 路和d y c k 路是两种最典型的格路径，它们与计数组合学中的很 多经典的序列有着很密切的关系，见【4 】所以一直以来被广泛的研究，下面我们首先 来介绍一下什么叫做m o t z k i n 路 定义1 1 ( m o t z h n 路) ，l 阶的m o t z k i n 路是指在平面直角坐标系的第一象限内从原 点( o ，0 ) 到点( 0 ) 的格路径，并且允许的步法只能为( 1 ，1 ) ，( 1 ，0 ) ，( 1 ，一1 ) ( 分别记为 u 只d ) 任意一个凡阶的m o t z l 【i n 路m 可以看作是一个挖长的序列m = m l ， 尬 ued ，并且在任意七长的子序列m l 尬尥中，u 的个数不能少于d 的 个数如图l 表示_ ，z = 3 时的4 条m o t z k i n 路他们对应的序列分别是：，f f ，f u d ， u f d ，u d f 所有，l 阶的m o t z b n 路的全体构成的集合我们记为朋n ，它的个数我们称 为第，z 个m o t z b n 数，记为 第一节引言 1 2 研究背景和意义 图l ：挖= 3 时的4 条m o t z k i n 路 在生物学的研究中，有关遗传学的研究越来越受到人们的重视，其中最重要 的是对d n a ( 脱氧核糖核酸) 的研究，d n a 是一类带有遗传信息的生物大分子， 它由4 种主要的脱氧核苷酸( d a m ed g m 只d c m t 和d 1 m p ) 通过3 c ，5 c 磷酸二酯 键连接而成这些脱氧核苷酸的组成和排列不同，显示不同的生物功能，如编码 功能，复制和转录的调控功能等排列的变异可能产生一系列疾病r n a ( 核糖 核酸) 作为d n a 的信使，是由至少几十个核糖核苷酸通过磷酸二酯键连接而成 的一类核酸，在1 9 6 5 年r w 霍利等测定了第一个核酸即酵母丙氨酸转移核糖 核酸的核苷酸的排列顺序，我们称为此核糖核酸的一级结构也叫做线性链，此 后，关于对峪一级结构的测定有了迅速的发展当对姨只在这一个链中两个邻 居之间有键时，它自己折叠起来形成称为w a t s o n c r i c k 键的新键，这些新键定义 原来对峪链的二级结构如图2 给出了下面砌蛆链的一个可能的二级结构： aa c g g g g c g g g a c c c ij ij c a a c c c c i 兀7 cc c a 图2 ：砌呵a 链a a c g g g g c g g g a c c c u u c a a c c c c u u 的一个二级结构 1 9 8 0 年h o w e l l ，s m i t hw a t e 册a n 使用递推关系计算出长度为，z 的鼬蛆链的可能 2 图3 ：与r n a 链a a c g g g g c g g g a c c c u u c a a c c c c u u 对应的m o t z l ( i n 路 二级结构的数量，见【1 8 】，正好等于组合数学中经常提到的，z 阶的m o t z l ( i n 路的个数， 即第，1 个m o t z b n 数图2 给出的砌峨链的二级结构就对应一个2 6 阶的m o t z h n 路如图3 所示 1 3 本文研究结构 峰是格路径上的一个非常重要的统计量，a r e g e v 在【1 6 】中利用递推关系通过大薯 量的计算得出了m o t z 虹n 路上的峰的个数，由此得到了它们与广义m o t z h n 路的个数 的关系，并提出一个公开问题，希望可以找到一个组合证明来证明m o t z l ( i n 路上的峰 与广义m o t z k i n 路的关系本文的主要结果之一就是构造一个双射从而给出该问题的 组合证明 本文的另一个研究对象是行数不超过3 的，l 阶标准杨表，它的个数我们记 为s ( 3 ，0 ；”) 1 9 8 1 年，a r e g e v 在 1 5 】中运用对称函数的方法计算出了s ( 3 ，o ；，z ) = 伽击( 力( 力从而发现s ( 3 ，o ；n ) 正好等于第，1 个m o t z h n 数，l n s e n - p e n ge u 在 9 】中 通过对m o t z k i n 路上的步进行标号的方法给出了s ( 3 ，o ；，z ) = m 九的一个组合证明这 篇文章的另外一个主要结果就是利用r s k 算法，通过构造双射证明了s ( 3 ，0 ；咒) = m 玎 在第二节中，我们介绍了三种常见的格路径m o t z b n 路，d y c k 路，s c h r 6 d e r 路以及 与它们相关的一些组合结构 在第三节中，通过构造双射证明了m o t z h n 路上的峰的个数和广义m o t z 虹n 路的 关系，从而解决了a r e g e v 在 1 6 】中提出的公开问题 第四节是进一步讨论其它类型的格路径d y c k 路和s c l l r 6 d e r 路上的峰，给出了 3 第一节引言 n a r a y a n a 数的一个全新的计算方法并且通过用两种不同的计数方法计广义s c i l r 6 d e r 路的个数，我们还得到了一个有趣的组合恒等式 第五节主要是研究m o 蛐n 路与标准杨表的关系，利用r s k 算法证明了最多只有 三行的咒阶标准标准杨表的个数s ( 3 ，o ；，1 ) 等于第，1 个m o t z k i n 数m n 第六节是进一步的研究方向 4 第二节常见格路径及相关组合结构 2 常见格路径及相关组合结构 在组合数学中，用格路径做为模型可以描述很多组合结构，例如，树，标准杨表等 为了介绍这些相关结论，在这里我们先介绍一些基本的概念 2 1 相关概念 定义2 1 ( 图( g r a p h ) ) 由点集y = ( v l ，屹，) 和边集e = ( p l ，p 2 ，) 构成的有序 对g = ( ve ) 称为一个图，其中e 是由y y 的元素组成的可重集合 定义2 2 ( 有向图( d n c t e dg r a p h ) ) 每条边都含有一个方向的图叫做有向图设点1 ，是 有向图g 的一个顶点，则v 的出度是指从v 出发的边的条数，v 的入度是指向v 的边的 条数，v 的出度和入度的和称为v 的度 定义2 3 ( 连通图( c o n n e c t e dg r a p h ) ) 图g 中若点1 ，是边p 的一个顶点，则称，和p 是 关联的，图g 中前后关联的点边序列：w = p l ，1 9 2 屹岛h 称为g 的一条通道，若g 的一条通道中的点，边都不重复，则称其为g 的一条路，若g 的路的起点和终点重合， 则称其为g 的一个圈“，1 ，y ( g ) ，若存在一条从“到v 的路，则称“，v 是连通的，若g 中任意两点都是连通的，则称g 为连通的 定义2 4 ( 平面图( p l a n eg r 叩h ) ) 如果图g 可以画在平面上，使得任意两边互不交叉，则 称图g 为可平面图可平面图g 在平面上画出的无交叉边的图示称为它的平面嵌入， 它的任何一个可平面嵌入都称为一个平面图 定义2 5 ( 树( t r e e ) ) 连通且没有圈的图我们称为树 定义2 6 ( 平面树( p l a i l e 骶e ) ) 树的任一个可平面嵌入叫做一个平面树 定义2 7 ( 有根树( r o o t e d 骶e ) ) 设r 是一棵有向树，若r 中有一个顶点的入度为0 ，其 余顶点的入度都为l ，则称丁为有根树入度为o 的点称为根，出度数为1 的点称为叶 子设“，v 为丁中的点，若h 到1 ，有有向边，则称“为1 ，的父亲，1 ，为“的孩子 定义2 8 ( 有序二叉树( b i n a r yo r d e r e d 仃e e ) ) 若有根树z 的每个顶点最多只有两个孩 子，且它的孩子是有序的，则称丁为一个有序二叉树 气 第二节常见格路径及相关组合结构 定义2 9 ( 整数分拆( i n t e g e rp 越i t i o n ) ) ，l 为一正整数，a = ( a i ，a 2 ，九) ，满足允l 允2 儿 o ，且a l + a 2 + + 九= ，l ，则称a 为，l 的一个分拆，记为a 卜，1 七叫做分拆允 的长度，记为z ( a ) = 尼 例2 1 取，l = 1 6 ，则a = ( 5 ，3 ，3 ，2 ，1 ，1 ，1 ，) 就是1 6 的一个分拆，m ) = 7 定义2 1 0 ( 集合分拆( s e tp 矾t i o n ) ) 7 r = b l ，豌，瞰l 若满足 岛0 ，且毋m 】，v i ； 若f j ，则岛n 毋= 0 ； b lub 2u u 风= 研】， 则称7 r 为集合的一个分拆每个最称为该分拆的一个块 定义2 1 1 ( 标准杨表( s y t ) a 卜，l ，平面点阵列丁= ( 瓦_ ，) 称为形状为l 的一个n 阶标 准杨表，如果它满足： 瓦，j 为正整数； 1 f z ( 五) ，1 歹a f ； 每行和每列都是严格递增的 此时，a 称为标准杨表丁的形状，记为s h ( a ) 1351 01 7 2691 2 例2 2 r ：4 81 l 表示一个形状为a ：( 5 ，4 ，3 ，3 ，2 ，1 ) 的标准杨表 71 3 1 4 1 51 8 16 6 第二节常见格路径及相关组合结构 定义2 1 2 ( 避免“的排列) 若丌表示从 ，z 】= 1 ，2 ，咒j 到m 的一个双射，则我们可 以称序列7 r = 7 r 1 7 r 2 为 ，l 】的一个排列，其中雨= 丌( f ) ，v 1 f n m 的所有排列 构成的集合记为6 。取“= “1 “2 魄6 七，丌= 7 r l 丌2 g 。，如果7 r 中不存在子序 列丌f 。丌f 2 瓢，使得丌f 。，丌f 2 ，瓢的大小关系和对应的“l ，“2 ，魄的大小关系一致， 则称丌是一个，l 阶的避免“的排列这样的避免某个排列的排列我们叫做有禁排列 我们用g 。( n ) 表示g 。中所有的避免l l 的排列 如果我们取“= 3 2 1 ，称这样的排列为避免3 2 1 的排列例如，l = 4 时1 4 个避免 3 2 1 的排列如下： 1 2 3 41 2 4 31 3 2 4 1 3 4 21 4 2 32 1 3 42 1 4 3 2 3 1 4 2 3 4 12 4 1 33 1 2 43 1 4 23 4 1 24 1 2 3 2 2m o t z k i n 路及m o t z k i n 数 对任意一条，l 阶的m o t z 虹n 路m ，若第一步为u 步，则我们总可以找到第一次回 到工轴的d 步，这时m 可以分解为u l i d 如，这里l l 如为两条m o t z l ( i n 路所以我们 可以得出第一步为u 步的，z 阶m o t z h n 路的个数为墨2m 扣2 m 川，若肘的第一步为f 步，则这样的路就相当于在，z l 阶的m o t z 虹n 第一步前加上一个f 步，所以它的的个 数等于- 1 这样我们就证明m o t z k i n 数满足递推关系( 见 1 】) ： = m 川+ m 卜2 m 硝，咒兆 扛2 ，n l21 ，21 由此我们可以计算出m o t z k i n 序列的每一有限项的值，它的前1 6 项分别为( 见【1 9 中 的序列a o o l 0 0 6 ) ： l ，1 ，2 ，4 ，9 ，2 l ，5 l ，1 2 7 ，3 2 3 ，8 3 5 ，2 1 8 8 ，5 7 9 8 ，1 5 5 1 l ，4 1 8 3 5 ，1 1 3 6 3 4 ，3 1 0 5 7 2 m o t z 虹n 序列可以反映很多组合结构，r o b e r td o n a g h e y 在 7 ，8 】中列出了很多类 型可以用的计数的树这里我们列出来几种可以用，计数的组合结构：( 见 2 0 中 习题6 3 8 ) 7 第二节常见格路径及相关组合结构 ( 1 ) 在一个圆周上，1 个点之间画任意数量的不相交的弦，这样的画法的个数为第，1 个m o t z k n 数：如图4 表示n = 4 时9 种画不相交弦的方法 o o ee 图4 ：在一个圆周上4 个点之间画不相交弦的9 种画法 ( 2 ) 咒+ 1 条边的有根平面树的个数是第，1 个m o t z h n 数，这里要求除了根节点以 外，没有一个点是恰好只有一个孩子的；如图5 表示n = 4 时满足上面要求的9 棵树 入公人念畚公尖叭瓜 图5 ：5 条边的9 棵满足( 2 ) 中要求有根平面树 ( 3 ) 每个顶点最多只有两个孩子的，l 条边的平面树的个数也是第，1 个m o t z h n 数 如图6 表示，l = 4 时满足条件的9 棵树 1 人少人叭念八 图6 ：，l = 4 条边的满足( 3 ) 中条件的9 棵平面树 ( 4 ) 我们记 硝( 忌，z ；以) = a = ( a l ，五2 ，) i a 卜玎，a 七+ l f ， 厂 ，；，z ) = f 丁i r 是一个标准杨表，且s h ( 丁) = a ， 硝( 尼，z ；n ) ) ， s ( 足，z ；n ) = 群厂( 五= ，z ；咒) 这里盯( 忌，z ；咒) 表示集合丁( 足，z ；，z ) 的个数，则有s ( 3 ，0 ；凡) = ，在第六章我们将会给 出一个组合证明例如9 个行数不超过3 的4 阶标准杨表如下： 8 2 3 d y c k 路和c a t a l a n 数 121314 + 1341213 3 22 23424 443 中也有广泛的应用，长度为n 的砌峨链的可能二级 t z l ( i n 数见【1 8 】第2 6 1 页 我们如果对m o t z 虹n 路的定义稍作修改，就得到另外一种很重要的格路径d y c k 定义2 1 3 ，l 阶的d y c k 路是指在平面直角坐标系的第一象限上从原点( o ，0 ) 到点 ( 2 n ，o ) 的格路径，并且允许的步法只能为( 1 ，1 ) ，( 1 ，一1 ) ( 分别记为ud ) 任意一个，l 阶的d y c k 路l 可以看作是一个，l 长的序列l = l l 如厶，厶 ud ， 并且在任意忌长的子序列l l 厶厶中，u 的个数不能少于d 的个数所有，z 阶的 d y c k 路的全体我们记为既很容易可以看出d y c k 路是特殊的m o t z k i n 路，它的个数 即为我们熟悉的第尼个c a t a l a n 数，记为g = 击( 翟) ，它的前1 6 项分别为( 见【1 9 】中 序列a o 0 0 1 0 8 ) ： 1 ，l ，2 ，5 ，1 4 ，4 2 ，1 3 2 ，4 2 9 ，1 4 3 0 ，4 8 6 2 ，1 6 7 9 6 ，5 8 7 8 6 ，2 0 8 0 1 2 ，7 4 2 9 0 0 ，2 6 7 4 4 4 0 ， 9 6 9 4 8 4 5 这里我们列举一些可以用g 描述的组合结构如：( 参见 2 0 】中习题6 1 9 ) ( 1 ) 用，z 一1 条对角线将一个咒+ 2 边形三角剖分成聆个三角形的剖分个数如图7 表示，z = 3 时的5 种三角剖分 圆仓q 口仓 图7 ：以= 4 时五边形的5 个三角剖分 9 第二节常见格路径及相关组合结构 下： ( 2 ) ，1 个点的有序二叉树的个数为g 如图8 表示，l = 3 时的5 棵二叉树 图8 ：，l = 4 时的5 棵二叉树 ( 3 ) ，l + 1 个点的平面树的个数为g 如图9 表示，l = 3 时的5 棵平面树 图9 ：，l = 4 时的5 棵二叉树 ( 4 ) 两行，z 列的2 ，z 阶标准杨表的个数为g 例如，l = 3 时的5 个标准杨表如下： l23l24l25 134135 456356346256246 ( 5 ) 所有，z 阶的避免3 2 1 的排列的个数为g 例如5 个3 阶的避免3 2 l 的排列如 1 2 31 3 22 1 32 3 1 3 1 2 更多关于个路径与有禁排列的文章见 2 ，1 l ，1 2 ，1 5 】，在第五节我们证明定理5 2 过程中也会讨论m o t z k i n 路与有禁排列的 2 4s c h r i ；d e r 足各与s c h r 6 d e r 数 定义2 1 4 一个，l 阶的s c h r 6 d e r 路是指在平面直角坐标系的第一象限中直线y = 工 的上方，从原点( o ，0 ) 走到点( 甩，n ) 的路，允许的步法为( 0 ，1 ) ，( 1 ，o ) ，( 1 ，1 ) ( 分别记为 u d ，f ) 任意一个，l 阶的s c h r 6 d e r 路s 可以看作是一个，l 长的序列s = sl s 2 s 。， s f ( 以只d l ，并且在任意足长的子序列sl s 2 s i 中，u 的个数不能少于d 的个数 1 0 它的个数称为第，z 个s c h r 6 d e r 数，记为品 乙m 印乩 这个式子一个证明s c t l r 6 d e r 数的前1 6 项 1 ，2 ，6 ，2 2 ，9 0 ，3 9 4 ，1 8 0 6 ，8 5 5 8 ，4 1 5 8 6 ，2 0 6 0 9 8 ，1 0 3 7 7 1 8 ，5 2 9 3 4 4 6 ，2 7 2 9 7 7 3 8 ，1 4 2 0 7 8 7 4 6 ， 7 4 5 3 8 7 0 3 8 3 9 3 7 6 0 3 0 3 8 注意m o t z l ( i n 路与s c 啪d e r 路的区别，m o t z h n 路不能简单的看做把s c l l r 6 d e r 路 在冽平面上顺时针翻转4 5 度得到的，因为在m o t z 虹n 路中，每一步的长度都为1 ，而 在s c l l r 6 d e r 路中，每一个f 步的长度为2 s c 啪d e r 路和d y c k 路是有着密切联系的， 在 6 】中d a i ld r a k e 给出了一类特殊的d y c k 路和s c h r 6 d e r 路之间的一个双射例如 n = 2 时的6 条s c 啪d e r 路如图l o 所示 田田嚣田圈图 图l o ：聆= 2 时的6 条s c m d e r 路 s c l l r 6 d e r 数同样可以反映很多组合结构： ( 1 ) 从原点( 0 ，0 ) 到点+ 1 ，l + 1 ) 的格路径的个数为品，这里要求格路径所走的 步法可以为( 1 ，o ) 和( o ，足) ( 忌可以为任意的正整数，这两种步法我们分别记为e 和d ， 并且要求除了起点和终点外，格路径应严格在直线y = x 上方例如，z = 2 时有6 条这 样的格路，它们的步法分别为： ll l e e e2 1 e e e3 e e e1 2 e e ell e l e e2 e 1 e e ( 2 ) ，z 阶的带染色的m o t z 虹n 路的个数为品，这里m o t z l 【i n 路上的每个u 步和在工 轴上的f 步可进行2 染色，不在工轴上的f 步可进行3 染色如图1 1 表示2 阶的6 条 带染色的m o t z l 【i n 路 第二节常见格路径及相关组合结构 入 图1 1 ：6 条2 阶带染色的m o t z k i n 路，我们用l ，2 来表示不同的染色 ( 3 ) 叶子可以进行2 染色的挖+ 1 个点的平面树的个数为品见【2 0 】中习题6 3 9 ( c ) 如图1 2 表示3 个顶点的6 棵叶子可2 染色的平面树 入1 八八l 八 图1 2 ：忍= 2 时的6 棵叶子可2 染色的平面树，我们用l ，2 表示不同的染色 ( 4 ) 在由单位正方形构成的平面区域内，我们用2 1 的骨牌对下面的区域a 进行 覆盖的方法数为品，a 表示的区域为：第i 行有2 f 个单位正方形( 1 f ，2 ) ，第，l 行有 2 一1 ) 个单位正方形( 见【2 0 】中习题6 3 9 ( s ) ) 例如，l = 2 时的6 种情形如图1 3 表示 向届昌岛向皿 图1 3 ：咒= 2 时的6 种骨牌覆盖方法 1 2 - 乙 3m o t z “n 路上的峰 3 1 峰的概念 定义3 1 ( 峰( p e a k ) ，谷( v a u e y ) ) m = m l 尬鸠为一条，l 阶的m o t z 虹n 路，若存 在z 使得尬= u ，尬+ l = 尬+ 2 = = 尬+ 七= f ( 七o ) ，尬姗l = d ，则称序列 尬，尬+ i ，尬+ 川为m o t z 虹n 路上的一个峰，与尬对应的步在m o t z l ( i n 路上的终点 称为这个峰的一个峰点，若存在歹使得坞= d ，脚l = 鲰2 = = f = f ( z o ) ， 烁“l = u ，则称序列鸭，坞+ l 一，坞+ “l 为m o t z l 【i n 路上的一个谷，与坞“对应的步 在m o t z k i n 路上的终点称为这个谷的一个谷点，m o t z 虹n 路到达的终点也叫称为一个 谷点 类似的，我们可以定义d y c k 路和s c l l r 6 d e r 路上的峰与谷我们将所有，l 阶的 m o t z k i n 路，s c h r 6 d e r 路，d y c k 路上的峰的个数分别记为p m 。，p 而，p 磊令 尹m n = ( ( 尬p ) l m 朋。，p 是m 上的一个标记的峰 则妒朋n = p 这三种路上的峰的个数将是我们这篇文章研究的重点，峰做为格路 径上的一个重要统计量与其他很多组合结构有着密切的联系，例如：s e n p e n ge u 和 n n g s h a i lf u 在【l o 】中证明了d y c k 路中的p y r 枷d 的个数就等于平面树的叶子的个 数，其实d y c k 路中的p y 删 i l i d 就是d y c k 路上一种特殊的峰 为了研究峰的个数，我们这里再引入一些概念和记号在d y c k 路或者m o t z 虹n 路的定义中，如果允许走到第四象限，则称这样的路为广义的d y c k 路或者广义的 m o t z k i n 路在s c l 哟d e r 路的定义中如果允许走到直线) ，= z 下面，则称这样的路为广 义s c h 硒d e r 路我们用s m h ，踢，曼分别表示n 阶的广义m o t z 虹n 路，广义d y c k 路，广义s c m d e r 路的集合，其个数分别记为s ，j 磊，s 翰 我们用s 朋】! ：，u ( 忌) ( s m j ! ：，d ( 忌) ) 表示s 朋n 中第一个非f 步为u ，最后一个非f 步 为u ( d ) 的有七个峰的，l 阶广义m o t z k i n 路的集合类似的我们可以定义彻? u ( 足) ， s 硝d ( 足) ，5 d d d ( 忌) ，& 簖u ( 足) 我们分别用黝：，s 硝，霹表示第一个非f 步为u 的广 义d y c k ，m o t z l ( i n ，s c i 的d e r 路的集合，它们的个数分别记为s 嘏，s m ：，s 13 第三节m o t z l ( i n 路上的峰 a r e g e v 在 1 6 】中利用归纳的方法，通过大量的计算得到了所有，z 阶m o t z b n 路 上峰的个数： p m n = 主( 喜( ；) ( 咒了0 一t ) 从而得到了 跏n = 2 p m n + 1 ，s 以= 2 p 磊 并提出问题，希望可以给出这两个式子一个组合证明类似地我们可以得到 s 而= 2 p 而+ 1 接下来我们将给出这些式子一个双射的组合证明，从而就可以计算出 这三种路上峰的个数 3 2 双射：p m n _ m ： 定理3 1 存在双射：p m 厅一s m ：，若( mp ) 只m 万且m 中有七个峰当且仅 当l = 西( 尬即洲j ! i ，u ( 七一1 ) us 朋：，d ( 尼) 证明? ( 1 ) 从尹m 厅到s 朋：的映射 m o t z h n 路l 上任意一点a 的横坐标记为，纵坐标记为m l 上任意两点a ，b 间的部分称为l 的一个子路，记为l a 口交换l 中的d 步和u 步，保持f 步不变则我 们将得到一条新的路，记为z 若l i ，如是m o t z l ( i n 路的两个子路，l = l l 如表示把如 的起点接在l l 的终点形成的新的子路，以l l 的起点为起点，以如的终点为终点 任取( 尬p ) 尹朋。，其中点d ( o ，0 ) ，( ，z ，o ) 分别为m 的起点的终点按如下规则 定义( 旭p ) s m ： 记点c 表示m 中满足托 却的最左边的谷点； 记点b 表示m 中满足砌 工p ，妇= 的最右边的点； 记点a 表示肘中满足朔= o ，张妇的最右边的点； 令= m d a ，l l = 慨口，如= m 肥，如= 拖； 西( 尬p ) = 如z 五= l 1 4 步法为m d ，f ，因此l 是一条n 阶的广义m o t z h n 路，并且第一次离开工轴一定是在 岛上( 不为空集) 或者如上( 厶为空集) ，因此第一次离开工轴走的一定为u 步，即 s 朋：所以西是从尹眠到s m ：的一个映射 ( 2 ) 映射m 的逆映射甲 任意取l s m ：，点d ( o ，o ) ，( ，z ，o ) 分别表示l 的起点和终点按如下规则定义 甲( d 尹 记点b 表示l 中走到工轴下方的最左边的点( 如果这样的点不存在，则令召= m ； 记点a 表示l 中满足 山j = 叫j l ，丘，叫且l u l 庇 五) = k i ，口2 ，铆 即，a = z 穴m ) 可以知道a l = l 且口f 必定是序列叫中最大的数，所以口f = 凡我们 取 暖= # 歹：且j j “1 ) ，( v l i d ，j k l = ，l + l 2 1 第四节d y c k 路与s c m d e r 路上的峰 按如下规则我们可以得到一条n 阶的d y c k 路：从( o ，o ) 出发，走口l 步u 步，易l 步d 步，再走口2 一口1 步u 步，易2 步d 步，如此下去，最后走口，一口卜l 步u 步，易，步d 步由于 f仃 ( 旷口扣1 ) + 口l = 口f - ，z ，阢= 样( j ：1 = j f 几l = ，l + 1 ) = 咒， f = 2f - l 所以我们这样最终将到达点( 2 ，l ，o ) 由玩( 1 f d 的定义可以知道6 1 表示序列甜中 口2 前面的数的个数，并且由a 的定义可以知道，口2 前面的数都不能比口l 大，所以这样 的数的个数也不能比口l 大，即口l 6 l - 一般的v 2 足厶整l 玩= 槲j ：l 歹 + l l 即冬l 阢表示甜序列中口川前面的数字的个数，由鲰+ l 的定义可以知道，这些数都将 不会超过鲰，所以这样的数字的个数也不会超过鲰，即冬1 玩鲰这就表明，在任何 时候，u 步的步数不会小于d 步的步数，这样就保证我们得到的路不会走到z 轴下方 的，并且只有u 步和d 步，所以我们得到的是一条n 阶的d y c k 路并且职m ) 中 的每一个数就对应d v c k 路上的一个峰 任意给定一条，l 阶的d y c k 路，我们依次记录这条路上连续的u 步以及d 步的步 数，这样得到两个一样长的序列u = ( 比l ，“2 ，聊) ，d = ( d l ，如，西) 则这条路上的 峰的个数就是等于这两个序列的长度z 首先令1 = “l ，v l f 厶我们取 记 u d l + 如+ 西+ l = “l + 比2 + + h “l ， 【，z 】 1 ，d l + l ，d l + 如+ 1 ，d l + 必+ + 缸l + l = f l ，如，厶一f - lj f i 赴 尼，则令，= 1 ) 若乃，不存在( 即第一行中所以的数都 小于等于尼) ，则把尼放在第一行末尾，插入过程结束若丁1 ，存在，则用足替换死，然 后令= r l ，用相同的办把插入到第二行依次下去，直到某个元素被放入到某一 行的结尾，或是新起一行的第一个元素，则插入过程结束 1371 4 l471 4 248 268 例5 1 p = ，p 卜3 = 61 1 91 1 9