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.


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.

                                          enter image description here

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.


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


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.