×

Koroljuk’s formula for counting lattice paths revisited. (English) Zbl 1395.05016

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

MSC:

05A15 Exact enumeration problems, generating functions
05A19 Combinatorial identities, bijective combinatorics
06A07 Combinatorics of partially ordered sets
PDFBibTeX XMLCite
Full Text: arXiv