# Extracting coefficients from two-dimensional generating function

We have the two-dimensional recurrent series $$F(r+1,s+2) = F(r,s) + F(r,s+1) + F(r,s+2)$$ and the boundary conditions $$F(r,0)=1$$, $$F(0,s)=0$$ for all $$s>0$$ and $$F(0,0)=1$$ and $$F(r,1)=r$$. This series is for all $$r\geq0$$ and $$s\geq0$$. How do we find the general expression for the coefficient?

I used the 2D generating function $$G(x,y) = \sum_{r,s\geq0} F(r,s) x^r y^s$$ and applied the boundary conditions to obtain the following expression for G:

$$G(x,y) = \frac{xy}{(x-1)(1-x-xy-xy^2)}$$

which I can split to obtain

$$G(x,y) = \frac{-1}{1-x} \frac{xy}{1-x-xy-xy^2}$$

and the term $$\frac{-1}{1-x}$$ can be expressed as $$-(1+x+x^2+x^3+\dots)$$. I am having problems with the other term $$\frac{xy}{1-x-xy-xy^2}$$.

I referred to this post which handled a bivariate generating function but unfortunately I couldn't recast $$\frac{xy}{1-x-xy-xy^2}$$ into a term similar to $$\frac{1}{1-y(x+1)}$$ which was presented there. The closest I could get was:

$$\frac{xy}{1-x-xy-xy^2} = \frac{xy}{1-x(y^2+y+1)} = \frac{xy}{1-x[(y+1)^2-y]}$$

which is again not similar to the expression $$H(x,y) = \frac{xy}{1-x-y}$$ in this post.

All suggestions welcome.

We use the coefficient of operator $$[z^n]$$ do denote the coefficient of $$z^n$$ in a series.

We obtain for $$m,n\geq 1$$:

\begin{align*} \color{blue}{[x^my^n]}&\color{blue}{\frac{xy}{1-x(1+y+y^2)}}\\ &=[x^{m-1}y^{n-1}]\frac{1}{1-x(1+y+y^2)}\tag{1}\\ &=[x^{m-1}y^{n-1}]\sum_{j=0}^\infty x^j\left(1+y+y^2\right)^j\tag{2}\\ &=[y^{n-1}](1+y+y^2)^{m-1}\tag{3}\\ &=[y^{n-1}]\sum_{j=0}^{m-1}\binom{m-1}{j}y^j(1+y)^j\tag{4}\\ &=\sum_{j=0}^{\min\{m-1,n-1\}}\binom{m-1}{j}[y^{n-1-j}](1+y)^j\tag{5}\\ &\,\,\color{blue}{=\sum_{j=0}^{\min\{m-1,n-1\}}\binom{m-1}{j}\binom{j}{n-1-j}}\tag{6}\\ \end{align*}

Comment:

• In (1) we use the rule $$[z^{p-q}]A(z)=[z^p]z^qA(z)$$.

• In (2) we do a geometric series expansion.

• In (3) we select the coefficient of $$x^{m-1}$$.

• In (4) we apply the binomial theorem.

• In (5) we apply the rule from (1) again. We also set the upper limit of the sum accordingly, since the exponent of $$y^{n-1-j}$$ is non-negative.

• In (6) we select the coefficient of $$y^{n-1-j}$$.

• Thank you for this beautiful derivation! I have a quick question: what would happen in step (2) if the rule $[z^{p-q}]A(z) = [z^p]z^q A(z)$ had been applied to $x$? Would this change the result since the expression becomes $[y^{n-1}]\sum_{j=0}^{\infty} [x^{m-1-j}] (1+y+y^2)^j$? – MrABBA Apr 19 at 14:34
• @MrABBA: You're welcome. In (2) there is only $j=m-1$ to consider, since other values of $j$ do not contribute to $x^{m-1}$. This situation is different to (5) where we additionally have $(1+y)^j$ which also do contribute. In (2) we have accordingly to the rule (1) the situation $[x^{m-1}]x^{m-1}=[x^0]$ which is the constant part and needs not be explicitly written. – Markus Scheuer Apr 19 at 14:43
• @MrABBA: We can write your example in the comment as $[y^{n-1}]\sum_{j=0}^{\infty}[x^{m-1-j}]x^0(1+y+y^2)^j=[y^{n-1}](1+y+y^2)^{m-1}$ since $j$ has to be $m-1$ whereas terms with other values of $j$ do not contribute. – Markus Scheuer Apr 19 at 14:51