部分Motzkin路的计数

Enumeration of the partial Motzkin paths

一条长为n的部分Motzkin路是从(0,0)到(n,k)的一条经过整点的格路径,它由上步U=(1,1),下步D=(1,-1)以及水平步H=(1,0)构成,且从不走到x轴的下方.从(0,0)到(n,0)的Motzkin路的个数叫做第n个Motzkin数.利用核方法得到了Motzkin数的发生函数及部分Motzkin路径数的Riordan矩阵的表示.基于递推关系和线性代数方法给出了高度受限的部分Motzkin路的发生函数,并给出了相关示例.

A partial Motzkin path of length n is a lattice path from(0,0)to(n,k),which run through the integer points,consisting of up steps U=(1,1),down steps D=(1,-1)and horizontal steps H=(1,0),and it never goes below the x-axis.The number of Motzkin paths from(0,0)to(n,0)is called the n-th Motzkin number.The generating function of Motzkin numbers and the representation of the Riordan matrix of the number of partial Motzkin paths are obtained by using the kernel method.Finally,the generating functions of partial Motzkin paths with restricted height are given by using recurrence relations and the linear algebraic method.Some relevant examples are presented here.