加权广义的Schröder路的计数

马帅帅,杨胜良

(兰州理工大学理学院,甘肃 兰州 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所示.

图2 矩阵V的递推关系

由图2可知Vn,k满足如下递推关系,

矩阵V=(Vn,k)n,k≥0的第 0列就是 Schröder数序列 (见文献 [8]中序列A006318),通项公式有

其中Ck是第k个Catalan数[9].

因为Vn+1,k+1=Vn,k+2Vn,k+1+Vn,k+2+Vn+1,k+3,对应的A-矩阵为

且Φ[0](t)=1+2t+t2.根据(5)式可得

又因为Vn+1,0=2Vn,0+Vn,1+Vn+1,2,所以R[0](t)=2+t,S[1](t)=t.根据(7)式可得

则可得如下定理.

定理 2.1设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,则矩阵V可以表示为Riordan矩阵

若令U(n,k)表示从 (0,0)到 (2n−k,k)的格路的集合,其中格路允许的步集为u=(1,1),h=(2,0),d1=(3,−1),d2=(2,−2),并且权分别为 1,2,1,1,则有Un.k=|U(n,k)|.这种不限制在x轴上方的路是自由的,它的发生函数可以表示为

其中Ci(t)是矩阵U第i列的发生函数,可得

则可得如下定理.

定理 2.2设U(n,k)表示从(0,0)到(2n−k,k)的格路的集合,其中格路允许的步集为u=(1,1),h=(2,0),d1=(3,−1),d2=(2,−2),并且权分别为 1,2,1,1,则矩阵U可以表示为Riordan矩阵

3 加权广义的 Schröder路和小 Schröder数

本节用加权广义的Schröder路给小Schröder数一个新的组合解释.现在在上一节给出的Schröder数新的组合解释中加一个在x轴没有水平步的条件,使之成为一种特殊的路,用n表示这种路的集合,(t)表示n的发生函数.

图3 符号化方法

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

其中s(t)表示小 Schröder路的发生函数,由(t)展开式前n项可以找到在OEIS的解释为没有山的小Schröder路.那么这种从(0,0)到(2n,0)允许的步集为

其中权分别为1,2,1,1,且在x轴没有水平步h=(2,0)的始终保持在x轴上方的格路径,就是没有山的小Schröder路的又一种新的组合解释.令(n,k)表示这种路的集合,则有.它的构造方法如图所示:

图4 矩阵的递推关系

令S(n,k)表示从(0,0)到(2n−k,k)的始终保持在x轴上方格路的集合,其中格路的步集为u=(1,1),h=(2,0),d1=(3,−1),d2=(2,−2),并且权分别为 1,3,2,0,则有Sn.k=|S(n,k)|.它的构造方法如图所示:

由图5可知Sn,k满足如下递推关系,

图5 矩阵S的递推关系

矩阵S=(Sn,k)n,k≥0的第 0列就是小 Schröder数序列 (见文献 [8]中序列A001003),其中通项公式有