Deriving the generating function for the Catalan triangle

Question

I'm hoping for help in deriving the two-variable generating function for the Catalan triangle, also known as a truncated version of Pascal's triangle. There are a few variations floating around, so to be specific we take the Catalan triangle (with 0's) to be OEIS A053121 $$\begin{matrix} 1\\ 0&1\\ 1&0&1\\ 0&2&0&1\\ 2&0&3&0&1\\ 0&5&0&4&0&1\\ 5&0&9&0&5&0&1\\ \dots\\ \end{matrix}$$ where for the top row $a_{0,0}=1$ and $a_{0,c}=0$ for $c\ge1$, for the leftmost column where the truncation takes place $a_{r,0}=a_{r-1,1}$ for $r\ge1$, and the general recurrence relation is $a_{r,c}=a_{r-1,c-1}+a_{r-1,c+1}$ for $r,c\ge1$. Notice that the non-zero entries in the leftmost column seem to form the Catalan numbers.

Here is what I've got so far, following THE METHOD in chapter 1 of Wilf's generatingfunctionology book. First, define the two-variable generating function $$f(x,y)=\sum_{r,c\ge0}a_{r,c}\,x^cy^r$$ and the one-variable generating functions $$Row_r(x)=\sum_{c\ge0}a_{r,c}\,x^c\text{ and }Col_c(y)=\sum_{r\ge0}a_{r,c}\,y^r$$ so that $$f(x,y)=\sum_{r\ge0} Row_r(x) y^r=\sum_{c\ge0}Col_c(y) x^c.$$ You can multiply the terms of the general recurrence relation by $x^c$ and sum over $c\ge1$ to get $$Row_r(x)=\left(x+\frac1x\right)Row_{r-1}(x)-\frac1x a_{r-1,0}$$ and then multiply the terms of this functional relation by $y^r$ and sum over $r\ge1$ to get $$f(x,y)=\frac{yCol_{0}(y)-x}{x^2y+y-x}.$$

The problem is that this formulation of $f$ depends on the generating function for the leftmost column. My question is:

without using the observation that the non-zero entries in the leftmost column form the Catalan numbers, and only using the recurrence relation above for $a_{r,c}$ with its boundary conditions, how can you determine the two-variable generating function $f(x,y)$?

Incidentally, the OEIS page for the Catalan triangle gives $$f(x,y)=\frac{c(y^2)}{1-xyc(y^2)},$$ where $c(y)=\frac{1-\sqrt{1-4y} }{2y}$ is the generating function for the Catalan numbers, as a note from Emeric Deutsch.

Answer 1

To set the stage, define the row and column generating functions

$$R_r(z)=\sum_{c=0}^\infty a_{r,c}z^c~~~,~~ Q_c(y)=\sum_{r=0}^\infty a_{r,c}y^r$$

Applying the recurrence relation to both yields the recurrences

$$R_r(z)=(z+1/z)R_{r-1}(z)-\frac{a_{r-1,0}}{z}$$ $$Q_c(y)=y(Q_{c-1}(y)+Q_{c+1}(y))$$

The first one depends explicitly on the values of the first column, but the second one does not; this allows us to solve for $Q_c$ using the first two columns as initial conditions. Denoting $\kappa_{\pm}(y)=\frac{1\pm\sqrt{1-4y}}{2y}$, the general solution can be written as

$$Q_{c}(y)=A(y\kappa_+(y^2))^c+B(y\kappa_-(y^2))^c$$

Note that $A,B$ generally depend on $y$ and can be determined in terms of the first column generating function $Q_0$, since the second column can be expressed as a function of the first, $yQ_1(y)=Q_0(y)-1$. The expressions read

$$A=\frac{(\kappa_+(y^2)y^2-1)Q_0(y)+1}{y^2(\kappa_+(y^2)-\kappa_-(y^2))}$$ $$B=\frac{(\kappa_-(y^2)y^2-1)Q_0(y)+1}{y^2(\kappa_-(y^2)-\kappa_+(y^2))}$$

Now, the complete generating function $F(z,y)=\sum_{r=0}^\infty R_r(z)y^r=\sum_{c=0}^\infty Q_c(y)z^r$ can be represented in two different ways. By the row recurrence relation we can show that

$$F(z,y)=\frac{yQ_0(y)-z}{y(z^2+1)-z}$$

On the other hand, from the results on the column recurrence, it holds that

$$F(z,y)=\frac{A}{1-zy\kappa_{-}(y^2)}+\frac{B}{1-zy\kappa_{+}(y^2)}$$

One can show that two representation provide no new information on $Q_0(y)$. To make progress, we take a page from the method of images for linear PDEs- the problem we face here is very similar; the boundary condition $a_{r,-1}=0$ is difficult to work with. We can eliminate it using the method of images, and instead work with the recursion

$$a_{r,c}=a_{r-1,c-1}+a_{r-1,c+1},~~a_{0,c}=\delta_{c,1}-\delta_{c,-1}, c\in\mathbb{Z}$$

We will show ad hoc that this satisfies the requisite boundary condition $a_{r,0}=0$ (moved to the right by one unit compared to the original) and hence, when restricting to $c>0$, this should yield the required answer. We note that each of the terms in the initial condition generate a Pascal triangle, and since the recurrence is linear, the two triangles are superimposed on each other. We can use the linearity to deduce that the solution is encoded in the following generating function

$$a_{r,c}=[z^c](z-1/z)(z+1/z)^r$$

It should be clear that $(z+1/z)^r$ generates a row of the Pascal triangle and $(z-1/z)$ takes into account the shift by one unit to the right and left respectively, as well as the change in sign for the mirror image. Extracting coefficients is done by expanding using the binomial identity

$$(z-1/z)(z+1/z)^r=\sum_{\ell=-1}^r \left[{r\choose\ell+1}-{r\choose\ell}\right]z^{-2\ell+r-1}$$

with the convention that ${r\choose\ell}=0$ if $ \ell<0 $ or $ \ell>r$. The coefficients we are interested in are those with positive powers of $z$. We can isolate those by considering only $\ell\leq \lfloor\frac{r-1}{2}\rfloor$.

With this work done, it is easy to show that the boundary condition $a_{r,0}=0$ is obeyed by showing that there is no constant coefficient in the above expression for any $r$; for $r$ even, the expansion skips the middle column, and for $r=2m+1$ odd, the coefficient is zero since it is equal to

$$[z^0](z-1/z)(z+1/z)^{2m+1}={2m+1\choose m+1}-{2m+1\choose m}=0$$

Finally, we can show that the non-zero components of the first column to the right are given by

$$[z^1](z-1/z)(z+1/z)^{2m}={2m\choose m}-{2m\choose m+1}=C_{m}$$

This shows that $Q_0(y)=\kappa_-(y^2)$ which then shows that generating function is given by

$$F(z,y)=\frac{y\kappa_-(y^2)-z}{y(z^2+1)-z}=\frac{\kappa_-(y^2)}{1-zy\kappa_-(y^2)}$$

since the following equalities hold: $$y\kappa_-(y^2)-z=y\kappa_-(y^2)(1-zy\kappa_+(y^2))$$ $$y(z^2+1)-z=(1-zy\kappa_+(y^2))(1-zy\kappa_-(y^2))$$