
doi: 10.37236/1368
A bivariate symmetric backwards recursion is of the form $d[m,n]=w_{0}(d[m-1,n]+d[m,n-1])+\omega_{1}(d[m-r_{1},n-s_{1}]+d[m-s_{1},n-r_{1}])+\dots+\omega_{k}(d[m-r_{k},n-s_{k}]+d[m-s_{k},n-r_{k}])$ where $\omega_{0},\dots\omega_{k}$ are weights, $r_{1},\dots r_{k}$ and $s_{1},\dots s_{k}$ are positive integers. We prove three theorems about solving symmetric backwards recursions restricted to the diagonal band $x+u < y < x-l$. With a solution we mean a formula that expresses $d[m,n]$ as a sum of differences of recursions without the band restriction. Depending on the application, the boundary conditions can take different forms. The three theorems solve the following cases: $d[x+u,x]=0$ for all $x\geq0$, and $d[x-l,x]=0$ for all $x\geq l$ (applies to the exact distribution of the Kolmogorov-Smirnov two-sample statistic), $d[x+u,x]=0$ for all $x\geq0$, and $d[x-l+1,x]=d[x-l+1,x-1]$ for $x\geq l$ (ordinary lattice paths with weighted left turns), and $d[y,y-u+1]=d[y-1,y-u+1]$ for all $y\geq u$ and $d[x-l+1,x]=d[x-l+1,x-1]$ for $x\geq l$. The first theorem is a general form of what is commonly known as repeated application of the Reflection Principle. The second and third theorem are new; we apply them to lattice paths which in addition to the usual North and East steps also make two hook moves, East-North-North and North-East-East. Hook moves differ from knight moves (covered by the first theorem) by being blocked by any piece of the barrier they encounter along their three part move.
lattice paths, Exact enumeration problems, generating functions, symmetric backwards recursion, boundary
lattice paths, Exact enumeration problems, generating functions, symmetric backwards recursion, boundary
| selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | 6 | |
| popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network. | Average | |
| influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | Average | |
| impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network. | Average |
