王善坤，張治海

(大連理工大學 城市學院，遼寧 大連 116600)

?

Colored-Motzkin數對數凸性研究

王善坤，張治海

(大連理工大學 城市學院，遼寧 大連 116600)

摘要：通過構造Colored-Motzkin三角矩陣，驗證了該矩陣為Aigner-Catalan-Riordan矩陣的特例。通過證明Colored-Motzkin數是Colored-Motzkin三角矩陣的第0列元素來研究其對數凸性。由于Catalan數、Motzkin數、Hexagonal數都是Colored-Motzkin數的特例，因此可以統一的推導出Catalan數、Motzkin數、Hexagonal數各自都構成對數凸序列。

關鍵詞：Colored-Motzkin數；Aigner-Catalan-Riordan矩陣；對數凸性

組合學家們在組合序列的對數凹性方面已經取得了豐富的研究成果[3-4]。而在組合序列的對數凸性方面，情況并不是一樣的樂觀。Davenport 和 Pólya[5]于1949年得出二項式卷積保持對數凸性的結論，但是在很長一段時間里，組合學家們并沒有對序列的對數凸性進行非常系統的研究。因此目前只有一些比較零散的研究結果。本文研究帶有參數的組合序列Colored-Motzkin數的對數凸性，由于Colored-Motzkin數可以統一的表示許多常見的組合序列，因此可以統一的判斷許多常見組合序列是否具有對數凸性。

1Colored-Motzkin數及相關工具簡介

1.1　Colored-Motzkin數

Colored-Motzkin數mn(u,l,d)[6]定義為

式中，u,l,d為非負整數。 mn(u,l,d)滿足遞歸關系

(n+2)mn(u,l,d)=l(2n+1)mn-1(u,l,d)+(4ud-l2)(n-1)mn-2(u,l,d)。

由上式可以得出Colored-Motzkin數的發(fā)生函數為[7]

1.2　Riordan矩陣

Riordan矩陣是無限下三角矩陣，該矩陣可以用一對函數(g(x),f(x))來表示。Riordan矩陣第k列元素的發(fā)生函數Ck(x)為

Ck(x)=xkfk(x)g(x), k=0,1,2,…,

式中，g(0)=1,f(0)≠0。

設R=[rn,k]n,k≥0為Riordan矩陣，且R=(g(x),f(x))。則Riordan矩陣R可以通過序列A={an}n≥0和Z={zn}n≥0來刻畫[8]，即

設A序列的發(fā)生函數為A(x)，Z序列的發(fā)生函數為Z(x)，則A(x)和Z(x)與g(x)和f(x)滿足關系

1.3　Aigner-Catalan-Riordan矩陣

設矩陣

是無限下三角矩陣，其滿足遞歸關系

(n,k≥0),

式中，zj,aj,k為非負整數，且當k>j≥0時 aj,k=0。無限下三角矩陣T=[tn,k]n,k≥0稱為Aigner-Catalan-Riordan矩陣。

設矩陣T=[tn,k]n,k≥0為Aigner-Catalan-Riordan矩陣，則稱矩陣

為Aigner-Catalan-Riordan矩陣T=[tn,k]n,k≥0的系數矩陣。容易看出Aigner-Catalan-Riordan矩陣是廣義的Riordan矩陣。

2Colored-Motzkin數的對數凸性

定義1Colored-Motzkin三角矩陣M(u,l,d)=[Mn,k(u,l,d)]n,k≥0是無限下三角矩陣，其遞歸定義為

M0,0(u,l,d)=1, T0,k(u,l,d)=0 (k>0);

Tn+1,0(u,l,d)=lTn,0(u,l,d)+dTn,1(u,l,d) (n≥0);

Tn+1,k+1(u,l,d)=uTn,k(u,l,d)+lTn,k+1(u,l,d)+dTn,k+2(u,l,d) (n,k≥0)。

其中u,l,d為非負整數。

定理1Colored-Motzkin數mn(u,l,d)是Colored-Motzkin三角矩陣M(u,l,d)=[Mn,k(u,l,d)]n,k≥0的第0列元素。

證明由Riordan矩陣的定義可得Colored-Motzkin三角矩陣M(u,l,d)=[Mn,k(u,l,d)]n,k≥0是Riordan矩陣的特例，且其A序列與Z序列分別為

A={u,l,d,0,…},Z={l,d,0,…};

其A序列與Z序列的發(fā)生函數分別為

A(x)=u+lx+dx2,Z(x)=l+dx。

設M(u,l,d)=(g(x),f(x))，則由A(x)和Z(x)與g(x)和f(x)之間滿足的關系可得

由f(0)=c可以解得

