加權(quán)Motzkin數(shù)的恒等式及其組合意義

辛華,楊勝良

(蘭州理工大學(xué)理學(xué)院,甘肅 蘭州 730050)

1 引言

以簡潔地描述Motzkin路的概念開始.定義n階的Motzkin路是這樣的路,它是指在平面直角坐標(biāo)系的第一象限內(nèi)從原點(diǎn)(0,0)到點(diǎn)(n,0)的格路徑,并且允許的步法只能為(1,1),(1,0),(1,?1).在點(diǎn)(n,0)結(jié)束的Motzkin路的個數(shù)記作Mn并且稱作n階Motzkin數(shù).一個在x軸沒有水平步的Motzkin路稱為一個Riordan路.在點(diǎn)(n,0)結(jié)束的Riordan路的個數(shù)稱為第n個Riordan數(shù)Rn.

大量文獻(xiàn)對Motzkin路進(jìn)行了研究,其中一些文獻(xiàn)研究了它和其他組合對象的關(guān)系,如文獻(xiàn)[1-4].更一般地,文獻(xiàn)[4]對水平步著k種顏色的Motzkin路進(jìn)行了討論并給出了峰和谷的計(jì)數(shù)方法,而文獻(xiàn)[5]則對水平步和下步分別著d和c種顏色的Motzkin路進(jìn)行了深刻的研究,文獻(xiàn)[6-9]則得到了Motzkin序列之間的一些遞推關(guān)系.本文主要通過Riordan矩陣的A序列和Z序列計(jì)算了水平步、上步和下步加權(quán)Motzkin路的矩陣及其逆矩陣,在此基礎(chǔ)上得到加權(quán)Motzkin路的相關(guān)遞推關(guān)系式.以下對本文中使用到的Riordan矩陣的相關(guān)概念做簡要介紹.

一個Riordan矩陣

是一個無限下三角形矩陣,它的第k列的生成函數(shù)是g(t)f(t)k,即

其中

為形式冪級數(shù),且 g0=1,f0=0,f1?=0.

2012年,文獻(xiàn)[10]引入了Riordan矩陣的概念,本文以引理的形式給出.

引理 1.1 一個 Riordan矩陣 R=(d(t),h(t))可以在文獻(xiàn) [11-13]中分別由兩個序列 A=(a0,a1,···) 和 Z=(z0,z1,···) 描述如下:

如果A(z)和Z(z)分別是A序列和Z序列的生成函數(shù),那么就有：

且

本文的結(jié)構(gòu)如下.第二部分集中討論了本文的主要結(jié)果,在對水平步加權(quán)的Motzkin路研究的基礎(chǔ)上,利用A序列和Z序列計(jì)算出了水平步、上步和下步加權(quán)的Motzkin路和Riordan路的矩陣表達(dá)式,分別由定理2.1和定理2.2呈現(xiàn);此外還給出了其逆矩陣的表達(dá)式,分別由推論2.1和推論2.2呈現(xiàn).推論2.2還給出了Riordan矩陣逆矩陣的一般元.第三部分,主要給出了加權(quán)Motzkin數(shù)的遞推關(guān)系恒等式并利用二次方程的微分變換給出了證明.

2 加權(quán) Motzkin路與加權(quán) (α,β,γ)-Motzkin數(shù)

這一部分將會對不同步加權(quán)的 Motzkin路給出組合解釋.考慮所謂的 (α,β,γ)-Motzkin路,這種路是水平步有α種顏色,上步有β種顏色以及下步有γ種顏色的部分Motzkin路.用 M(α,β,γ)n(t) 和 R(α,β,γ)n(t) 分別表示在 (n,0) 結(jié)束的 (α,β,γ)-Motzkin 路的個數(shù)和 (α,β,γ)-Riordan 路的個數(shù),相對應(yīng)的生成函數(shù)分別記作 M(α,β,γ)(t) 和 R(α,β,γ)(t).

根據(jù)對非空的(α,β,γ)-Motzkin路的第一個返回點(diǎn)進(jìn)行分解,所有的這些路都可以通過明確的語法對象構(gòu)造如圖1所示：

圖1 Motzkin路的第一個返回點(diǎn)分解

設(shè)

是 (α,β,γ)-Motzkin 路的發(fā)生函數(shù),現(xiàn)假設(shè) α,β,γ 固定,且一般將 m(α,β,γ)n記作 mn. 根據(jù)上圖,則有

因此 M(α,β,γ)(t)是二次方程 βγt2y2+(αt? 1)y+1=0 的解. 而該二次方程的解是：

其中,由于第一個解不給出非負(fù)整數(shù),因此它不可能是加權(quán)Motzkin數(shù)的生成函數(shù).于是有:

根據(jù)對非空的(α,β,γ)-Riordan路的第一個返回點(diǎn)進(jìn)行分解,所有的這些路都可以通過明確的語法對象構(gòu)造如圖2所示:

圖2 Riordan路(在x軸沒有水平步的Motzkin路)的第一個返回點(diǎn)分解

故有 R(α,β,γ)(t)=1+ βγt2M(α,β,γ)(t)R(α,β,γ)(t),求解此方程,則可得

定理 2.1 設(shè)Mn,k表示從(0,0)到(n,k)的(α,β,γ)-Motzkin路的個數(shù),則矩陣(Mn,k)n,k∈N是由

給出的Riordan矩陣,其中

是 (α,β,γ)-Motzkin路個數(shù)的發(fā)生函數(shù).

證明 因?yàn)镸n,k滿足以下的遞推關(guān)系(如圖3所示)：

圖3 Motzkin路之間的關(guān)系

所以

則有

由引理1.1可知,f(t)= ˉh(t),即 h(f(t))=t,則有

即證

令 ω(t)=tM(α,β,γ)(t),則

利用拉格朗日反演公式,有

推論 2.1 (M(α,β,γ)(t),βtM(α,β,γ)(t)) 的逆矩陣給出如下：

例 2.1 當(dāng) (α,β,γ)=(1,1,1),(1,2,1)和 (1,3,1)時(shí),對應(yīng)的(Mn,k)n,k∈N前幾行矩陣如下:

定理 2.2 設(shè)Rn,k表示從(0,0)到(n,k)的(α,β,γ)-Riordan路的個數(shù),則矩陣(Rn,k)n,k∈N是由

給出的 Riordan 矩陣,其中 M(α,β,γ)(t) 是 (α,β,γ)-Motzkin 路的個數(shù)的發(fā)生函數(shù).

證明 與定理2.1的證明類似,因此這里省略細(xì)節(jié).

推論 2.2(Rn,k)n,k∈N的逆矩陣給出如下:

其中

3 加權(quán) (α,β,γ)-Motzkin數(shù)的遞推關(guān)系

由第 2 部分,可知 (α,β,γ)-Motzkin 路的發(fā)生函數(shù) M(α,β,γ)(t) 滿足二次方程

對該方程兩邊關(guān)于t求導(dǎo),則可得

因此,有

上面最后的等式可以通過交叉相乘然后利用二次方程βγt2y2+(αt?1)y+1=0而得到證明.現(xiàn)在有

可以把上式重新寫成

令這個方程左邊表達(dá)式中tn的系數(shù)等于0,其中n≥1,得到

這與文獻(xiàn)[4,14]中給出的加權(quán)Motzkin數(shù)的遞推關(guān)系式相同,遞推關(guān)系(4)是非常數(shù)系數(shù)的2階齊次線性遞推關(guān)系.

當(dāng) α,β,γ取以下特殊值時(shí),(α,β,γ)-Motzkin數(shù)滿足不同的遞推關(guān)系式,而且得到了幾個著名的序列:

例 3.1 當(dāng)α=1,β=1,γ=1時(shí),(1,1,1)-Motzkin數(shù)的遞推關(guān)系式為:

它的前幾項(xiàng)是m0=1,1,2,4,9,21,···,這個序列是Motzkin數(shù)序列A001006.

例 3.2 當(dāng)α=2,β=1,γ=1時(shí),(2,1,1)-Motzkin數(shù)的遞推關(guān)系式為:

它的前幾項(xiàng)是m0=1,2,5,14,42,···,這個序列是Catalan數(shù)序列A000108.

例 3.3 當(dāng)α=3,β=1,γ=2時(shí),(3,1,2)-Motzkin數(shù)的遞推關(guān)系式為:

它的前幾項(xiàng)是 m0=1,3,11,45,197,903,···,這個序列是小 Schr¨oder數(shù)序列 A001003.