Koroljuk's formula for counting lattice paths revisited

zbMATH Open1395.05016arXiv1306.6015MaRDI QIDQ4576352FDOQ4576352

James J. Y. Zhao

Publication date: 12 July 2018

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.

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

Recommendations

• scientific article
• 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

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)

Cited In (3)

• Counting lattice paths via a new cycle lemma
• The research and progress of the enumeration of lattice paths
• Title not available (Why is that?)

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)