Number of paths from $(0,0)$ to $(n,k)$ where all four directions are allowed, using a specific number of steps

Question

It is well known that the number of paths from $(0,0)$ to $(n,k)$ in $\mathbb{N^2}$ with the set of steps $\{(1,0),(0,1)\}$ is ${n+k \choose k}$. This is the minimum number of steps needed to get to $(n,k)$.

Consider the step set:

$\;\;\;\;\;\;$ $\uparrow$

$\leftarrow\;\;\;\;\;\;\;\;$ $\rightarrow$

$\;\;\;\;\;\;$ $\downarrow\;\;$

Where every step is one unit in that direction. I wonder: is it known how many paths there are from $(0,0)$ to $(n,k)$ with n+k+2 or even n+k+4 steps under these unit steps?

I mean, is there a closed form formula for these kind of paths with $2$, $4$ or $2r$ "extra" steps?

Answer 1

I am posting the answer in the interest of quality content and engaging the curiosity of the viewers who left wondering about the answer. I found the answer to my question after much reference hunting from paper to paper during the summer of 2014. The answer is: Yes, there is such a formula for $n+k+2$ and $n+k+4$, in fact the formula works for $n+k+t$ where $t$ is any number of extra steps, and there even is a formula for higher dimensions!!.

$$P_n^{++}((0,0)\rightarrow(c,d)):=\binom{n}{\frac{n+c-d}{2}}\binom{n+2}{\frac{n-c-d}{2}}-\binom{n+2}{\frac{n+c-d}{2}+1}\binom{n}{\frac{n-c-d}{2}-1}$$

Where $n$ is the total number of steps, so there are $n-c-d$ extra steps. For higher dimensions refer to the paper.

The details of the proof can be found in Richard Guy, Bruce E. Sagan and Christian Krattenthaler's paper titled Lattice paths, reflections, & dimension-changing bijections . This is a dvi copy found in Sagan's website. The proof is ingenious and rather simple( once you see it, but not before.)

Answer 2

For a path with $n+k+2r$ steps, if you have $n+i$ steps of $(1,0)$ you'll have $i$ steps of $(-1,0)$, $k+r-i$ steps of $(0,1)$ and $r-i$ steps of $0,-1)$, where $0 \le i \le r$. Note that it doesn't matter in which order you take your steps. So you just count the number of ways to choose $n+i$ elements out of $n+k+2r$, then $i$ out of the remaining $k+2r-i$, then $k+r-i$ of the remaining $k+2r-2i$. The total number of ways is $$ \sum_{i=0}^r \dfrac{(n+k+2r)!}{(n+i)!i!(k+r-i)!(r-i)!} = {n+k+2\,r\choose k+r}{n+k+2\,r\choose r}$$

EDIT: Oops, this is using ${\mathbb Z}^2$, not ${\mathbb N}^2$. If you require the path to stay in the first quadrant, that changes things.