Enumerating Lattice Paths Touching or Crossing the Diagonal at a Given Number of Lattice Points
Keywords: Lattice path, bijection
AbstractWe 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.