{
  "id": "2406.09590",
  "version": "v1",
  "published": "2024-06-13T21:07:42.000Z",
  "updated": "2024-06-13T21:07:42.000Z",
  "title": "Combinatorial enumeration of lattice paths by flaws with respect to a linear boundary of rational slope",
  "authors": [
    "Federico Firoozi",
    "Jonathan Jedwab",
    "Amarpreet Rattan"
  ],
  "comment": "22 pages, 10 figures, 2 tables",
  "categories": [
    "math.CO"
  ],
  "abstract": "Let $a,b$ be fixed positive coprime integers. For a positive integer $g$, write $N_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). We wish to determine $|N_k(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_k(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_k(g)$ is in bijection with $N_{k+1}(g)$. One consequence is that the value $|N_k(g)|$ is constant over each successive set of $a+b$ values of $k$. This in turn allows us to derive a recursion for $|N_k(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_k(g)|$ for all $k$ and $g$. Our methods are purely combinatorial.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2024-06-13T21:07:42.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "05A15"
    ],
    "keywords": [
      "lattice paths",
      "linear boundary",
      "combinatorial enumeration",
      "rational slope",
      "form expression"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 22,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}