Catalan lattice paths with rook, bishop and spider steps

JOURNAL OF COMBINATORIAL THEORY SERIES A

卷:120

Article

Kung, Joseph P. S.¹  de Mier, Anna² 

[1] Univ N Texas, Dept Math, Denton, TX 76203 USA

[2] Univ Politecn Cataluna, Dept Matemat Aplicada 2, ES-08034 Barcelona, Spain

关键词: Lattice path;    Rook and queen paths;    Catalan boundary;    Generating function;   

DOI  :  10.1016/j.jcta.2012.08.010

来源: Elsevier

【 摘 要 】

A lattice path is a path on lattice points (points with integer coordinates) in the plane in which any step increases the x- or y-coordinate, or both. A rook step is a proper horizontal step east or vertical step north. A bishop step is a proper diagonal step of slope 1 (to the northeast). A spider step is a proper step of finite slope greater than 1 (in a direction between north and northeast). A lattice path is Catalan if it starts at the origin and stays strictly to the left of the line y = x - 1. We give abstract formulas for the ordinary generating function of the number of lattice paths with a given right boundary and steps satisfying a natural slope condition. Explicit formulas are derived for generating functions of the number of Catalan paths in which all rook steps and some (or all) bishop or spider steps are allowed finishing at (n, n). These generating functions are algebraic; indeed, many satisfy quadratic equations. (C) 2012 Elsevier Inc. All rights reserved.

【 授权许可】

Free