Koroljuk's formula for counting lattice paths revisited

MaRDI QIDQ4576352zbMATH OpenFDO

Authors James J. Y. Zhao

Publication date 12 July 2018

Full work available at URL https://arxiv.org/abs/1306.6015

zbMATH Keywords

lattice pathballot problemforward recursionKoroljuk's formula

Mathematics Subject Classification ID

Exact enumeration problems, generating functions (05A15) Combinatorial identities, bijective combinatorics (05A19) Combinatorics of partially ordered sets (06A07)

Abstract: Koroljuk gave a summation formula for counting the number of lattice paths from $(0,0)$ to $(m,n)$ with $(1,0),(0,1)$-steps in the plane that stay strictly above the line $y=k(x-d)$, where $k$ and $d$ are positive integers. In this paper we obtain an explicit formula for the number of lattice paths from $(a,b)$ to $(m,n)$ above the diagonal $y=kx-r$, where $r$ is a rational number. Our result slightly generalizes Koroljuk's formula, while the former can be essentially derived from the latter. However, our proof uses a recurrence with respect to the starting points, and hereby presents a new approach to Koroljuk's formula.

Recommendations

• scientific article; zbMATH DE number 4077210
• Enumerating lattice paths touching or crossing the diagonal at a given number of lattice points
• Counting lattice paths via a new cycle lemma
• On lattice path counting by major index and descents
• Counting lattice paths in restricted planes

Cited in

(4)

• Counting lattice paths via a new cycle lemma
• The research and progress of the enumeration of lattice paths
• scientific article; zbMATH DE number 4077210 (Why is no real title available?)
• Simple formulas for lattice paths avoiding certain periodic staircase boundaries

This page was built for publication: Koroljuk's formula for counting lattice paths revisited

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4576352)