An $n$-Dyck path (or a Catalan path) is a lattice path $P$, unit East and North steps, in an $n\times n$ square grid which stays (weakly) above the main diagonal. Let $\square_n$ denote all such paths. Define the area of a path $P$ to be the number of full squares below the path and above the diagonal. Then one variant of a $q$-Catalan number is in the form $$C_n(q)=\sum_{P\in\square_n}q^{area(P)}.$$ A few examples: $C_1(q)=1,\, C_2(q)=1+q,\, C_3(q)=1+2q+q^2+q^3$.

There is this notion of $q,t$-Catalan numbers so that $C_n(q)=C_n(q,1)$.

I'm finding (after some fooling around) the following generating function which I've not encountered in the literature.

Question. Is this known or can you provide a proof? $$\sum_{n=0}^{\infty}C_n(q)\,z^n =\frac{\sum_{k=0}^{\infty}q^{k^2}\prod_{j=1}^k\frac{z}{q^j-1}} {{\sum_{k=0}^{\infty}q^{k(k-1)}\prod_{j=1}^k\frac{z}{q^j-1}}}$$

  • Nemo: Close, but (39) has k(k+1) in the denominator, and neither reindexing nor fiddling with (-a) gets it, I don't think. – William J. Keith Feb 26 '17 at 17:26
  • Yes, these and their many generalizations are known by many. That is not the question. I ask if the generating function equation as given above is known for Catalan or can be given a proof. If you have such info, please provide. – T. Amdeberhan Feb 26 '17 at 19:16
up vote 9 down vote accepted

The functions $$ C_n(q)=\sum_{P\in\square_n}q^{area(P)} $$ satisfy the following recurrence relation $$ C_n(q)=\sum_{k=1}^nq^{k-1}C_{k-1}(q)C_{n-k}(q).\tag{1} $$ Proof. (taken from the book "The q, t-Catalan Numbers and the Space of Diagonal Harmonics" by J. Haglund, page 14, typo corrected)

We break up our path $P$ according to the “point of first return” to the line y = x. If this occurs at (k, k), then the area of the part of $P$ from (0, 1) to (k − 1, k), when viewed as an element of $\square_{k-1}$, is $k − 1$ less than the area of this portion of $P$ when viewed as a path in $\square_{n}$.$\qquad\qquad\qquad~~~~~\Box$

The generating function $$ G(z,q)=\sum_{n=0}^\infty C_n(q)z^n $$ satisfies the functional equation, which is a direct consequence of $(1)$: $$ G(z,q)-1=zG(z,q)G(qz,q). $$ We rewrite it for convenience as $$ \frac{1}{G(z,q)}=1-zG(qz,q).\tag{2} $$ It is known that the generalized Rogers-Ramanijan continued fraction, formula (39), $$ F(a,q)=\frac{\sum_{k=0}^\infty\frac{(-a)^kq^{k^2}}{(q;q)_k}}{\sum_{k=0}^\infty\frac{(-a)^kq^{k^2+k}}{(q;q)_k}}=1-\cfrac{aq}{1-\cfrac{aq^2}{1-\cfrac{aq^3}{1-...}}}, $$ satisfies the functional equation $$ F(a,q)=1-\frac{aq}{F(aq,q)}.\tag{3} $$ Since $G(0,q)=F(0,q)=1$ it is clear from comparing $(2)$ and $(3)$ that $$ \frac{1}{G(z,q)}=F(z/q,q)=\frac{\sum_{k=0}^\infty\frac{(-z)^kq^{k^2-k}}{(q;q)_k}}{\sum_{k=0}^\infty\frac{(-z)^kq^{k^2}}{(q;q)_k}}, $$ as required.

  • z/q and invert, of course. I should have spotted it. Yes, this works. – William J. Keith Feb 26 '17 at 21:19
  • Page 14? More like page 8, Proposition 1.6.1? – darij grinberg May 27 '17 at 19:18
  • @darijgrinberg , yes, you are right, thanks – Nemo May 28 '17 at 8:27

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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