限定高度的Dyck路的计数

王亚芹

(兰州理工大学 理学院, 甘肃 兰州 730050)

Dyck路作为一类重要的组合结构是近年来计数组合学研究的一个热点[1-2].一条半长为n的Dyck路是从(0,0)到(2n,0)的一条经过整点的格路径,它由n个上步U=(1,1)和n个下步D=(1,-1)构成,且从不走到x轴的下方.众所周知,半长为n的Dyck路的个数是第n个Catalan数.作为一种重要的数学模型,Dyck路在组合计数以及组合优化中有重要的应用[3-4].Yang等[5]研究了Dyck路的一种推广形式,Rowland[6]研究了Dyck路与二元树之间的关系.设cn,k是从(0,0)到(n,k)的所有Dyck路的个数.图1给出cn,k的部分值.Merlini等[3]证明了矩阵(cn,k)n,k≥0的许多组合性质.本文考虑一类从(0,0)到(n,k)的限定高度Dyck路,通过递推关系和线性代数的方法描述其发生函数的性质,用克拉默法则进行求解,并得到对应的显式公式.在特殊情况下,得到了Fibonacci数列的一个应用.

图1 从(0,0)到(n,k)的Dyck路径数Fig.1 The number of Dyck paths from (0,0) to (n,k)

引入一个上边界h,使路径位于一条带状区域中,称为限定高度h的Dyck路:使用步骤U=(1,1)和D=(1,-1),且限定在直线y=h以下(不能到达),x轴以上的带状区域内的路径.设fn,k是从(0,0)到(n,k)限定高度为h的Dyck路径的个数.

例1图2给出一条从(0,0)到(14,0)限定高度5的Dyck路,图3给出其递推关系.

图2 从(0,0)到(14,0)限定高度5的一条Dyck路

图3 限定高度的Dyck路的递推关系Fig.3 The recursion of height restricted Dyck paths

1 限定高度的Dyck路的计数

设fj(z)为限定高度h,且终点在直线y=j上的Dyck路的发生函数

因此

移项得

从而得到下面的线性方程组

记ah为有h行和h列的系数矩阵Ah的行列式

(1)

定理1

证明由式(1)对第一行展开会产生递归

(2)

设α+β=1,αβ=z2,那么有

从而

根据Girard-Waring公式

有

定理2限定高度h,且终点在直线y=j上,0≤j≤h-1的Dyck路的发生函数为

证明利用线性方程组来求解fj(z).根据克拉默法则,对于0≤j≤h-1,可得

其中:Ah,j+1是通过将Ah的第j+1列替换为列向量(1,0,0,…,0)T获得的矩阵.通过常规计算,得到det(Ah,j+1)=zjah-j-1.因此

定理3限定高度h,且终点在x轴上的Dyck路的发生函数可以表示成以下形式的有限连分式

其中连分式有h-1层.

易知,限定高度h的Dyck路的发生函数对应的连分式有h-1层.

例2限定高度h=4的路Dyck的发生函数f0(z)有3层.

2 一些具体示例

例3当h=2,0≤j≤1时,

f0(z)=1+zf1(z),f1(z)=zf0(z)

移项得

f0(z)-zf1(z)=1, -zf0(z)+f1(z)=0

因此

根据克拉默法则可得

所以有

图4给出限定高度2的Dyck路径数fn,k的前部分值.

图4 h=2时fn,k的前部分值Fig.4 First part values of fn,k when h=2

例4当h=3,0≤j≤2时

移项得

因此

根据克拉默法则可得

图5给出限定高度3的Dyck路径数fn,k的前部分值.

图5 h=3时fn,k的前部分值

例5当h=4,0≤j≤3时

移项得

因此,有以下线性方程组

设a4为系数矩阵A4的行列式,即

根据克拉默法则可得

图6给出限定高度4的Dyck路径数fn,k的前部分值.

图6 h=4时fn,k的前部分值Fig.6 First part values of fn,k when h=4

求和可得

例6当h=5,0≤j≤4时,

移项得

因此,有以下线性方程组

根据克拉默法则可得

f0(z)+f1(z)+f2(z)+f3(z)+f4(z)=

也可以直接通过定理1得出fj(z),

因此

图7给出限定高度5的Dyck路径数fn,k的前部分值.

图7 h=5时fn,k的前部分值Fig.7 First part values of fn,k when h=5