Discrepancy in the number of diagonal paths in a lattice

53 Views Asked by At

I want to find the number of diagonal paths (north-east and south-east paths) from $(0,j)$ to $(n,k)$ without touching the lines $y=m$ and $y=0$, where $0<j<m$. I observed that to find such paths, just finding paths from $(0,j)$ to $(n-1,k-1)$ should be sufficient, as after that just adding a diagonal edge suffices. Now, to do this, I first shifted the whole lattice downwards, so now I need to find the number of diagonal paths from origin to $(n-1,k-j-1)$ without touching the lines $y=m-j$ and $y=-j$. To do this, I transformed the lattice using the map $$(x,y) \mapsto \left(\frac{x-y}{2},\frac{x+y}{2}\right)$$ and after that applied lemma 4a from Narayana's Lattice Path Combinatorics With Statistical Applications, pg 12 and after some calculation, the number of diagonal paths turned out to be $$L\left(\frac{n-k+j}{2},\frac{n+k-j}{2}-1;j,m-j\right)=\sum_l \left[\binom{n-1}{\frac{n-k+j}{2}-lm}_+-\binom{n-1}{\frac{n+k+j}{2}-1+lm}_+\right]$$ where $$\binom{n}{x}_+ = \begin{cases}\binom{n}{x} &\text{ if } 0 \le x\le n \\ 0 &\text{ if } x<0, x>n\end{cases} $$But from this answer and also this, the number of diagonal paths is turning out to be $$\sum_l \left[\binom{n-1}{\frac{n+k-j}{2}-1+lm}_+-\binom{n-1}{\frac{n+k+j}{2}-1+lm}_+\right]$$which presents a discrepancy. Is there any mistake in my approach or did I do any mistake in calculation?

1

There are 1 best solutions below

0
On BEST ANSWER

As requested: Notice that $\binom{n}{k}=\binom{n}{n-k}$ and so the first binomial in your expression gives $$\binom{n-1}{\frac{n-k+j}{2}-lm}=\binom{n-1}{n-1-\left (\frac{n-k+j}{2}-lm\right )}=\binom{n-1}{\frac{n+k-j}{2}+lm-1}.$$