most recent 30 from http://mathoverflow.net 2013-05-21T16:50:51Z http://mathoverflow.net/feeds/question/91449 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/91449/generating-function-for-dyck-words healyp 2012-03-17T08:19:09Z 2012-03-17T21:02:58Z

<p>Hello,</p> <p>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}$.</p> <p>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)$.</p> <p>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.</p> <p>Could somebody enlighten me? Thanks.</p>

http://mathoverflow.net/questions/91449/generating-function-for-dyck-words/91492#91492 Ira Gessel 2012-03-17T21:02:58Z 2012-03-17T21:02:58Z

<p>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 <code>$p&lt;q$</code> 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$.</p>