学位论文 > 优秀研究生学位论文题录展示

Dyck路，Motzkin路和Schr(?)der路上峰的计数

作　者: 丁云
导　师: 杜若霞
学　校: 华东师范大学
专　业: 运筹学与控制论
关键词: 格路径 Dyck路 Motzkin路 Schr(o ¨)der路峰标准杨表 RSK算法
分类号: O157
类　型: 硕士论文
年　份: 2011年
下　载: 15次
引　用: 0次
阅　读: 论文下载

内容摘要

Dyck路,Motzkin路和Schroder路等格路径作为一类重要的组合结构是近年来计数组合学研究的一个热点.它们与树,有禁排列,正交多项式,连分式等其它结构联系紧密,并且在统计学,随机过程及生物信息学等领域有着广泛应用.在本文中我们主要研究了这三种格路径上的统计量：峰的个数A. Regev在[16]中利用递推关系通过大量的计算给出了Motzkin路上的峰的个数,并发现n阶广义Motzkin路的个数等于所有n阶的Motzkin路上的峰的个数的两倍加一,并提出公开问题,即寻找这一问题的双射证明.本文的主要结果就是构造了一个双射从而解决了A. Regev提出的问题.利用这一双射我们给出了Dyck路,Motzkin路和Schroder路上峰的个数,以及Narayana数的一个新的证明.另外通过用两种不同的方法计数广义Schroder路的个数,我们还得到了一个有趣的组合恒等式.这个等式即为[21]中第115页习题3(g)等式的变形.本文的另一个主要结果就是利用RSK算法,给出了Motzkin路和行数不超过3的标准杨表之间的一个双射.

全文目录

摘要  6-7
ABSTRACT  7-10
1 引言  10-14
  1.1 Motzkin路的概念  10-11
  1.2 研究背景和意义  11-12
  1.3 本文研究结构  12-14
2 常见格路径及相关组合结构  14-22
  2.1 相关概念  14-16
  2.2 Motzkin路及Motzkin数  16-18
  2.3 Dyck路和Catalan数  18-19
  2.4 Schroder路与Schroder数  19-22
3 Motzkin路上的峰  22-28
  3.1 峰的概念  22-23
  3.2 双射φ:PM_n→SM~0_n  23-26
  3.3 Motzkin路上的峰的个数  26-28
4 Dyck路与Schroder路上的峰  28-35
  4.1 Dyck路上的峰  28-32
  4.2 Schroder路上的峰  32-35
5 Motzkin路与标准杨表  35-40
  5.1 RSK算法  35-37
  5.2 利用Motzkin路计算S(3,0;n)  37-38
  5.3 定理5.2的推论  38-40
6 进一步的研究方向  40-42
参考文献  42-46
致谢  46-49

相似论文

一类孤子方程的可积离散化,O175.2
基于ZigBee的奶牛个体识别与定位系统设计,TN929.5
MIMO-OFDM系统中降低峰均功率比的方法研究,TN919.3
广州市天然气高压系统分析研究,TU996
OFDM系统中选择性映射降低峰均比的研究,TN919.3
基于水声通信OFDM系统峰均比抑制方法及其性能研究,TN919.3
小波包多载波调制系统中的峰均比技术研究,TN919.3
带短域的分数阶Schrǒdinger算子的散射,O177
基于IEC61850-9的电子式互感器校验与在线监测系统,TM45
LTE上行单载波频分多址技术仿真与研究,TN929.5
面向4G物理层的关键技术研究,TN919.3
介质阻挡放电光学观测系统研究与图像分析,TM835
基于光谱匹配的高光谱岩矿识别技术研究,TP391.41
光伏发电并网关键技术及其对电网的影响研究,TM615
光正交频分复用传输技术的研究,TN919.3
基于部分传输序列算法的OFDM系统峰均比抑制方法的研究,TN919.3
用于金属磨粒检测系统的噪声消除算法研究,TP391.41
电调谐雷达吸波材料研究,TB34
基于IEEE 802.16e OFDMA物理层的关键技术研究,TN929.531
互联网新政治与替代性民主,G206
光电联合变换器的设计和相关峰图像的处理,TP391.41