非对称Motzkin路
2016-12-12张超
张超
(上海外国语大学贤达经济人文学院商学院,上海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刻画,相应的……
