非對稱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來表?？盏姆菍ΨQMotzkin路用空字ε來表示，一般情況下都形象的表示為“·”。在文章中我們用圖像或文字來表示非對稱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-），女，山東萊蕪，碩士研究生，助教，教師，研究方向：組合數學。