2024/06/13 by Federico Firoozi, Firoozi, Federico, Jonathan Jedwab +3
Computer Science · Mathematics · #05A15 #Advanced Combinatorial Mathematics #Combinatorics (math.CO) #Digital Image Processing Techniques #FOS: Mathematics #Topological and Geometric Data Analysis
paper · pdf · doi:10.48550/arxiv.2406.09590
openalex publication_date 2024/06/13 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Let a,b be fixed positive coprime integers. For a positive integer g, write Wk(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 |Wk(g)| 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 |Wk(g)| 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 Wk(g) is in bijection with Wk+1(g). One consequence is that the value |Wk(g)| is constant over each successive set of a+b values of k. This in turn allows us to derive a recursion for |Wk(g)| whose base case is given by Bizley's result for k=0. We solve this recursion to obtain a closed form expression for |Wk(g)| for all k and g. Our methods are purely combinatorial.