張超

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

非對(duì)稱Motzkin路

張超

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

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

非對(duì)稱Motzkin路；Lagrange反演定理；研究分析

引言

格路計(jì)數(shù)問題是組合數(shù)學(xué)主要研究的兩大問題之一，多年來(lái)備受國(guó)內(nèi)外學(xué)者的關(guān)注。2010年Deutsch等人[1，2]定義了一種新的格路（非對(duì)稱Dyck路），文章在類比Motzkin路[3]及非對(duì)稱Dyck路的定義和相關(guān)計(jì)數(shù)結(jié)果后，提出了非對(duì)稱Motzkin路的概念，并討論了帶有路長(zhǎng)，左步數(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）不超過(guò)x軸。

n稱為路徑的路長(zhǎng)。每條非空的Motzkin路都可以被唯一的寫成Hα，UβDγ的形式之一，其中α，β，γ為任意Motzkin路。

定義3[1-2]xy平面上滿足如下四個(gè)條件的格路，稱為非對(duì)稱的Dyck路。

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

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

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

（4）不超過(guò)x軸。

n稱為路徑的半基，路徑步數(shù)的一半稱為半長(zhǎng).每條非空的非對(duì)稱Dyck路都可以被唯一的寫成UαDβ，UγL的形式之一，其中α，β，γ為非對(duì)稱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表示路長(zhǎng)為n，左步數(shù)為s，水平步數(shù)為t，峰個(gè)數(shù)為m的格路的條數(shù)。路長(zhǎng)用z刻畫，左步數(shù)用x刻畫，水平步數(shù)用y刻畫，峰的個(gè)數(shù)用u刻畫，相應(yīng)的生成函數(shù)為

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

二、主要結(jié)果

（一）非對(duì)稱Motzkin路的定義

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

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

圖1　非對(duì)稱Motzkin路

圖2　非對(duì)稱DYck路

通過(guò)上面的分解，我們可以得到通過(guò)路長(zhǎng)（用z刻畫）來(lái)表示的非對(duì)稱Motzkin路的發(fā)生函數(shù)

圖3　Motzkin

圖4　DYck路

圖5　非空非對(duì)稱Motzkin路的分解

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

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

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

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

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

則由Lagrange反演定理得到

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

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

經(jīng)過(guò)簡(jiǎn)單的運(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é)。