马帅帅,杨胜良

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

1 引言

Schröder数[1-5]是一种常见的组合数,在有序树、整数的拆分等问题中有广泛应用.文献 [1]给出了 Schröder数的相关解释:半长为n的 Schröder路是从 (0,0)到(2n,0)的一条始终保持在x轴上方的经过整点的格路径,允许的步集为上步U=(1,1),水平步H=(2,0)以及下步D=(1,−1).在x轴没有水平步的 Schröder路被称为小 Schröder 路.

所有半长为n的 Schröder路的个数是 Schröder数,记为rn,Schröder数的发生函数r(t)满足等式

所有半长为n的小 Schröder路的个数是小 Schröder数,记作sn,小 Schröder 数的发生函数s(t)满足等式

定义 1.1步集为u=(1,1),h=(2,0),d1=(3,−1),d2=(2,−2)并且权分别为1,a,b,c的始终保持在x轴上方的格路径,称之为加权广义的Schröder路.

图1 符号化方法

由符号化方法可以得到这种路的发生函数为

若a=2,并且b=c=1时,对应的发生函数为

由此可以得到 Schröder数的发生函数,那么这种从 (0,0)到(2n,0),步集为u=(1,1),h=(2,0),d1=(3,−1),d2=(2,−2)并且权分别为1,2,1,1的始终保持在x轴上方的格路径是Schröder数又一种新的组合解释.

若a=3,b=2,c=0时,对应的发生函数S(t)为

由此可以得到用小Schröder数的发生函数表达的式子,那么这种从(0,0)到(2n,0),步集为u=(1,1),h=(2,0),d1=(3,−1),d2=(2,−2)并且权分别为 1,3,2,0的始终保持在x轴上方的格路径是小Schröder数又一种新的组合解释.

本文用矩阵的方法研究组合问题,下面是Riordan矩阵的相关概念.

定义1.2[6]若无限下三角矩阵M=(mn,k)n,k∈N第k列的生成函数为g(t)f(t)k则称该矩阵为Riordan矩阵,其中

是形式幂级数,且d00,f0=0,f10,记mn,k=[tn]g(t)f(t)k,其中 [tn]是系数算子,记作M=(g(t),f(t))=(g,f).

2 加权广义的 Schröder 路和 Schröder 数

本节用加权广义的Schröder路给Schröder数一个新的组合解释.令V(n,k)表示从(0,0)到(2n−k,k)的始终保持在x轴上方格路的集合,其中格路的步集为u=(1,1),h=(2,0),d1=(3,−1),d2=(2,−2),并且权分别为 1,2,1,1,则有Vn.k=|V(n,k)|.它的构造方法如图2所示.

图……