Let $a,b$ be fixed positive coprime integers. For a positive integer g, write Nₖ(g) for the set of lattice paths from the startpoint $(0,0)$ to the endpoint $(ga,gb)$ with steps restricted to \(1,0), (0,1)\, having exactly k flaws (lattice points lying above the linear boundary). We wish to determine |Nₖ(g)|. The enumeration of lattice paths with respect to a linear boundary while accounting for flaws has a long and rich history, dating back to the 1949 results of Chung and Feller. The only previously known values of |Nₖ(g)| are the extremal cases $k = 0$ and $k = g(a+b)-1$, determined by Bizley in 1954. Our main result is that a certain subset of Nₖ(g) is in bijection with Nₖ₊₁(g). One consequence is that the value |Nₖ(g)| is constant over each successive set of $a+b$ values of k. This in turn allows us to derive a recursion for |Nₖ(g)| whose base case is given by Bizley's result for $k=0$. We solve this recursion to obtain a closed form expression for |Nₖ(g)| for all k and g. Our methods are purely combinatorial.
No takes yet. Share an insight, caveat, or question.
Firoozi et al. (2024) studied this question.
Synapse has enriched 5 closely related papers on similar clinical questions. Consider them for comparative context: