论文部分内容阅读
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的标准杨表之间的一个双射。