非对称Motzkin路

张超

（上海外国语大学贤达经济人文学院商学院，上海200000）

非对称Motzkin路

张超

（上海外国语大学贤达经济人文学院商学院，上海200000）

文章定义了一种新的格路即非对称Motzkin路，通过路长，左步数对非对称Motzkin路进行计数，并通过Lagrange反演定理得到相应的计数公式。文章的结论是Motzkin路中结果的推广。

非对称Motzkin路；Lagrange反演定理；研究分析

引言

格路计数问题是组合数学主要研究的两大问题之一，多年来备受国内外学者的关注。2010年Deutsch等人[1，2]定义了一种新的格路（非对称Dyck路），文章在类比Motzkin路[3]及非对称Dyck路的定义和相关计数结果后，提出了非对称Motzkin路的概念，并讨论了带有路长，左步数两个参数的计数问题。

一、预备知识

定义1[3]xy平面上满足三个条件的格路，称为Motzkin路。

（1）起始于(0，0)，终止于(n，0)；

（2）步集为上升步U（1，1），下降步D（1，-1），水平步H（1，0）；

（3）不超过x轴。

n称为路径的路长。每条非空的Motzkin路都可以被唯一的写成Hα，UβDγ的形式之一，其中α，β，γ为任意Motzkin路。

定义3[1-2]xy平面上满足如下四个条件的格路，称为非对称的Dyck路。

（1）起始于（0，0），终止于（2n，0）；

（2）步集为上升步U（1，1），下降步D（1，-1）及左步L（-1，-1）；

（3）上升步与左步不重叠；

（4）不超过x轴。

n称为路径的半基，路径步数的一半称为半长.每条非空的非对称Dyck路都可以被唯一的写成UαDβ，UγL的形式之一，其中α，β，γ为非对称Dyck路，且γ≠ε（ε表示空路）

Lagrange反演定理[4]设A（z）满足等式A（z）=1+zH（A（z）），此处H（λ）是关于λ的多项式，且上式有唯一解A（z），设G（λ）是关于λ的多项式，则有

定义4用as,t,m,n表示路长为n，左步数为s，水平步数为t，峰个数为m的格路的条数。路长用z刻画，左步数用x刻画，水平步数用y刻画，峰的个数用u刻画，相应的生成函数为

引理1[3]路长为n的Motzkin路的条数为

二、主要结果

（一）非对称Motzkin路的定义

非对称Motzkin路是指xy平面上起点和终点在x轴，且不超过x轴，由上升步U（1，1），下降步D（1，-1），左步L（-1，-1）以及水平步H（1，0）构成，上升步和左步不重叠的路（图1）。非对称Dyck路为没有水平步的非对称Motzkin路（图2），Motzkin路为没有左步的非对称Motzkin路（图3），Dyck路为没有水平步和左步的非对称Motzkin路（图4）。路的步数为路长，如果一条路从（0，0）点开始，在（n，0）点结束，则其路长为n。

每条非对称Motzkin路都可以用U，D，L，H表示成一个字，如图1中的非对称Motzkin路可以用UHUUHUDLLHHDHUUDL来表示；这些字集我们用S来表。空的非对称Motzkin路用空字ε来表示，一般情况下都形象的表示为“·”。在文章中我们用图像或文字来表示非对称Motzkin路。每条非空的非对称Motzkin路γ都可以唯一地表示成如下任一种形式（图5）

图1　非对称Motzkin路

图2　非对称DYck路

通过上面的分解，我们可以得到通过路长（用z刻画）来表示的非对称Motzkin路的发生函数

图3　Motzkin

图4　DYck路

图5　非空非对称Motzkin路的分解

用an来表示F(z)中zn的系数，也就是路长为n的非对称Motzkin路的条数，下面我们来求an。由上可知

其中，则由Lagrange反演定理得到

（二）主要计数结果

定理1设as，n为含有s个左步，路长为n的非对称Motzki n路的条数为相应的发生函数，则

这四种情况，从而F（x，z）满足如下等式

则由Lagrange反演定理得到

从而左步数为s，路长为n的非对称Motzkin路的条数为

注令s=0，即左步数为0，则路长为n的Motzkin路的条数为

经过简单的运算得

这一结果引理1一致。

[1]Deutsch E，Emanuele Munarini，Simone Rinaldi.Skew Dyck paths，area，and superdiagonal bargraphs[J].Journal of statistical Planning and Inference，2010，140：1550-1562.

[2]Deutsch E,Emanuele Munarini,Simone Rinaldi.Skew Dyck paths[J].Journal of Statistical Planning and Inference，2010,140：2191-2230.

[3]Donaghey R，Shapiro L W.Motzkin numbers[J].Combin.Theory.Ser.A，1977，23：291-301.

[4]Rogers D，Shapiro G，Deques L W.Trees and lattice paths [M].Lecture Notes in Mathematics，1981，884：293-303.

In this thesis,we discuss a new lattice path-Skew Motzkin paths.we consider the enumeration of skew Motzkin paths according to length，number of left steps,and obtain the corresponding counting formulas by means of the Lagrange inversion theorem.Our results extend previous work of Motzkin paths.

skew motzkin paths;lagrange inversion theorem;study and analysis

O157

A

2096-000X（2016）24-0261-03

张超（1985，09-），女，山东莱芜，硕士研究生，助教，教师，研究方向：组合数学。