Riordan矩陣在廣義Motzkin路計數(shù)中的應(yīng)用

王麗娟，楊勝良

（蘭州理工大學(xué)理學(xué)院，甘肅蘭州730050）

Riordan矩陣在廣義Motzkin路計數(shù)中的應(yīng)用

王麗娟，楊勝良

（蘭州理工大學(xué)理學(xué)院，甘肅蘭州730050）

用Riordan矩陣的方法研究了具有4種步型的加權(quán)格路（廣義Motzkin路）的計數(shù)問題，引入了一類新的計數(shù)矩陣，即廣義Motzkin矩陣.同時給出了這類矩陣的Riordan表示，也得到了廣義Motzkin路的計數(shù)公式.Catalan矩陣，Schr?der矩陣和Motzkin矩陣都是廣義Motzkin矩陣的特殊情形.

Riordan矩陣；格路；Catalan矩陣；Schr?der矩陣；Motzkin矩陣

1 引言

集合Z×Z中的點叫做xOy平面上的格點.由一些格點構(gòu)成的序列P=v0v1···vn叫做長度為n的格路.格路P=v0v1···vn上的兩個相鄰格點vi=（ai，bi），vi+1=（ai+1，bi+1）的差vi+1-vi=（ai+1-ai，bi+1-bi）叫做一個步，i=0，1，···，n.

設(shè)C（n，k）表示所有從點（0，0）到點（n，n-k），允許步為E=（1，0），N=（0，1），并且不到直線y=x上方的格路的集合，C（n，k）為集合C（n，k）中格路的個數(shù)，即C（n，k）=|C（n，k）|.由文獻［1］，C（n，k）是投票數(shù)，且

在文獻［2］中，Ramírez研究了第一象限內(nèi)一類具有4種步型：E=（1，0），N=（0，1），U=（1，1），V=（1，2）的加權(quán)格路的計數(shù)問題，利用這類加權(quán)格路定義了一種Riordan矩陣，這種Riordan矩陣的升對角線上的元素之和為k-Bonacci數(shù).本文用Riordan矩陣的方法研究了具有4種步型的加權(quán)路（廣義Motzkin路）的計數(shù)問題，引入了一類新的計數(shù)矩陣，即廣義Motzkin矩陣.同時給出了這類矩陣的Riordan表示，也得到了廣義Motzkin路的計數(shù)公式.Catalan矩陣，Schr?der矩陣和Motzkin矩陣都是廣義Motzkin矩陣的特殊情形.

2 Riordan矩陣

3 廣義Motzkin矩陣與廣義Motzkin數(shù)

這一節(jié)考慮第一象限內(nèi)具有4種步型E=（1，0），N=（0，1），U=（1，1），V=（1，2）且位于對角線y=x以下的加權(quán)格路的計數(shù)問題，這些步的權(quán)分別為1，a，b，c.這樣的路叫作廣義Motzkin路.規(guī)定加權(quán)格路P的權(quán)w（P）是其所有步的權(quán)的乘積，加權(quán)格路P的長度l（P）是組成這條格路的步的個數(shù).

根據(jù)上一節(jié)中Riordan矩陣的刻畫，矩陣D=［D］n，k≥0為Riordan矩陣.如果取權(quán)a=0，b=c=1，則（9）式與經(jīng)典的Motzkin矩陣的遞推關(guān)系一樣，初值也相同，所以Riordan矩陣D（1，0，1，1）就是例2.3中的Motzkin矩陣.因此稱這個Riordan矩陣為廣義Motzkin矩陣，稱其首列元素為廣義Motzkin數(shù).

定理3.1 廣義Motzkin矩陣的逆矩陣D-1的Riordan表示為：

定理3.2 廣義Motzkin矩陣D的Riordan表示為：

定理3.3 廣義Motzkin矩陣的一般元素為：

［1］Renault M.Four Proofs of the Ballot Theorem［J］.Mathematics Magazine，2007，80（5）：345-352.

［2］Ramírez J L，Sirvent V F.A Generalization of the k-Bonacci Sequence from Riordan Arrays［J］.Electronic Journal of Combinatorics，2015，22（1）：1-20.

［3］Shapiro L W，Getu S，Woan W J，et al.The Riordan group［J］.Discrete Applied Mathematics，1991，34：229-239.

［4］Sprugnoli R.Riordan arrays and combinatorial sums［J］.Discrete Mathematics，1994，132：267-290.

［5］He Tianxiao，Sprugnoli R.Sequence characterization of Riordan arrays［J］.Discrete Mathematics，2009，309（12）：3962-3974.

［6］Merlini D，Rogers D G，Sprugnoli R，et al.On some alternative characterizations of Riordan arrays［J］. Canadian Journal of Mathmatics，1997，49（2）：301-320.

［7］Merlini D，Sprugnoli R.Algebraic aspects of some Riordan arrays related to binary words avoiding a pattern［J］.Theoretical Computer Science，2011，412（27）：2988-3001.

［8］Sprugnoli R.An Introduction to Mathematical Methods in Combinatorics［M］.Dipartimento Di Sistemi E Informatica Viale Morgagni，2006.

［9］Sloane N J A.The on-line encyclopedia of integer sequences［EB/OL］.New York：Cornell University，1964.

［10］Nkwanta A，Shapiro L W.Pell walks and Riordan matrices［J］.Fibonacci Quarterly，2005，43（2）：170-180.

The application of Riordan arrays in counting generalized Motzkin paths

Wang Lijuan，Yang Shengliang
（School of Science，Lanzhou University of Technology，Lanzhou730050，China）

By means of Riordan arrays，the counting problems of weighted latticed paths with four types of steps（generalized Motzkin paths）are studied，and a new class of enumerative arrays，i.e.，generalized Motzkin arrays，are introduced.Meanwhile，the Riordan array expressions of these arrays are given，and the counting formulas also obtained.It turns out that Catalan array，Schr?der array and Motzkin array are all the special cases of the generalized Motzkin arrays.

Riordan array，latticed path，Catalan array，Schr?der array，Motzkin array

O157.1

A

1008-5513（2016）02-0160-09

10.3969/j.issn.1008-5513.2016.02.007

2016-01-15.

國家自然科學(xué)基金（11561044）.

王麗娟（1988-），碩士生，研究方向：代數(shù)組合與組合優(yōu)化.

2010 MSC:05A15，15A09