Number of ways to get to a specified lattice point from the origin

Question

If we want to get to the point $(a,b)\in\mathbb{Z}^2$ with $a \neq 0, b\neq 0$, and are allowed to make either 1 or 2 steps in the x and y directions, how many ways are there to get to $(a,b)$ from $(0,0)$?

In the case of one dimension, if we want to get to point $a$ from $0$ and are allowed 1 or 2 steps each time, we let $f(n)$ be the number of ways of arriving at $a$ when a distance of $n$ from $a$. So $f(n)=f(n-1)+f(n-2)$ with the initial conditions $f(1)=1,f(2)=2$. Then the value of $f(a)$ is our answer.

In the case of two dimensions, I tried a similar thing. If we let $f(n,k)$ be the number of ways of getting to $(a,b)$ when the x-coordinate is a distance $n$ from $a$ and the y-coordinate is a distance $k$ from $b$, then $f(n,k) = f(n-1,k) + f(n-2,k) + f(n,k-1)+f(n,k-2)$ with initial conditions $f(a,b)=0, f(a-1,b)=1,f(a-2,b)=2,f(a,b-1)=1,f(a,b-2)=2$ etc. This does not seem very useful as a solution and was wondering if whether there is some way to find an explicit form for $f(a,b)$.

Answer 1

Here we consider the steps \begin{align*} (1,0), (2,0), (0,1), (0,2)\tag{1} \end{align*} and we are looking for the number $\color{blue}{f(n,k)}$ of different paths to walk from $(0,0)$ to $(n,k), n,k\geq 0$ in a minimum number of steps.

At first we determine $s(n,k)$, the number of steps needed to go from $(0,0)$ to $(n,k)$. It is easy to see that the number of valid paths on the $x$-axis resp. $y$-axis is

\begin{align*} s(2n,0)&=s(2n-1,0)=n\qquad n\geq 1, \\ s(0,2k)&=s(0,2k-1)=k\qquad k\geq 1 \end{align*}

The number of steps needed to go from $(0,0)$ to $(n,k)$ in a minimum number of steps can be determined by first going horizontally to $(n,0)$ and then vertically from $(n,0)$ to $(n,k)$.

We conclude the number of steps $s(n,k)$ from $(0,0)$ to $(n,k)$ is given as \begin{align*} \color{blue}{s(2n,2k)} &\color{blue}{=s(2n-1,2k)}\\ &\color{blue}{=s(2n,2k-1)}\\ &\color{blue}{=s(2n-1,2k-1)} \color{blue}{=n+k}\tag{2} \end{align*}

For small values $n,k$ the numbers $s(n,k)$ and $f(n,k)$ are given in the graphics below:    

We denote with $[x^n]$ the coefficient of $x^n$ of a series and we encode the steps in (1) algebraically as \begin{align*} \color{blue}{x+x^2+y+y^2}\tag{3} \end{align*}

In the following we consider the case $f(2n,2k)$. We obtain for $n,k\geq 1$ \begin{align*} \color{blue}{f(2n,2k)}&=[x^{2n}y^{2k}]\left(x+x^2+y+y^2\right)^{n+k}\\ &=[x^{2n}y^{2k}]\sum_{j=0}^{n+k}\binom{n+k}{j}\left(x+x^2\right)^j\left(y+y^2\right)^{n+k-j}\\ &=\sum_{j=0}^{n+k}\binom{n+k}{j}[x^{2n-j}](1+x)^j[y^{k-n+j}](1+y)^{n+k-j}\\ &\qquad\qquad\cdot[[2n\geq j]][[j\geq n-k]]\tag{4}\\ &\,\,\color{blue}{=\sum_{j=0}^{n+k}\binom{n+k}{j}\binom{j}{2n-j}\binom{n+k-j}{k-n+j}}\\ &\qquad\qquad\color{blue}{\cdot[[2n\geq j]][[j\geq n-k]]} \end{align*} The other cases listed in (2) can be calculated similarly.

In (4) we use the rule $[x^p]x^qA(x)=[x^{p-q}]A(x)$. We also use Iverson brackets to assure that powers of $x$ resp. $y$ are non-negative.