3
$\begingroup$

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.

Improve this question
$\endgroup$
1

1 Answer 1

Reset to default
4
$\begingroup$

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

Improve this answer
$\endgroup$
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
    Commented Mar 18, 2012 at 15:25

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .