Enumerating Lattice Paths Touching or Crossing the Diagonal at a Given Number of Lattice Points

  • Michael Z. Spivey
Keywords: Lattice path, bijection

Abstract

We give bijective proofs that, when combined with one of the combinatorial proofs of the general ballot formula, constitute a combinatorial argument yielding the number of lattice paths from $(0,0)$ to $(n,rn)$ that touch or cross the diagonal $y = rx$ at exactly $k$ lattice points.  This enumeration partitions all lattice paths from $(0,0)$ to $(n,rn)$.  While the resulting formula can be derived using results from Niederhausen, the bijections and combinatorial proof are new.
Published
2012-08-30
Article Number
P24