# 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$.

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$$.

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.