Counting Lattice Paths via a New Cycle Lemma
Counting Lattice Paths via a New Cycle Lemma
复制标题
DOI：
10.1137/100796431
复制
发表时间：
2012-05
期刊：
影响因子：
--
通讯作者：
Tomoki Nakamigawa;N. Tokushige
中科院分区：
文献类型：
--
作者：
Tomoki Nakamigawa;N. Tokushige
设$\α，\β，m，n$为正整数。在L上确定直线$L：Y=\αx+\β$和格点$q=(m，n)$。众所周知，从原点到Q且仅在Q处接触L的格路的个数由$FRAC{\β}{m+n}\Binom{m+n}m给出。我们证明的关键成分是由Dvoretzky和Motzkin[Duke Math]提出的圈引理的一个新变体。J.，14(1947)，第305-313页]和Raney[Trans.阿默。数学课。Soc.，94(1960)，第441-451页]。我们还给出了循环移位边界下格路的计数公式，推广了欧文和拉坦在[J.Combin]中的一个结果。理论系列。A，116(2009)，pp.499-514]，以及具有给定峰值数目的点阵路径的计数公式，该公式包含作为特例的Narayana数。
Let $\alpha,\beta,m,n$ be positive integers. Fix a line $L:y=\alpha x+\beta$ and a lattice point $Q=(m,n)$ on L. It is well known that the number of lattice paths from the origin to Q which touch L only at Q is given by $\frac{\beta}{m+n}\binom{m+n}m.$ We extend the above formula in various ways; in particular, we consider the case when $\alpha$ and $\beta$ are arbitrary positive reals. The key ingredient of our proof is a new variant of the cycle lemma originated by Dvoretzky and Motzkin [Duke Math. J., 14 (1947), pp. 305–313] and Raney [Trans. Amer. Math. Soc., 94 (1960), pp. 441–451]. We also include a counting formula for lattice paths lying under a cyclically shifting boundary, which generalizes a resultdue to Irving and Rattan in [J. Combin. Theory Ser. A, 116 (2009), pp. 499–514], and a counting formula for lattice paths having a given number of peaks, which contains the Narayana number as a special case.