MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top


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|cite|improve this question
Sorry, I should probably have dug a bit deeper before posting my crie de coeur. I found a reference to this paper by Deutsch and the answer may be there. – healyp Mar 17 '12 at 9:00
up vote 3 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|cite|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

Your Answer


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.