非對稱Motzkin路

張超

（上海外國語大學(xué)賢達(dá)經(jīng)濟(jì)人文學(xué)院商學(xué)院，上海200000）

非對稱Motzkin路

張超

（上海外國語大學(xué)賢達(dá)經(jīng)濟(jì)人文學(xué)院商學(xué)院，上海200000）

文章定義了一種新的格路即非對稱Motzkin路，通過路長，左步數(shù)對非對稱Motzkin路進(jìn)行計(jì)數(shù)，并通過Lagrange反演定理得到相應(yīng)的計(jì)數(shù)公式。文章的結(jié)論是Motzkin路中結(jié)果的推廣。

非對稱Motzkin路；Lagrange反演定理；研究分析

引言

格路計(jì)數(shù)問題是組合數(shù)學(xué)主要研究的兩大問題之一，多年來備受國內(nèi)外學(xué)者的關(guān)注。2010年Deutsch等人[1，2]定義了一種新的格路（非對稱Dyck路），文章在類比Motzkin路[3]及非對稱Dyck路的定義和相關(guān)計(jì)數(shù)結(jié)果后，提出了非對稱Motzkin路的概念，并討論了帶有路長，左步數(shù)兩個(gè)參數(shù)的計(jì)數(shù)問題。

一、預(yù)備知識(shí)

定義1[3]xy平面上滿足三個(gè)條件的格路，稱為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平面上滿足如下四個(gè)條件的格路，稱為非對稱的Dyck路。

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

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

（3）上升步與左步不重疊；

（4）不超過x軸。

n稱為路徑的半基，路徑步數(shù)的一半稱為半長.每條非空的非對稱Dyck路都可以被唯一的寫成UαDβ，UγL的形式之一，其中α，β，γ為非對稱Dyck路，且γ≠ε（ε表示空路）

Lagrange反演定理[4]設(shè)A（z）滿足等式A（z）=1+zH（A（z）），此處H（λ）是關(guān)于λ的多項(xiàng)式，且上式有唯一解A（z），設(shè)G（λ）是關(guān)于λ的多項(xiàng)式，則有

定義4用as,t,m,n表示路長為n，左步數(shù)為s，水平步數(shù)為t，峰個(gè)數(shù)為m的格路的條數(shù)。路長用z刻畫，左步數(shù)用x刻畫，水平步數(shù)用y刻畫，峰的個(gè)數(shù)用u刻畫，相應(yīng)的生成函數(shù)為

引理1[3]路長為n的Motzkin路的條數(shù)為

二、主要結(jié)果

（一）非對稱Motzkin路的定義

非對稱Motzkin路是指xy平面上起點(diǎn)和終點(diǎn)在x軸，且不超過x軸，由上升步U（1，1），下降步D（1，-1），左步L（-1，-1）以及水平步H（1，0）構(gòu)成，上升步和左步不重疊的路（圖1）。非對稱Dyck路為沒有水平步的非對稱Motzkin路（圖2），Motzkin路為沒有左步的非對稱Motzkin路（圖3），Dyck路為沒有水平步和左步的非對稱Motzkin路（圖4）。路的步數(shù)為路長，如果一條路從（0，0）點(diǎn)開始，在（n，0）點(diǎn)結(jié)束，則其路長為n。

每條非對稱Motzkin路都可以用U，D，L，H表示成一個(gè)字，如圖1中的非對稱Motzkin路可以用UHUUHUDLLHHDHUUDL來表示；這些字集我們用S來表?？盏姆菍ΨQMotzkin路用空字ε來表示，一般情況下都形象的表示為“·”。在文章中我們用圖像或文字來表示非對稱Motzkin路。每條非空的非對稱Motzkin路γ都可以唯一地表示成如下任一種形式（圖5）

圖1　非對稱Motzkin路

圖2　非對稱DYck路

通過上面的分解，我們可以得到通過路長（用z刻畫）來表示的非對稱Motzkin路的發(fā)生函數(shù)

圖3　Motzkin

圖4　DYck路

圖5　非空非對稱Motzkin路的分解

用an來表示F(z)中zn的系數(shù)，也就是路長為n的非對稱Motzkin路的條數(shù)，下面我們來求an。由上可知

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

（二）主要計(jì)數(shù)結(jié)果

定理1設(shè)as，n為含有s個(gè)左步，路長為n的非對稱Motzki n路的條數(shù)為相應(yīng)的發(fā)生函數(shù)，則

這四種情況，從而F（x，z）滿足如下等式

則由Lagrange反演定理得到

從而左步數(shù)為s，路長為n的非對稱Motzkin路的條數(shù)為

注令s=0，即左步數(shù)為0，則路長為n的Motzkin路的條數(shù)為

經(jīng)過簡單的運(yùn)算得

這一結(jié)果引理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-），女，山東萊蕪，碩士研究生，助教，教師，研究方向：組合數(shù)學(xué)。