Counting the ways on grid if one can move from $(x,y)$ to $(x+a, x+b)$ for arbitrary $x,y,a,b\geq 0$.

Question

On 2 dimensional grid, consider the situation that one can move from $(p,q)$ to $(p+α,q+β)$ at once for arbitrary integer $p,q,α,β\geq 0 \land (α,β)\neq(0,0)$. I want to count how many ways are there to move from (0,0) to (x,y). I proved there is $\sum_{i=0}^{\min(x,y)}\binom{x}{i}\binom{y}{i}2^{x+y-(i+1)}$ by combinatorial view. Then, can we derive this using formal power series?

I've tried to derive this, however different formula appear and I cannot get the combinatorial interpretation of that formula.

The number of ways to get $(x,y)$ by $n$ moves is

\begin{align} &[s^x t^y]\left(\frac{1}{1-s}\frac{1}{1-t}-1 \right)^n \\ =&[s^x t^y]\left(\frac{s+t-st}{(1-s)(1-t)}\right)^n \end{align}

Note that $[s^x t^y] f(s,t)$ is the coefficient of $s^x t^y$ term of $f(s,t)$.

Summing up for $n=1,2,...,$ we can get the number of ways to go to $(x, y)$ by arbitrary number of moves.

\begin{align} &[s^x t^y]\sum_{n=1}^\infty \left(\frac{s+t-st}{(1-s)(1-t)}\right)^n \\ =&[s^x t^y]\frac{s+t-st}{1-2(s+t-st)} \\ =&[s^x t^y]\sum_{i=0}^{\min(x,y)}2^{x+y-i-1} (s+t-st)^{x+y-i} \\ =&\sum_{i=0}^{\min(x,y)}2^{x+y-i-1} (-1)^i \frac{(x+y-i)!}{(x-i)!(y-i)!i!} \end{align}

However, this seems different from $\sum\binom{x}{i}\binom{y}{i}2^{x+y-(i+1)}$. Also, I cannot come up with the combinatorial interpretation of the formula we get.

UPDATE

I want to explain in details for the following.

\begin{align} &[s^x t^y]\sum_{n=1}^\infty \left(\frac{s+t-st}{(1-s)(1-t)}\right)^n \\ =&[s^x t^y]\left(\frac{s+t-st}{1-2(s+t-st)} - \frac{(1-s)(1-t)\lim_{N\to\infty}\left(\frac{s+t-st}{(1-s)(1-t)}\right)^N}{1-2(s+t-st)} \right)\\ \end{align}

Here, I suppose the term, $-\frac{(1-s)(1-t)\lim_{N\to\infty}\left(\frac{s+t-st}{(1-s)(1-t)}\right)^N}{1-2(s+t-st)}$ can be treated as $0$ because if we put $s=0$ and $t=0$, $\frac{s+t-st}{(1-s)(1-t)}=0$ which means the degree of this term will go $\infty$ if we take power of $\infty$. Thus this term have nothing to do with the $s^x t^y$ term and it's ok to treat it as $0$.

Answer 1

We consider non-negative integers $x,y$ and to get a first impression we start calculating the first few values of \begin{align*} \sum_{j\geq 0}\binom{x}{j}\binom{y}{j}2^{x+y-{j+1}}\tag{1} \end{align*} We write $j\geq 0$ and recall $\binom{p}{q}=0$ if $q>p$. The values of (1) are given in the picture below and we observe the sequence is archived in OEIS as A059576.

                                          

The values in OEIS coincide with (1) besides $(x,y)=(0,0)$ which is set to $1$, so that the value of $(x,y)$ is the sum of the values with smaller $x$ or smaller $y$ (an example marked in blue).

We now assume $x,y\geq 0, x+y\geq 1$ and obtain \begin{align*} \color{blue}{[s^xt^y]}&\color{blue}{\sum_{n=1}^\infty\left(\frac{s+t-st}{(1-s)(1-t)}\right)^n}\\ &=[s^xt^y]\left(\frac{1}{1-\frac{s+t-st}{(1-s)(1-t)}}-1\right)\\ &=[s^xt^y]\frac{s+t-st}{1-2(s+t-st)}\\ &=\frac{1}{2}[s^xt^y]\frac{1}{1-2(s+t-st)}\tag{2}\\ &=\frac{1}{2}[s^xt^y]\sum_{j=0}^\infty 2^j(s+t-st)^j\\ &=\frac{1}{2}[s^xt^y]\sum_{j=0}^\infty2^j \sum_{k=0}^j\binom{j}{k}s^k(1-t)^kt^{j-k}\\ &=\frac{1}{2}[s^xt^y]\sum_{k=0}^\infty\sum_{j=k}^\infty 2^j\binom{j}{k}s^k(1-t)^kt^{j-k}\tag{3}\\ &=\frac{1}{2}[t^y]\sum_{j=x}^\infty 2^j\binom{j}{x}(1-t)^xt^{j-x}\tag{4}\\ &=\frac{1}{2}[t^y]\sum_{j=0}^\infty 2^{j+x}\binom{x+j}{j}t^j(1-t)^x\\ &=\frac{1}{2}\sum_{j=0}^y2^{j+x}\binom{x+j}{j}[t^{y-j}](1-t)^x\\ &=\frac{1}{2}\sum_{j=0}^y2^{j+x}\binom{x+j}{j}\binom{x}{y-j}(-1)^{y-j}\tag{5}\\ &=\sum_{j=0}^y\binom{x+y-j}{y-j}\binom{x}{j}2^{x+y-j-1}(-1)^{y-j}\tag{6}\\ &=2^{x+y-1}\sum_{j\geq 0}\binom{x}{j}\left(-\frac{1}{2}\right)^j[z^{y-j}](1+z)^{x+y-j}\\ &=2^{x+y-1}[z^y](1+z)^{x+y}\sum_{j\geq 0}\binom{x}{j}\left(-\frac{z}{2(1+z)}\right)^j\\ &=2^{x+y-1}[z^y](1+z)^{x+y}\left(1-\frac{z}{2(1+z)}\right)^x\\ &=2^{x+y-1}[z^y](1+z)^{y}\left(1+\frac{z}{2}\right)^x\\ &=2^{x+y-1}[z^y](1+z)^{y}\sum_{j\geq 0}\binom{x}{j}\left(\frac{z}{2}\right)^j\\ &=\sum_{j\geq 0}\binom{x}{j}[z^{y-j}](1+z)^y2^{x+y-j-1}\\ &=\sum_{j\geq 0}\binom{x}{j}\binom{y}{y-j}2^{x+y-j-1}\\ &\,\,\color{blue}{=\sum_{j\geq 0}\binom{x}{j}\binom{y}{j}2^{x+y-j-1}} \end{align*} and the claim follows.

Comment:

• In (2) we use $\frac{2(s+t-st)}{1-2(s+t-st)}=\frac{1}{1-2(s+t-st)}-1$. We can ignore the term $1$ which does not contribute to $[s^xt^y]$ since $x+y\geq 1$.

• In (3) we exchange the summation of series.

• In (4) we select the coefficient of $s^x$.

• In (5) we select the coefficient of $t^{y-j}$.

• In (6) we change the order of summation $j\to y-j$.

Note: The expression with the exponent $\infty$ is mathematically not sound and should be avoided.