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.


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

  • $\begingroup$ Thanks for the response. Actually, what I am trying to count is prefixes of Catalan Strings of length $p+q$, if my understanding of Dyck words is correct. Going back again and redoing it I realise what I was foolishly missing before. The recurrence $c_{p,q}=c_{p−1,q}+c_{p,q−1}$ yields $$c(x,y)-1=x c(x,y) + xy \frac{c(x,y) -1}{x}$$ which simplifies to $$c(x,y) = \frac{1-y/x}{1-x-y}$$ and this gives the expected result. So I tihnk my recurrence is ok. Thanks again. $\endgroup$
    – healyp
    Mar 18 '12 at 15:25

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.