非對稱Dyck路的三個計數(shù)結(jié)果

,

(徐州師范大學(xué) 數(shù)學(xué)科學(xué)學(xué)院,江蘇 徐州 221116)

0 引言

格路計數(shù)問題是組合數(shù)學(xué)主要研究問題之一,多年來備受國內(nèi)外學(xué)者的關(guān)注.最近,Deutsch等人[1-2]定義了一種新的格路(非對稱Dyck路),討論了其性質(zhì),并給出了計數(shù)公式.本文主要考慮非對稱Dyck路在固定半長和左步時,帶有峰、谷、雙升等參數(shù)的計數(shù)問題.

1 預(yù)備知識

定義1[1]平面上起點和終點都在x軸,且不向下越過x軸,由上升步U(1,1),下降步D(1,-1),左步L(-1,-1)構(gòu)成步集,且上升步和左步不重疊的路,我們稱之為非對稱Dyck路.我們用M表示所有的非對稱Dyck路集,則M中任一非空路都可以被唯一的表示為Uα1Dα2或Uα3L的形式,其中α1,α2,α3∈M且α3≠ε(ε表示空路).

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

引理1[4]峰的個數(shù)為l,半長為n的Dyck路的條數(shù)為

引理2[4]谷的個數(shù)為t,半長為n的Dyck路的條數(shù)為

引理3[4]雙升的個數(shù)為m,半長為n的Dyck路的條數(shù)為

引理4[2]左步數(shù)s,半長為n的非對稱Dyck路的條數(shù)為

2 主要結(jié)果

1)F(x,y,z)=1+z[F(x,y,z)(F(x,y,z)-1)+yF(x,y,z)+x(F(x,y,z)-1)].

證明1)由于任一非空的非對稱Dyck路γ都可以唯一地分解為如下三種形式之一

Uα1Dα2;UDα3;Uα4L;(α1,α4≠ε),

從而我們得到

F(x,y,z)=1+zF(x,y,z)(F(x,y,z)-1)+zyF(x,y,z)+zx(F(x,y,z)-1),

即

F(x,y,z)=1+z[F(x,y,z)(F(x,y,z)-1)+yF(x,y,z)+x(F(x,y,z)-1)].

2)令A(yù)(z)=1+zH(A(z)),H(λ)=λ(λ-1)+yλ+x(λ-1),其中A(z)=F(x,y,z),則由Lagrange反演定理得

令σ-t+k=σ-1,則

所以

即

左步數(shù)為s,峰的個數(shù)為t,半長為n的非對稱Dyck路的條數(shù)為

注1 當(dāng)s=0時,則非對稱Dyck路變成普通的Dyck路,由此可知:含有t個峰,半長為n的Dyck路的條數(shù)at,n為

注2 對t=1,2,…,n求和,可知左步數(shù)為s半長為n的非對稱Dyck路的條數(shù)為

此結(jié)果與引理4結(jié)論一致.

1)F(x,y,z)=1+z[yF(x,y,z)(F(x,y,z)-1)+F(x,y,z)+x(F(x,y,z)-1)];

證明由于任一非空的非對稱Dyck路γ都可以唯一的分解為如下三種形式之一

Uα1Dα2；Uα3D；Uα4L;(α2,α4≠ε),

則有

F(x,y,z)=1+zyF(x,y,z)(F(x,y,z)-1)+zF(x,y,z)+zx(F(x,y,z)-1).

即

F(x,y,z)=1+z[yF(x,y,z)(F(x,y,z)-1)+F(x,y,z)+x(F(x,y,z)-1)].

令A(yù)(z)=1+zH(A(z)),H(λ)=yλ(λ-1)+λ+x(λ-1),其中A(z)=F(x,y,z),則由Lagrange反演定理得

所以

令s+t+m=σ-1,則

所以

即

故左步數(shù)為s,谷的個數(shù)為t,半長為n的非對稱Dyck路的條數(shù)為

注3 當(dāng)s=0時,則非對稱Dyck路變成普通的Dyck路,含有t個谷,半長為n的Dyck路數(shù)為

此結(jié)果與引理2的結(jié)果一致.

1)F(x,y,z)=1+z[yF(x,y,z)(F(x,y,z)-1)+F(x,y,z)+xy(F(x,y,z)-1)].

證明由于任一非空的非對稱Dyck路γ都可以唯一的分解為如下三種形式之一

Uα1Dα2；UDα3；Uα4L;(α1,α4≠ε),

故有

F(x,y,z)=1+zyF(x,y,z)(F(x,y,z)-1)+zF(x,y,z)+zxy(F(x,y,z)-1).

令A(yù)(z)=1+zH(A(z)),H(λ)=yλ(λ-1)+λ+xy(λ-1),其中A(z)=F(x,y,z),則由Lagrange反演定理得

所以

令s+l=t,l+s+m=σ-1,則

所以

即

故左步數(shù)為s,雙升的個數(shù)為t,半長為n的非對稱Dyck路的條數(shù)為

注4 當(dāng)s=0時,則非對稱Dyck路變成普通的Dyck路,故含有t個雙升,半長為n的Dyck路數(shù)為

此結(jié)果與引理3的結(jié)果一致.

[1]Deutsch E,Munarini E,Rinaldi S.Skew Dyck paths area and superdiagonal bargraphs[J].Journal of Statistical Planning and Inference,2010,140:1550-1562.

[2]Deutsch E,Munarini E,Rinaldi S.Skew Dyck paths[J].Journal of Statistical Planning and Inference,2010,140:2191-2203.

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

[4]Deutsch E.Dyck path enumeration[J].Discrete Mathematics,1999,204:167-202.