我们记 中所有恰含 个 步， 个低参数和 个高参数的PDP的总数为 .注意，在本文中， （ ， ）为根据 步的数目以及被考查的参数（低参数，高参数）的数目给出的PDP的生成函数.

我们记 为所有 Dyck路中参数 的值之和，则我们有

在本文中，我们假设 中所有PDP的出现是等可能的，则参数 的期望为 .

下面我们给出有关Dyck路的一些定义以及定理证明中需要用到的引理.文献综述

定义1  Dyck路的非空子路称为一个串，子路所经过的步数称为串的长度.

例如，长为 的串有 .其中 称为峰， 称为谷.长为 的串有 .众所周知 ，半长为 且恰含 个谷的经典Dyck路的个数为Narayana数 .

定义2  如果一个串与直线 接触，则称其为低串，否则称其为高串.

引理1 （Lagrange反演定理）  设 是关于 的多项式，生成函数 满足函数方程

则此函数方程有唯一解 ，且

引理2   对于 ，

证  显然生成函数 满足Lagrange反演定理的条件，因此

引理3   当 为非负整数时， 

证  对 使用数学归纳法.当 时，由广义牛顿二项式定理，我们有

当 时，由上述论证，我们有

假设命题对 均成立，则对于 ，由 的函数方程有

由归纳原理知，结论得证.

2 根据各种参数进行PDP计数

在本节中，我们主要研究有关长为 的串的统计数据.我们将先给出含有不同参数的PDP生成函数方程，然后应用拉格朗日反演定理给出其计数公式，最后我们将给出PDP中各参数值的数目及其期望估计.

2.1   的数目

由第一返回分解，每个非空经典Dyck路可唯一分解为

 , 或者 .来~自^751论+文.网www.751com.cn/

从而，根据 步的数目（用 表示）以及 的数目（用 表示），我们可知经典Dyck路的生成函数 满足以下函数方程：

     (2.1)

进而，我们有如下定理：

定理2.1  （1）对于 ，我们记 ，则

 .

（2）对于 ，

且有

（3） 中串 的数目的期望值为

证  （1）由Lagrange反演定理，

从而

即有

 .

（2）由最后返回分解，任意 可唯一分解为

 或者 .

因此，当 时

类似地，我们可以得到当 时

当 时

整理即得

一类广义Dyck路中若干统计量的计数(2):http://www.751com.cn/shuxue/lunwen_74665.html