（基础数学专业论文）一些组合数的对数凸性和对数凹性的组合证明.pdf

大连理工大学硕士学位论文 摘要 对数凸性和对数凹性的研究对了解组合序列的分布是有益的，这是获得不等式的丰 富源泉，而且在统计中特别有用在组合学，代数学，分析学，几何学，计算机科学和 概率统计学中很多著名的序列都具有对数凹性和对数凸性近些年来，对这个问题的研 究非常活跃s t a n l e y 在4 3 1 中对研究对数凹性问题的一般方法作了详细的阐述 2 0 0 6 年，l i u 和w a n g 在f 2 8 】中讨论了对数凹性和对数凸性之间的异同点，并且给出了研究 对数凸性问题的一般方法至今，研究对数凹性和对数凸性的方法包括经典分析学，线 性代数学，l i e 代数表示论，代数几何学和t o t a lp o s i t i v i t y 理论由于我们是基于组合背 景研究序列的对数凹性和对数凸性，因此我们希望给序列的对数凹性和对数凸性一些组 合解释本文主要用格路，d y c k 路和反射原理证明序列的对数凸性和对数凹性及其相应 的口_ 对数凸性和酽对数凹性，并得到一些新的保对数凸性的线性变换 本文安排如下： 1 第一章着重介绍对数凸性和对数凹性研究的背景及其发展情况，并简单叙述本文所 需的概念及符号 2 第二章主要讨论利用格路，d y c k 路和反射原理证明序列的对数凸性和对数凹性一般 性方法，其中第一节主要介绍大s c h r s d e r 数，中心d e l a n n o y 数，f i n e 数等的对数凸 性，第二节介绍普通d e l a n n o y 数的对数凹性及s i m i o n 猜想的推广 3 第三章介绍哥对数凸性和于对数凹性，并建立g - 对数凸性和线性变换保持对数凸 性之间的联系 关镶词：格路；对数凸性；对数凹性；q - 对数凸；q - 对数凹 一些组合数的对数凸性和对数凹性的组合证明 c o m b i n a t o r i a lp r o o f so fl o g - c o n v e x i t ya n d l o g - c o n c a v i t yo fs o m ec o m b i n a t o r i a ln u m b e r s a b s t r a c t i ti si n t e r e s t i n gt ok n o wt h ed i s t i r b u t i o no fc o m b i n a o t i r i a ls e q u e n c e s ：l o g - c o n v e x i t y , l o g - c o n c a v i t y t h i si saf e r t i l es o u r c eo fi n e q u a l i t i e s ，w h i c ha r ep a r i c u l a r l yu s e f u li ne s t i m a t e s l o g - c o n v e xs e q u e n c e sa n dl o g - c o n c a v es e q u e n c e sa r i s eo f t e ni nc o m b i a t o r i c s ，a l g e b r a ，a n a l y s i s ， g e o m e t r y , c o m p u t e rs c i e n c e ，p r o b a b i l i t ya n ds t a t i s t i c t h e r eh a sb e e na na m o u n to fi n t e r e s ta n d r e s e a r c hd e v o t e dt ot h i st o p i ci nr e c e n ty e a r i n1 9 8 9 ，s t a n l e y 4 3 g a v ea ne x c e l l e n ts u r v e yo ft h e l o g - c o n c a v i t y v e r yr e c e n t l y , l i ua n dw a n g 2 s g a v eas u r v yo ft h el o g - e o n v e 耐t y i ng e n e r a l ， t h et o o l st h a ta r eu s e f u li np r o v i n gt h el o g - c o n v e x i t ya n dl o g - c o n c a v i t yi n d u d ec l a s s i ca n a l y s i s ， l i n e a ra l g e b r a ，t h er e p r e s e n t a t i o nt h e o r yo fl i ea l g e b r a s ，a l g e b r a i cg e o m e t r ya n dt h et h e o r yo f t o t a lp o s i t i v i t y s i n c eo u rm a i ni n t e r e s ts t e m sf r o mt h ec o m b i n a t o r i a lm o t i v a t i o n s ，w ea l w a y s l o o kf o rt h ec o m b i n a t o r i a li n t e r p r e t a t i o nf o rt h el o g - c o n v e x i t ya n dt h el o g - c o n c a v i t y i nt h i s t h e s i s ，w es h o wh o wl a t t i c ep a t h s ，d y c kp a t h sa n dt h er e f l e c t i o np r i n c i p l ec a nb eu s e dt og i v e c o m b i n a t o r i a lp r o o f so fl o g - c o n v e x i t ya n dl o g - c o n c a v i t yo fs e q u e n c e s ，a sw e l la sq - l o g - c o n v e x i t y a n dq - l o g - c o n c a v i t y w eo b t a i ns o m en e wl i n e a rt r a n s f o r m a t i o np r e s e r v i n gt h el o g - c o n v e x i t y i nt h ef i r s tc h a p t e r ，w er e v i e ws e v e r i a lb a s i cd e f i n i t i o n sa n dr e s u l t so nt h el o g - c o n v e x i t y a n dl o g - c o n c a v i t y i nt h es e c o n dc h a p t e r ，w eg i v es o m ec o m b i n a t o r i a lp r o o fo fl o g - c o n v e x i t ya n dl o g - c o n c a v i t y o fs o m ec o m b i n a t o r i a ln u m b e r sb yl a t t i c ep a t h s ，d y c kp a t h sa n dt h er e f l e c t i o np r i n c i p l e i n s e c t i o n2 1 ，w ep r o v i d et h ec o m b i n a t o r i a lp r o o f so fs o m 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 e l a r g es c h r 6 d e rn u m b e r s ，t h ec e n t r a ld e l a n n o yn u m b e r sa n dt h ef i n en u m b e r s i ns e c t i o n2 2 ，w e p r o v e t h e l o g - c o n c a v i t y o f t h e d e l a n n o y n u m b e r s a n d p r e s e n t t h e g e n e r a l i z a t i o no f t h ec o n j e c t u r e o fs i m i o n i nt h et h i r dc h a p t e r ，w eg i v es o m eq - l o g - c o n v e xa n dq - l o g - c o n c a v er e s u l t sa n ds o m en e w l i n e a rt r a n s f o r m a t i o n sp r e s e r v i n gl o g - c o n v e x i t y k e y w o r d s ：l a t t i c ep a t h s ；l o g - c o n v e x i t y ；l o g - c o n c a v i t y ；q - l o g - c o n v e x i t y ；q - l o g - c o n c a v - i t y i i 独创性说明 作者郑重声明：本硕士学位论文是我个人在导师指导下进行的 研究工作及取得研究成果。尽我所知，除了文中特别加以标注和致 谢的地方外，论文中不包含其他人已经发表或撰写的研究成果，也 不包含为获得大连理工大学或其他单位的学位或证书所使用过的材 料。与我一同工作的同志对本研究所做的贡献均已在论文中做了明 确的说明并表示了谢意。 作者签名：吐! 篁蔓日期：2 型：塑 大连理工大学硕士学位论文 大连理工大学学位论文版权使用授权书 本学位论文作者及指导教师完全了解呔连理工大学硕士、博士学位论文版权使用 规定”，同意大连理工大学保留并向国家有关部门或机构送交学位论文的复印件和电子 版，允许论文被查阅和借阅本人授权大连理工大学可以将本学位论文的全部或部分内 容编入有关数据库进行检索，也可采用影印、缩印或扫描等复制手段保存和汇编学位论 文 作者签名： 导师签名： 咀堕垃 互差 2 一年月苴日2 碰年月苴日 大连理工大学硬士学位论文 1 绪论 本章为后续各章作准备着重介绍对数凸性和对数凹性研究的发展情况及所研究问 题的背景、目前的发展状况，而后简单叙述本文所需要的概念及术语 1 1 引言 对数凸性和对数凹性的研究对了解组合序列的分布是有益的，这是获得组合不等式 的丰富源泉i l l 】，而且在统计中特别有用具有对数凸性或对数凹性的序列也经常出现在 其它学科，比如，代数学，分析学，几何学，计算机科学和概率统计学通常证明一个 序列具有对数凸性或对数凹性是一件十分困难的事情，因为它要使用精密且精深的数学 工具这些数学工具的数量和种类有很多例如，经典分析学【1 3 9 1 ，线性代数学f 3 4 ，2 8 】， l i e 代数表示论f 酬，代数几何学，以及t o t a lp o s i t i 、，i 妙( 7 r p ) 理论【8 】等等相关问题， 技巧和方法觅s t a n l e y 的关于对数凹性的综述文献【删和b r e n t i 的补充文献【8 ，以及l i u 和w a n g 的关于对数凸性的综述文献 2 8 】 这篇文章主要的数学工具是格路s g m o h a n t y 的著作l a t t i c ep a t hc o u n t i n ga n d a p p l i c a t i o n s 3 1 】系统地介绍了格路的计数及其应用在解决概率统计和组合计数问题 时，格路提供了一个有用且初等的工具例如，利用格路可以解决b e r t r a n d 在1 8 8 7 年提 出的投票问题f l l 】1 9 8 5 年i g e s s e l 和g v i e n n o t 在 2 0 中用非交格路给二项式矩阵的 子矩阵一个组合解释他们的这些工作奠定了用格路解决对数凸性和对数凹性问题的基 础 1 9 9 2 年，b s a g a n 3 5 1 证明了q - 二项式系数和q - s t r f l i n g 数的q - 对数凹性，这里他用 的工具就是格路1 9 9 4 年，r s i m i o n 在研究组合统计时提出了关于格路的著名的s i m i o n 猜想f 3 8 】在f 2 3 1 中，h i l d e b r a n d 通过复杂的计数技巧证明了特殊情况下的s i m i o n 猜想 最近，h i l d e b r a n d 2 3 1 ，y w a n g 4 7 】以及m b 6 n a 和b s a g a u 5 1 分别证明了一般的s i m i o n 猜想格路也可以应用于证明单峰性，例如，b s a g a n 在 3 7 1 中利用它给出了二项式系 数的单峰性个简单的组合证明 在 2 8 】中，l i u 和w a n g 提出丁关于对数凸性的组合证明的问题，本文解决了该问 题的一部分在第二章和第三章中，我们将用格路，d y e k 路和反射原理给出一些组合数 的对数凸性或对数凹性组合证明，及其相应的哥对数凸性和铲对数凹性这些数包括 d e t a n n o y 数，大s c h r s d e r 数，小s c h r & i e r 数。c a t a l a n 数，m o t z k i n 数，f i n e 数等 一些组合数的对数凸性和对数凹性的组合证明 1 2 对数凸和对数凹的研究概况 这一节将介绍对数凸性和对数凹性的研究概况以及研究这个问题的一般性工具 我们首先介绍几个定义对于非负序列 ) o = n o ，a ，) ，简写为 n ) ，如果对 所有的1 ，均有不等式2 a 女口一1 + 。k + 1 ( 2 a 女o k 一1 + a k + 1 ) 成立，则称此序列是凸 的( 凹的) ；如果对所有的k 1 ，均有不等式2 口k l a k + 1 ( 口2 o , k 一1 a k + 1 ) 成立，则称 此序列是对数凸的( 对数凹的) ；如果存在非负数m 使得当k m 时，n 是递增的，而 当m 时，a k 是递减的，则称此序列是单峰的如果此序列无内部零点( 即不存在 i j 砭瓣了2 1 瓦矿 ( 1 1 ) 但是，在组合序列中，大部分的序列都没有二项式系数那样简单的计数公式例如第_ = 类s t r i l i n g 数 5 3 】 附，= 塞c 妒高眠剐， 因此关于序列对数凸性和对数凹性问题的研究显得十分困难 1 9 8 9 年r s t a n l e y 在 4 3 】 中对这个问题作了系统的阐述，他具体介绍了研究序列对数凹性的一般性方法，如经典 分析，代数几何，t p 理论等在众多的方法中，利用n e w t o n 不等式【4 3 l 解决有限序列 的对数凹性是一种经典方法 n e w t o n 不等式设 赳 o 0 是无限矩阵若a 的所有予矩阵的行列式均大于 2 大连理工大学硕士学位论文 等于零，则称a 是t p 矩阵设a o ，0 1 ，a 2 ，是无限非负序列，如果它的t o e p l i t z 矩阵 ，印 ，、1 0 ( 吩一) 啦o2 lo 是t p 矩阵，其中当 0 时，a k = 0 ，则称此无限序列为p 6 1 y a f r e q u e n c y 序列，简称p f 序列通常称一个有限序列a o ，n 1 ，a n 为p f 序列，即称无限序列n o ，o - ，a 。，0 ，0 ， 是p f 序列如果a o ，n 1 ，是p f 序列，那么它的t o e p l i t z 矩阵( 啦一j ) j o 的2 阶子矩 阵的行列式都是非负的，如 啦 啦+ 1 l ：n ? 一啦一1 。l + l o 啦一1 啦 所以此序列一定是对数凹的 a s s s e n s c h o e n b e r g - w h i t n e y 定理把有限p f 序列和仅有实 零点的多项式紧密的联系在一起关于t p 矩阵和p f 序列的其它结果可参见f 2 5 1 a i s s e n - s c h o e n b e r g - w 1 n i t n e y 定理吼有限非负序列a o ，a 1 ，a n 是p f 序列的充要条 件是它的发生函数b no 砚一仅有实零点 我们注意到p f 序列比对数凹序列具有更好的性质有时我们仅对序列的对数凹性 感兴趣，但我们可以通过证明此序列的p f 性间接地研究它的对数凹性组合数学中已 经有很多对数凹序列被证实具有p f 性例如，二项式系数( ；) 和第一类无符号s t i r r i n g 数c ( n ，k ) 的发生函数分别为 + 1 ) n 和。白十1 ) 扛+ 2 ) 扛+ n 一1 ) ，因此它们都是p f 序 列在 2 2 ，1 l 】中，h a r p e r 和c o m t e t 分别证明了第二类s t i f l i n g 数和e u l e r i a n 数的p f 性 质最近，w a n g 和y e h 【4 9 】用一种统一的方法证明了这些数的p f 性质关于p f 性和 对数凹性之间关系的其它结果可参见f b r e n t i 的博士论文嗍，他最早将t p 理论引入到 对数凹性问题的研究 在8 1 中，f b r e n t i 考虑了保持对数凹性不变的线性变换我们称线性变换 匈= 。( n ，i ) i = 0 是p l c ( p r e s e r v i n gl o g - c o n c a v i t y ) ，如果它能保持对数凹性即，协) 的对数凹性蕴涵着 ) 的对数凹性到目前为止，已经发现了一些重要的线性变换具有p l c 性质例如 = 砉( 拈一，m n 。， f b r e n t i 主要是利用p f 序列【8 】的性质来证明线性变换的p l c 性质 引理f 50 】设，0 1 ，和弱，墨，墨满足下列条件t 3 一些组合数的对数凸性和对数凹性的组合证明 ( i ) 怎，a k 0 ，0 r n ； ( i i ) 0 s x o ，s x ls s 那么n - o a k x k x o 诂o a k 0 2 0 0 3 年，y w a n g 在 4 8 中利用a b e l 变换得到的“引理”给出了证明线性变换的 p l c 性质的一般性方法令a 。= 舞一一1 + 1 ，即 小酗棚z 卜2 匿nc n - 1 , i k 匿n c n + l , i b -2 【吾“m 叫一匡n c扣j 匿“b j - 那么为了证明线性变换( 1 2 ) 的p l c 性质，只需要证明a 。0 我们利用 x 4 的对数凹 性注意到 矗) 是对数凹的充要条件是 z l 一1 + 1 2 ；i x j j i 1 那么把x i x j 的下标之和i + j 作为权，则有相同权的町是可比较的令& 是a 。中权 为t 的项之和，且记吼( t ) 是。的项筑z “前的系数，其中0 i 5l t 2 j ，则 2 n l t 2 j a 。= 岛和s t = 哦( n ，t ) z z “ t = 0 i = 0 因此a 。0 的充分条件是对于所有的0 t s2 n ，有s t 20 成立又由于 0 s 知5x l x t 一1s3 ；2 0 t 一2 s 根据a b e l 变换，我们得到& o 的充分条件是对所有的0 r t 2 j ，有掣啦( n ，t ) 0 成立根据上面的讨论，我们将在3 2 节中证明线性变换( 1 3 ) 具有p l c 性2 0 0 6 年， w a n g 和y e h 在 5 0 中进一步定义了双p l c 线性变换如果线性变换 n = n ( n ，i ) 缸而 n = 0 ，l ，2 ，r t i = o 可以保持对数凹性，则称此线性变换是双p l c ( d o u b l ep l c ) ，即由 z 。) 和 ) 的对数凹 性可以推出 ) 的对数凹性例如，线性变换( 1 3 ) 也是双p l c 【50 1 显然线性变换的 p l c 性质是双p l c 性质的特殊情况 由于我们是基于组合背景研究序列的对数凹性和对数凸性，因此我们希望给序列的 对效凹性和对数凸性一些组合解释一般情况下，非负序列a o ，a l ，的组合意义是存 在集合序列岛，研，使得l 鼠l = 啦，其中 _ 0 ，1 ，n ，且i & l 表示集合鼠的基数 因此，如果能构造一个单射 咖：一1 s j + 1 + s ， 那么这个单射就是序列 o k ) o 坯。对数凹性的组合解释( 即组合证明) 我们给序列( 1 1 ) 对数凹性个简单的组合证明【4 3 j 设瓯是集合 n 】= 1 ，2 ，n ) 的k 元子集的簇，则 4 大连理工大学硕士学位论文 i & i = ( ：) 设x 为集合m 的任意子集，定义墨，= x n 吼考虑( a ，b ) s k 一1 鼠+ 1 令 j 是满足l 山i = l 岛| - 1 的最大整数定义妒( ，b ) = ( g ，d ) ，这里c = a ju ( b b ) 且 d = 马u ( a a j ) 容易验证庐是单射这就给出序列( 1 1 ) 对数凹性一个组合证明( 在第 二章中我们将给出另外一种组合证明) 我们知道同一个序列可以有多种不同的组合意义例如r s t a n l e y 在4 2 1 和他的m i t 主页1 中就给著名的c a t a n 数上百种组合解释因此这类序列对数凹性和对数凸性一 定有不同的组合证明那么我们可以适当地选择序列的组合解释，然后用组合方法系统 地证明序列的对数凸性和对数他凹性，但是，事实上这很难实现田，3 5 】在第二章中我们 将用格路系统地证明某些重要的组合序列的对数凹性和对数凸性 相对于对数凹性，关于对数凸性的文献很少但是在某些方面，对数凸性具有比对 数凹性更优美的性质例如 瑚，给定两个对数凸序列 $ 。) 和 鼽) ，则我们从对数凸的定 义直接得到它们之和的序列 + 鼽 仍是对数凸的但是，在一般情况下，对数凹性不 具有此性质通过前一部分的讨论可以发现，通常我们可以借助序列的p f 性间接研究 序列的对数凹性但是，到目前为至，没有发现类似于p f 性的研究对数凸性的方法 根据序列的凹性和对数凹性的定义，我们也可以通过凹性来研究对数凹性但是序列对 数凸性的研究并不能借助于序列的凸性，因为对数凸性比凸性强，即如果一个序列是对 数凸的，那么它一定是凸的因此，对数凸性的研究比对数凹性更具有挑战另外，在 组合数学中，很多著名的序列具有对数凸性，如c a t a l a n 数和m o t z k i n 数等这些数的对 数凸性的代数证明参见【2 剐在 17 】中，d o , r i d ，s v r t a n b 和v e l j a n b 基于生物学背景( t h e s e c o n d a r ys t r u c t u r eo fr n a ) 用分析的方法证明了c a t a l a n 数和m o t z k i n 数的对数凸性 l i u 和w a n g 唧】介绍了和对数凹相对应的性质一保持对数凸性的线性变换和q 一对数凸 性，并且给出了满足某类三项递归关系序列对数凸性的判定定理 1 3 定义和符号 为避免后文叙述繁琐，这里先介绍一些重要的定义和常用符号( 若无特别声明，这些 符号适用于全文) 设z 2 = ( t ，j ) ： ，j z ) 是二维整数格点( i n t e g e rl a t t i c ep o i n t ) 的集合如果对于所有 的0 k n ，都有m z 2 成立，则称点序列p = p o ，p 2 ，为路( p a t h ) p o 称为p 的起 点，肌称为p 的终点例如， p = ( 0 ，0 ) ，( 1 ，1 ) ，( 2 ，1 ) ，( 3 ，1 ) ，( 3 ，2 ) ，( 4 ，2 ) ，( 5 ，3 ) ，( 5 ，4 ) ，( 5 ，5 ) ( 见f i g 1 1 ) 如果路p 的终点和路口的起点重合，那么p q 表示路p 和路g 的连接路也 经常用步( s t e p s ) 来描述，它的第i 步就是从a 一1 到p l 的向量我们把向量的坐标放入方 括号以区别路中的格点元素的圆括号如果使用e = 1 ，0 ，n = 0 ，1 】以及d = 1 ，1 】表示 向东( e t ) ，向北( n o r t h ) 和对角( d i a g o n a l ) 的单位步那么f i g 1 1 中的路p 可以被写成 1 h t t p ：w w w - m a t h m i t e d u 。r s t a u 5 一 = 些墨金墼她鱼垡塑壁墼翌丝堕丝全堡塑 d e e n e d n n 的形式 ( 1 a t t i c ep a t h ) ， 如果一条路由向东步e 和向北步组成，那么称这条路为格路 ( 0 ，0 ) f i g 1 1 如果在第一象限内从( i ，0 ) 到a + 锋，o ) 的路是由向上( r i s e ) 步r = 1 ，1 】和向下( t a n ) 步f = 1 1 ，一1 组成，那么称此路为d y c k 路( d y c kp a t h ) 例如， ( 见f i g 1 2 ) p = ( 0 ，o ) ，( 1 ，1 ) ，( 2 ，2 ) ，( 3 ，1 ) ，( 4 ，o ) ，( 5 ，1 ) ，( 6 ，0 ) ( 0 ，0 ) x , z f i g 1 2 显然f i g 1 2 中的d y c k 路可被写成r r f f r f d y c k 路中点的高度是该点的纵坐标与起 点的纵坐标之差如果d y c k 路中有一段是r f ，则称这段为山峰( p e a k ) ，其中r 步和f 步的交点称为峰点；连接峰点的最大连续的r 步序列称为这个山峰的上坡( a s c e n t ) ；连接 峰点的最大连续的f 步序列称为这个山峰的下坡( d e s c e n t ) 如果d y c k 路中有一段为f r ， 则称这段为山谷( v a l l e y ) 例如，在f i g 1 2 中d y c k 路p 有两个山峰，一个山谷，其中第 一个( 从左向右) 峰点的高度为2 ，第二个山峰的上坡为r 设g 是平面内的一条直线，q = q o ，q 2 ，q n 是z 2 中的路则口关于z 作反射形成的 格路有如下形式t q l = 矗，区，吐， 其中是q l 关于直线l 的反射，称q l 为q 关于的反射例如，如果q 是f i g 1 1 中 的路p 且直线是y = ，那么q 7 = d n n e n d e e ( 见f i g 1 3 ) ( 0 ，0 ) f 逗1 3 6 大连理工大学硕士学位论文 符号约定 1 ( 二) 表示二项式系数； 2 1 s l 表示集合s 的基数； 3 h 表示小于等于n 的最大整数，如 2 6 j = 2 ； 4 m 表示集合 1 ，2 ，n ) ； 5 定理，引理，命题，推论的编号方法为：如定理2 3 表示第二章的第三个定理，其余 类推； 6 图形的编号方法：如f i g 2 3 b 表示第二章的第三幅图中的b 图； 7 s l o a n e sa 0 0 6 3 1 8 表示s l o a n e 在其主页2 上给c a t a l a n 数的编号，此网页上s l o a n e 收 集了很多与c a t a l a n 数相关的性质及文献其它的类似 2 h t t p ：w w w r e s e a r c h a t t c o r n 一n j a s s e q u e a c e s 7 大连理工大学硕士学位论文 2 对数凸性和对数凹性 本章我们将利用格路，d y c k 路和反射原理系统地讨论序列的对数凸性和对数凹性 问题 2 1 对数凸性 本节主要给出一些数的对数凸性的组合证明，这些数包括c a t a l a n 数，大s c h r s d e r 数，中心：项式系数，中心d e a n n o y 数，m o t z k i n 数，小s c h r s d e r 数和f i n e 数 2 1 1 c a t a l a n 数和大s c h r 6 d e r 数 设只是从点( i ，t ) 到点+ t ，n + i ) 带有对角步d 的格路p 的集合，其中p 只在 对角线y = z 的下方我们称这类路为s c h r s d e r 路吼当i = 0 时，1 只。( o ) i 就是我们熟 知的大s c h r s d e r 数当i 芝00 0 ) 时，只。( i ) 是只( o ) 向右上( 左下) 方移动t 个对角 步d 因此，对任意固定的t ，有r n = 1 只。( ) | t 在 4 1 ，e x e r c i s e s6 3 9 中，s t a n l e y 列出了大 s c h r s d e r 数十多种组合解释下面是这个序列的前几项 r n ) 。o = 1 ，2 ，6 ，2 2 ，9 0 ，3 9 4 ，1 8 0 6 ，) ( s l o a n e sa 0 0 6 3 1 8 ) 大s c h r s d e r 数的发生函数为一1 2 二r n t ”= 击( 1 一t 一、l 一6 t + t 2 ) n 0 一 关于大s c h r s d e r 数的结论参见【7 ，4 2 ，5 1 ，l o 设( t ) 是从点( i ，i ) 到点+ i ，n + i ) 的格路p 的集合，其中p 只在对角线y = z 的 下方我们称这类格路为c a t a l a n 路，则( t ) 可看作是只的子集它们的计数就是 c a t a l a n 数= i ( i ) i = 再箝( 劲，其中n 0 c a t a l a n 数是十分迷人的组合计数至今， 人们已经给出它上百种组合解释( 见s t a n l e y 4 1 ，e x e r c i s e s6 1 9 和他的i v i t 主页) c a t a l a n 数也可用d y c k 路解释，即从( 0 ，0 ) 到( 2 n ，0 ) d y c k 路的计数( 这与第三章中的n a r a y a n a 数 有关) 下面是c a t a l a n 数的前几项 g ) 。! o = l ，1 ，2 ，5 ，1 4 ，4 2 ，1 3 2 ) ( s l o a n e sa 0 0 0 1 0 6 ) 它的发生函数为 缈= 警 n 0 一 9 一些组合数的对数凸性和对数凹性的组合证明 大s c h r s d e r 数和c a t a l a n 数的关系不仅仅局限在组合意义上，在计数关系上更加紧密 在睁1 l 中，j w e s t 用组合方法证明了h = ；：o ( “n + - h k ) ”k 由于c a t a l a n 数对数凸性的组 合证明和大s c h r s d e r 数的类似，我们仅仅给出后者的组合证明，它们对数凸性的代数证 明参见 2 8 定理2 1 大s c h r s d e r 数序列 ) 畦。是对数凸的 证明：为了证明 h ) 。o 的对数凸性，只需证明如下映射为单射 妒：。夕；( o ) 4 ( 1 ) + 。+ l ( o ) 。，一1 ( 1 ) 考虑一对s c h r s d e r 路( p ，g ) 只( o ) 只。( 1 ) ，显然p 和q 相交设第一个( 从左下方) 交点 为c 那么c 分别把p 和q 分割成p l ，p 2 和q l ，啦令p l = p 1 9 2 和q 7 = q z p 2 ，则p ，只汁1 ( o ) 和口一1 ( 1 ) 定义妒( p ，口) = ，q ，) 所以妒的像由，9 7 ) 咒+ 1 ( o ) 只。一l ( 1 ) 组成，其 中p 和口7 相交如果妒0 ，q ) = ，一) ，则我们可以用相同的方法把，一) 返回到0 ，口) 所 以妒是单射例如，f i g 2 1 ( 以后我们规定p 为实线，q 为虚线，且和r 作类似规定) ( 0 ，0 ) 证毕 命题2 1 c a t a a n 数序列 q ) 。o 是对数凸的 我们可以从c a t a l a n 数的计数公式直接得到它的对数凸性证明又由于c a t a l a n 数的 组合察释类似于大s c h r s d e r 数，因此它的对数凸性的组合证明类似于定理2 1 的证明， 具体的证明过程参见【2 8 2 1 2 中心二项式系数和中心d e l a n n o y 数 十九世纪后期，h d e l a n n o y 【1 2 】引进了d e l a n n o y 递归关系 d ( ，k ) = d ( n ，k 一1 ) + d ( n 一1 ，k 一1 ) + d ( n 一1 ，k ) 其中d ( o ，0 ) = 1 ，且当i r 时令= o 假设 1 k ，且r n 令玩，k ( i ，j ，a ) 表示留n ，t ( t ，j ) 中所有不进入左上 角a 的f e r r e t s 图的格路的集合当a l k 或者r n 时，容易看出级k ( t j ， ) 是空集； 当a = ( 0 ) 时，显然玩，k ( ，j ， ) = 豌，k ( i ，j ) 例如，当a = ( 5 ，3 ，1 ，1 ) 时，f i g 2 1 5 中的格 路p 掣瑰6 ( o ，0 ，a ) ，因为p 的第五步和第六步进入了a 的f e r r e r s 图 t 喜_ h j o * 拱糍i 鞭i i ! 粥! 拳= = 二：= = 二* 一 垂i 黼 * ；* 簟；j 巍j 4 - 记( k ， ) = i 瓯，k ( i ，j ，x ) l ，其中i 和j 是任意固定的整数在1 3 8 】中，s i m i o n 猜想对任 意正整数n 和分拆 ，序列 ( n ，0 ， ) ，n ( n 一1 ，1 ， ) ，( n 一2 ，2 ，a ) ，n ( 0 ，n ， ) 是单峰的这一猜想蕴涵着某些组合统计分布的单峰性显然上述序列无中间零点，因 此，只要证明它的对数凹性，就可以说明它的单峰性最近h i l d e b r a n d 2 4 1 ，w m a g ( 4 7 1 ，b t n a 和s a g a n 6 1 分别证明了它的对数凹性，其中定理2 6 的方法2 和定理2 7 的证明可以看 作是b 6 n 8 和s a g a nf 6 】证明s i m i o n 猜想方法的推广 类似于劈n k ( t ，j ， ) ，定义玩k ( i ，j ，a ) 表示，k ( i ，j ) 中所有不进入左上角入的f e r r e t s 图的d e l a n n o y 路的集合记d ( k ，a ) = l 鲰，k ( i ，j ，a ) i ，则下面的两个定理可看作是s i m i o n 猜想的推广 定理2 8 对于任意正整数n 和分拆a ，序列 d ( n ， ) h z o 是对数凹的 证明z 我们可以给出类似于定理2 6 方法2 的证明我们用吸，k ( i ，j ，a ) 代替方法2 中 玩k ( t ，j ) 我们仅需要注意p 和q 是第一对竖直距离为1 的点，从而吐不会进入 的 f e r r e t s 图因此q 7 = 口i 聊玩，( o ，一1 ，a ) 所以妒是单射例如，f i g 2 1 6 大连理工大学硕士学位论文 ( o ，一2 ) 0 ，面+ 。( o ，一2 ) 。0 ，争) f i g 2 1 6 证毕 定理2 9 对于任意正整数n 和分拆a ，序列d ( n ，0 ，a ) ，d 一1 ，1 ， ) ，d 一2 ，2 ，a ) ，d ( o ，a ) 是对数凹的 证明：我们可以给出类似于定理2 7 的证明我们用玩，( t ，j ， ) 代替定理2 7 证明中 玩，k ( i ，j ) 我们仅需要注意p 和q 是第一对竖直距离为1 的点，且和百是最后对水平距 离为一1 的点，从而酲和p ：均不会进入 的f e t t e r s 图因此口，= 西p 2 西玩( o ，一1 ， ) ，一= 西口卯；玩， ( o ，一1 ，a ) 所以妒是单射例如，f i g 2 1 7 ( 0 , - 2 、i q 证毕 。0 ，( 0 _ 2 ) 。0 ，j ) 。憎，口) ( ，d ) f i g 2 1 7 大连理工大学硬士学位论文 3q - 对数凸性和铲对数凹性 在这一章中，我们将介绍多项式序列的q 对数凸性和g - 对数凹性，并且证明一些多 项式序列具有q 一对数凸性或q - 对数凹性这些多项式包括tq - s c h r s d e r 数和q - d e l a n n o y 数我们也给出一些保对数凸性( 对数凹性) 的线性变换，并建立它们和q 一对数凸( 哥对 数凹) 之间的联系 设q 是未定元，且 矗( q ) ) 。o 是任意给定的关于q 的实多项式序列如果对所有的 n 1 ，a 一1 ( g ) 厶+ 1 ( g ) 一厶( g ) 2 的所有系数均为非负( 非正) 的，那么称序列 ( q ) ) 。o 是 q 一对数凸的旧对数凹的) 俨对效凹的定义主要是由s t a n l e yf 3 6 】引入具有哥对数凹性 的多项式序列有很多，例如q 一二项式系数。第类和第二类q - s t i f l i n g 数这些结论参见 s a g a n 3 5 ，3 6 】以及【2 7 ，3 2 】哥对数凸的定义是由l i u 和w a n g 2 8 】第一次引入如果序列 厶( q ) ) 。o 是q 对数凸的汀对数凹的) ，那么对于任意固定的正实数q ，序列 ( g ) ) 。o 是对数凸的( 对数凹的) 在通常情况下，反之不成立 例如【心，我们熟知阶乘n ! 是对数凸的，且( n ) 口f - i i k l ( ) 口是州的俨模拟( q - a n a l o g ) ， 其中( n ) g = 1 + q + q 2 + + q ”1 我们可以直接计算得到( n ) 。! 的哥对数凸性 3 1 q - 对数凸性 本节主要介绍q - s c h r & l e r 数和口- 中心d e l a m m y 数的口- 对数凸性，并给出一个新的 保对数凸线性变换 3 1 1 n a r a y a n a 数和q - s c h r s d e r 数 n a r a y a n a 数n ( n ，k ) 是从( 0 ，0 ) 到( 2 n ，0 ) 有k 个山峰的d y c k 路的计数根据这个定 义，我