Hello,


I'm trying to reinvent the wheel here by deriving the formula for Dyck Words of length p+q, that is, p left parens and q right parens. The answer of course is $\binom{p+q}{q} - \binom{p+q}{q-1}$.


Using an OGF, if I'm right, starting from the recurrence $c\_{p,q} = c\_{p-1,q} + c\_{p,q-1}, \quad q \leq p$ and letting $c(x,y) = \sum\_{p=0} \sum\_{q\leq p}c\_{p,q}x^p y^q$ I should get $c(x,y)-1 = x \times c(x,y) + y \times f(x,y)$.


It is this $f(x,y)$ that is troubling me. Reverse engineering the answer it seems to me that I need $c(x,y)(1-x-y)=1-y/x$ which would have come from $c(x,y)-1 = x \times c(x,y) + y \times (c(x,y)-1/x)$. I don't see how this could be.


Could somebody enlighten me? Thanks.



Generating function for Dyck Words
I'm not completely sure what the problem is, but 
$$(1-x-y) c(x,y) = 1 - y C(xy) = 1 - \frac{1-\sqrt{1-4xy}}{2x},$$
where $C(z)$ is the Catalan number generating function,
$$C(z) =\sum\_{n=0}^\infty C\_n z^n = \frac{1-\sqrt{1-4z}}{2z},$$
and $C\_n = c\_{n,n}=\frac{1}{n+1}\binom{2n}{n}$.
If we set $c\_{p,q}=0$ for $p<q$ then this formula shows how the recurrence
$c\_{p,q}=c\_{p-1,q}+c\_{p,q-1}$ fails when $p=q=0$ and when $q=p+1$.


