Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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.

share|improve this question
1  
Sorry, I should probably have dug a bit deeper before posting my crie de coeur. I found a reference to this paper by Deutsch sciencedirect.com/science/article/pii/S0012365X98003719 and the answer may be there. –  healyp Mar 17 '12 at 9:00
add comment

1 Answer 1

up vote 1 down vote accepted

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

share|improve this answer
    
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. –  healyp Mar 18 '12 at 15:25
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.