Combinatorial enumeration of lattice paths by flaws with respect to a linear boundary of rational slope

Let $a,b$ be fixed positive coprime integers. For a positive integer $g$, write $W_k(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 connecting the startpoint to the endpoint). We determine $\mathrm{\mid }{W}_k(g)\mathrm{\mid }$ for all $k$ and $g$. The enumeration of lattice paths with respect to a linear boundary while accounting for flaws has a long and rich history, dating back at least to the 1949 results of Chung and Feller. The only previously known values of $\mathrm{\mid }{W}_k(g)\mathrm{\mid }$ are the extremal cases $k=0$ and $k=g(a+b)-1$, determined by Bizley in 1954. Our main combinatorial result is that a certain subset of $W_k(g)$ is in bijection with $W_{k+1}(g)$. One consequence is that the value $\mathrm{\mid }{W}_k(g)\mathrm{\mid }$ is constant over each successive set of $a+b$ values of $k$. This in turn allows us to derive a recursion for $\mathrm{\mid }{W}_k(g)\mathrm{\mid }$ whose base case is given by Bizley’s result for $k=0$. We solve this recursion to obtain a closed form expression for $\mathrm{\mid }{W}_k(g)\mathrm{\mid }$ for all $k$ and $g$. Our methods are purely combinatorial.