將式g(x)與Colored-Motzkin數的發(fā)生函數進行比較，可得Colored-Motzkin數mn(u,l,d)是Colored-Motzkin三角矩陣M(u,l,d)=[Mn,k(u,l,d)]n,k≥0的第0列元素，即

mn(u,l,d)=Mn,0(u,l,d)。

證畢。

定理2[9]設矩陣T=[tn,k]n,k≥0為Aigner-Catalan-Riordan矩陣，若該矩陣的系數矩陣[ζ,A]是TP2矩陣， 則矩陣T的第0列元素構成對數凸序列。

定理3當l2≥ud時，Colored-Motzkin數mn(u,l,d)構成對數凸序列。

證明由Colored-Motzkin三角矩陣M(u,l,d)=[Mn,k(u,l,d)]n,k≥0的定義可得矩陣M(u,l,d)是Aigner-Catalan-Riordan矩陣的特例，其系數矩陣為

易見當l2≥ud時系數矩陣[ζ,A]是TP2矩陣。最后由定理2可得當l2≥ud時，Colored-Motzkin數mn(u,l,d)構成對數凸序列。

證畢。

3結語

通過研究Colored-Motzkin數的對數凸性，可以統一的研究Catalan數、Motzkin數、Hexagonal數的對數凸性，統一相關結論。

當u=1,l=1,d=1時，

當u=1,l=2,d=1時，

當u=1,l=3,d=1時，

可見Colored-Motzkin數是Catalan數、Motzkin數、Hexagonal數的共同推廣[10]，即

Mn(1,1,1)=Mn;

Mn(1,2,1)=Cn+1;

Mn(1,3,1)=Hn。

推論1Catalan數、Motzkin數、Hexagonal數各自都構成對數凸序列。

參考文獻：

[1]DOLIC′T,SVRTAND,VELJAND.Enumerativeaspectsofsecondarystructures[J].DiscreteMath, 2004, 285(1/2/3):67-82.

[2]ASAIN,KUBOI,KUOHH.Bellnumbers,log-concavity,andlog-convexity[J].ActaApplMath, 2000, 63(1/2/3):79-87.

[3]STANLEYRP.Log-concaveandunimodalsequencesinalgebra,combinatorics,andgeometry[G]∥GraphTheoryanditsApplications:EastandWest.NewYork:NewYorkAcadSci, 1989: 500-535.

[4]BRENTIF.Log-concaveandunimodalsequencesinalgebra,combinatorics,andgeometry:anup-date[G]∥Jerusalemcombinatorics’93.vol178.AmerMathSoc,Providence,RI, 1994: 71-89.

[5]DAVENPORTH,PóLYAG.Ontheproductoftwopowerseries[J].CanadianJMath, 1949, 1:1-5.

[6]MANSOURT,SCHORKM,SUNY.Motzkinnumbersofhigherrank:generatingfunctionandexplicitexpression[J].JIntegerSeq, 2007, 10(7):Article07.7.4, 11.

[7]WILFHS.Generatingfunctionology[M].Boston:AcademicPress,Inc, 1990.

[8]MERLINID,ROGERSDG,SPRUGNOLIR,etal.OnsomealternativecharacterizationsofRiordanarrays[J].CanadJMath, 1997, 49(2):301-320.

[9]WANGY,ZHANGZH.Log-convexityofAigner-Catalan-Riordannumbers[J].LinearAlgebraAppl,2014, 463:45-55.

[10]WANGY,ZHANGZH.Combinatoricsofgeneralizedmotzkinnumbers[J].JIntegerSeq, 2015, 18(4) :Article15.2.4.

(責任編輯鄒永紅)

Study on the Log-convexity of Colored-Motzkin Numbers

WANG Shan-kun, ZHANG Zhi-hai

(College of urban, Dalian University of Technology, Dalian Liaoning 116600, China)

Abstract:In this paper, by means of constructing Colored-Motzkin triangles array, we verify that the array is the special case of Aigner-Catalan-Riordan arrays. We investigate the log-convexity of Colored-Motzkin numbers by proofing the fact that Colored-Motzkin numbers coincide with the first column of the Colored-Motzkin triangles. For the reason that Catalan numbers, Motzkin numbers and Hexagonal numbers are special cases of Colored-Motzkin numbers, we could get the log-convexity of Catalan numbers, Motzkin numbers and Hexagonal numbers, respectively.

Key words:colored-motzkin numbers；Aigner-Catalan-Riordan arrays；log-convexity

中圖分類號：O157.1

文獻標志碼：A

文章編號：2096-1383(2016)01-0047-03

作者簡介：王善坤(1960-)，男，遼寧大連人，副教授，主要從事計算機網絡、計算機算法研究。

收稿日期：2015-04-21；最后修回日期：2015-10-08