Koroljuk's formula for counting lattice paths revisited

摘要

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.