摘要   平面上的广义Dyck路是指满足以下条件的路径： 始于原点，终于 ，其中 ； 不向上越过主对角线 ； 步集为 .记 为所有终于直线 且恰有 步的广义Dyck路构成的集合，本文将研究 中若干统计量的计数问题.首先，我们根据一些参数的数目建立了 中广义Dyck路的生成函数方程，然后我们运用拉格朗日反演定理给出了这些广义Dyck路的计数公式，最后我们考察了 中某些统计量的计数公式及期望估计.66680

毕业论文关键词  广义Dyck路；生成函数；拉格朗日反演定理；计数；期望

0 引言

平面直角坐标系中横纵坐标皆为整数的点称为平面格点，从某一个格点到另一个格点且只走平面格点的路径称为平面上的一条格路.格路的长度是指格路所经过的步数. 格路问题一直是组合数学中的经典问题,如今格路问题被广泛应用于生物信息学、统计学以及随机过程等领域.

所谓 平面上的Dyck路是指满足以下条件的格路： 始于原点，终于 ； 始终不向上越过主对角线； 步集为 .我们称 称为这种路径的半长.众所周知，半长为 的Dyck路的总数为第 个Catalan数 .

近年来，国内外大量学者对Dyck路的计数问题进行了研究.Deutsch教授等人首先运用符号方法（详见文献[1]）研究了经典Dyck路中各种参数的计数与期望估计问题（参见文献[3]-[8]），之后以T.Mansour教授为代表的多位学者进一步研究了高为 的参数计数问题（参见文献[10]-[13]），丰富了该领域的研究成果.论文网

如果把Dyck路的步集换成 ，则这种路径称为Motzkin路.近年来，有国外学者推广了经典Motzkin路，提出了广义Motzkin路（参见文献[14],[15]）的概念，即将第一个条件推广为始于原点，终于 ，其中 .

在本文中，类似于广义Motzkin路，我们引入广义Dyck路（简记为PDP）的概念，所谓广义Dyck路是指满足以下条件的格路： 始于原点，终于 ，其中 ； 始终不向上越过主对角线； 步集为 .我们可将这种类型的格路表示为 Dyck路，当 时，这种广义Dyck路恰为经典Dyck路，因此广义Dyck路是经典Dyck路的推广，我们记空路为 .

卢青林教授等人根据 步的个数以及各种长为 的参数的数目研究了PDP的计数和期望估计问题(详见文献[9])，本文在上述研究的基础上，根据 步的个数以及各种长为 串的数目进一步研究了PDP的计数和期望估计问题.本文共分为五大部分，第一部分我们给出一些预备知识；第二部分我们根据 步的个数以及各种长为 串的数目给出了PDP的生成函数方程及计数公式，以及所有PDP中长为 的串的计数公式及期望估计；第三部分根据 步的个数以及各种高低参数给出了PDP的生成函数方程及计数公式；第四与第五部分分别根据高、低参数以及 步的个数给出了PDP的生成函数方程及计数公式，并且分别给出高、低参数的计数公式及期望估计.

1 预备知识

对于整数 ，记所有 Dyck路的数目为 .众所周知， 被称为ballot数，且 .特殊地， 恰为Catalan数.

对于任意整数 ，我们记 为所有终于直线 的Dyck路构成的集合，设 为 的生成函数，则

其中 .

容易发现 恰为经典Dyck路的生成函数，也被称为Catalan函数，其满足函数方程：

易知其显式表达式为

设 为 中所有恰含 个 步的广义Dyck路的全体构成的集合.在本文中，我们根据 步的数目（用 表示）以及被考查的参数 的数目（用 表示）将PDP的生成函数记为 .类似地，我们根据 步的数目（用 表示），被考查的低参数 的数目（用 表示）以及高参数 的数目（用 表示）将PDP的生成函数记为 .其中