广义置换与杨表

论文摘要

1968年Knuth提出了置换上模式避免的概念,并借助RSK算法证明了避免π模式的广义置换的个数等于Catalan数Cn,且不依赖于π ∈ S3的选择.直到,1985年,R.Simion和F.W.Schmidt才首次系统地研究了避免三长模式的置换,并首次给出了 Knuth的结果的一个双射证明.在随后的三四十年间,模式避免的概念被广泛关注和研究,大量的研究成果被发表.2003年,在新西兰的奥塔哥大学举办了首届”Permutation Patterns”年会.这篇文章主要是借助杨表理论研究了广义置换中的模式避免.本论文的主要内容分成三个部分.第一部分主要研究广义置换上的模式避免.第二部分主要考虑修正的RSK对应及其应用.最后一部分则是关于避免321模式的置换的逆序数.在第三章中,我们对集合和重集上置换的模式避免的概念进行推广,首次定义并研究了广义置换上的模式避免.借助杨表理论中经典的RSK算法,证明了Sαβ中避免π模式的广义置换的个数等于Kostka数K（N,N）（α,β）,不依赖于π∈S3的选择,且与拆分α和β中的元素的排列顺序无关.延伸Dyck路和Riordan路的概念,我们定义了 Catalan-Riordan路.并证明了（n,k）型的Catalan-Riordan路的个数等于形状为（N,N）,型为（12k,2n-K）的半标准杨表的个数,亦等于避免任意π∈S3模式的（1mi,2n1）→（12k-m1,2n2）的广义置换的个数.作为应用,对Motzkin数和Riordan数给出了两个新的组合解释,分别是利用两行的矩形半标准杨表和避免π ∈ S3 模式的广义置换.在第四章中,我们研究了 Lewis的修正的RSK对应.首先,我们推广了 Lewis的双射.对任意给定的α=（α1,...,αn）∈{k,k+1},我们构造了Sα（1N）k+2与形状为（（k:+1）n的标准杨表的集合的双射.继而得到|Sα（1N）k+2|=f（k+1）n）不依赖于α中k的位置和个数.然后,我们将Lewis的方法由标准杨表延伸到了半标准杨表上,建立了广义置换与方形半标准杨表之间的双射,由此对一系列已知结论做出了新的证明.作为应用,我们给出了一些与Catalan数和Kostka数相关的恒等式.在第五章中,我们研究了避免321模式的置换上的逆序数.通过构造所有避免321模式的n长置换与长度为2n的Dyck路集之间的一个双射,我们给出了避免321模式且恰有m个逆序数的n长置换的计数公式.最后,我们给出了三类还值得继续研究的问题.第一类是构造双射,证明任意的π,π’在广义置换Sαβ中是Wilf-等价的.第二问题是确定任意的Π（?）S3在广义置换中的Wilf-等价类.第三类问题是研究广义置换上的统计量.

论文目录

• 摘要
• Abstract
• 第1章 绪论
•   1.1 基本概念与常用符号
•     1.1.1 广义置换与模式避免
•     1.1.2 杨表与RSK对应
•     1.1.3 置换上的统计量
•   1.2 研究背景及现状
•   1.3 主要研究内容
•     1.3.1 广义置换上的模式避免
•     1.3.2 修正的RSK对应
•     1.3.3 避免321模式的置换的逆序数
•   1.4 本文的结构安排
• 第2章 预备知识
•   2.1 Kostka数的性质与计算
•   2.2 行嵌入与RSK对应的性质
•     2.2.1 行嵌入
•     2.2.2 RSK对应
• 第3章 广义置换上的模式避免
•   3.1 引言
•   3.2 3长置换模式的Wilf等价
•   3.3 Catalan-Riordan格路
•   3.4 补充说明
• 第4章 模式避免与修正的RSK对应
•   4.1 引言
•   4.2 Lewis构造的延伸
•     4.2.1 Lewis构造
•     4.2.2 第一次延伸: 块递增置换
•     4.2.3 第二次延伸: 广义置换
•   4.3 应用
•     4.3.1 与Catalan数相关的恒等式
•     4.3.2 与Kostka数相关的恒等式
• 第5章 避免321模式的置换的逆序数
•   5.1 引言
•   5.2 避免321模式的置换的逆序数
• 结论
• 参考文献
• 致谢
• 附录 （攻读学位期间所发表和投稿论文目录）

文章来源

类型: 博士论文

作者: 梅周胜

导师: 彭岳建,王岁杰

关键词: 模式避免,逆序数,广义置换,对应,杨表

来源: 湖南大学

年度: 2019

分类: 基础科学

专业: 数学

单位: 湖南大学

基金: 湖南省研究生科研创新项目

分类号: O144

DOI: 10.27135/d.cnki.ghudu.2019.002187

总页数: 76

文件大小: 557K

下载量: 9