组合变换在等式、多项式及简单图中的应用

来源 :南开大学 | 被引量 : 1次 | 上传用户:richieli333
下载到本地 , 更方便阅读
声明 : 本文档内容版权归属内容提供方 , 如果您对本文有版权争议 , 可与客服联系进行内容授权或下架
论文部分内容阅读
利用组合方法给出某些数学问题简洁直观的证明是组合数学研究的热点课题。其本质就是构造组合结构,寻找适当的组合变换。在本文中,一方面,我们将这种方法应用于两个等式,即Simons等式和Munarini等式,给出了这两个等式的组合解释。进一步地,在Munarini等式的证明过程中涉及的组合技巧也可用于证明Boros-Moll多项式系数的正性。另一方面,作为组合变换的另一个应用,本文证明了一类简单图中交叉数和嵌套数是对称联合分布的。   Simons等式是Simons通过重复求导得到的一个关于二项式系数的等式。对该等式的证明包括Chapman给出的生成函数法,Prodinger给出的柯西积分公式法以及Wang和Sun给出的算子法。Hirschhorn指出Simons等式实际上是定义在超几何级数2F1上的Pfaff等式的一种特殊情况。而对于Pfaff等式的组合证明,Labelle和Yeh在他们的文章中已经给出。本文通过构造两种赋权组合结构上的组合变换,即赋权自由Dyck路和赋权自由Schroder路上的组合变换,给出了Simons等式另一种更加形象直观的组合解释。   依照Prodinger的方法,Munarini得到了Simons等式的一般化形式,称之为Munarini等式,该等式同时也足Pfaff等式的一般化形式。对Munarini等式的某些特殊情况,Shattuck给出了基本的双射证明。应用Labelle和Yeh在证明Pfaff等式过程中的技巧,我们给出了Munarini等式的组合解释。   本文还给出了Boros-Moll多项式系数正性的组合证明。Boros-Moll多项式足在求一个四次积分的过程中产生的,它与一类特殊的Jacobi多项式密切相关。Amdeberhan和Moll给出了有关该多项式表达式多种不同的证明。Boros和Moll曾经给出该多项式系数正性的证明,但他们的证明是借助Ramanujan基本定理实现的。此外,Boros-Moll多项式系数序列还有其它组合性质,如单峰性和对数凹性。利用组合方法来诠释这些性质已成为组合学中一个有趣的研究方向。   研究一类简单图中交叉数和嵌套数的对称联合分布问题是该论文中组合变换的另一个应用。1983年,De Sainte-Catherineit明了在集合[2n]的所有匹配中,2-交叉和2v嵌套是等分布的。之后,Klazar推广了该结论,证明了含有r个2-交叉、s个2-嵌套的匹配的个数等于含有r个2-嵌套、s个2-交叉的匹配的个数。近来,关于图中交叉和嵌套的对称联合分布问题又重新引起了广大学者的研究兴趣。2007年,以RSK算法为基础,Chen等证明了在集合[n]的所有划分或集合[2n]的所有匹配中,交叉数和嵌套数是对称联合分布的。同时,通过考虑Fevers图表的填充方式,Krattenthaler也证明了这一结论。本文通过构造一种新的算法,即改进的RSK算法,推广了该结论。   在本篇论文中,我们主要讨论组合变换在两类问题中的应用。其中之一是给出Simons等式、Munarini等式以及Boros-Moll多项式系数正性的组合解释。另一个是证明在每个点左度都不超过1的简单图中,交叉数和嵌套数是对称联合分布的。我们主要得到了以下两个方面的结果。   本文的第二章论述了我们的第一个结果,也就足组合地解释了Simons等式、Munarini等式以及Boros-Moll多项式系数的正性。对于Simons等式,其组合变换是以自由Dyck路、自由Schroder路以及在赋权自由Schroder路上的一个对合为基础的。而对于Munarini等式和Boros-Moll多项式系数的正性,其组合变换是以Foata和Labelle给出的一个关于Meixner endofunctions和双色排列的对应,以及Labelle和Yeh用于证明Pfaff等式的方法为基础的。   本文的第三、四章阐述了我们的第二个主要结论。在第三章中,我们给出了一个改进的RSK算法。利用此算法,我们构造了某个有序集合上的字ω与存在限制条件的有序杨表对(P(ω),Q(ω))之间的一个一一对应。此外,在本章中我们还证明了以下结论:ω的最长递增子序列的长度等于P(ω)的列数;ω的最长递减子序列的长度等于P(ω)的行数。   以第三章中改进的RSK算法为基础,在第四章中,我们主要证明了在每个点左度都不超过1的简单图中,交叉数和嵌套数是对称联合分布的。这个问题是通过构造每个点左度都不超过1的简单图和空型的有效徘徊杨表之间的双射得以解决的。事实上,对于每个点左度都不超过1的简单图构成的图类,如果固定左端点和右端点集合,我们的结论仍然成立。
其他文献
在数学里面,傅立叶分析和傅立叶变换已经发展了很长一段时间。傅立叶分析有很多的科学应用,例如在物理学,偏微分方程,数论,密码学,数值分析,光学,几何以及其他的领域。稳定态逼近是渐
压缩感知是近年来所研究的一种关于信号传输的新的理论,信号的稀疏表示、编码测量和重构算法等构成了压缩感知理论主要的三个方面.信号的稀疏表示为压缩感知的先决条件,即满足
1940年,Turan首先将极图理论作为一个学科来研究,Paul Erdos进而推动了这一理论的发展。自此,极图理论成为图论的一个重要分支。在极图理论里,我们所感兴趣的是图的各种不变量之
机器排序和机器覆盖经常在实际运用中出现,比如在网络通信中通道分配均衡问题,大型的并行计算问题,柔性生产系统中任务排序问题,等等.这篇论文主要研究了m台平行机的复合半在线排
约束矩阵方程问题是指在满足一定约束条件下的矩阵集合中求矩阵方程的解。约束条件不同,或矩阵方程不同,则得到不同的约束矩阵方程问题。 约束矩阵方程问题在结构设计、参数
本文主要研究乘子算子T与局部可积函数所生成的多线性交换子Tb的有界性问题。 首先,证明了多线性乘子交换子Tb的Sharp函数估计,并得到了该多线性交换子的Lp(w)(1<P<∞)有界性,
为筛选利用武夷山优质种质资源,促进品种结构调整,对武夷山留兰香、向天梅、醉贵妃、胭脂柳四个单枞进行植物学性状观察及主要生化成分分析。结果表明:留兰香、向天梅、醉贵
本文主要研究特殊三角剖分下二元样条函数空间的局部基和维数问题.一,利用Wang-型加密三角剖分?W下二元五次C2样条函数空间S52(?W)的Hermite插值条件,构造出空间S 52(?W)的一
为了气化缓斜和倾斜薄煤层,可采用本文作者提出的新工艺系统,其系统的本质用图1~3说明。第一,通过垂直鼓吹排瓦斯钻孔气化煤层,其钻进成本比钻进倾斜导向钻孔低的很多。第二,
全局的学习算法是对所有的训练样本构造一个模型来预测任何一个未知点的标记,而局部学习算法旨在某个给定点的邻域中构造算法,不同的测试点可能构造不同的算法模型。在某些情况