Catalan lattice paths with rook, bishop and spider steps

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...

Full description

Saved in:
Bibliographic Details
Published in:Journal of combinatorial theory. Series A 2013-02, Vol.120 (2), p.379-389
Main Authors: Kung, Joseph P.S., de Mier, Anna
Format: Article
Language:English
Subjects:
Catalan boundary
Generating function
Lattice path
Rook and queen paths
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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.
ISSN:0097-3165
1096-0899
DOI:10.1016/j.jcta.2012.08.010