5
$\begingroup$

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

$\endgroup$
3
  • $\begingroup$ Nemo: Close, but (39) has k(k+1) in the denominator, and neither reindexing nor fiddling with (-a) gets it, I don't think. $\endgroup$ Commented Feb 26, 2017 at 17:26
  • $\begingroup$ Some related formulas (though not this exact formula) can be found in Section 10 of my paper "A Noncommutative Generalization and q-Analog of the Lagrange Inversion Formula", Trans. Amer. Math. Soc. 257 (1980), 455–482, jstor.org/stable/1998307. $\endgroup$
    – Ira Gessel
    Commented Jul 25, 2023 at 2:24
  • $\begingroup$ @IraGessel: Thank you. $\endgroup$ Commented Jul 25, 2023 at 16:06

1 Answer 1

10
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ z/q and invert, of course. I should have spotted it. Yes, this works. $\endgroup$ Commented Feb 26, 2017 at 21:19
  • $\begingroup$ Page 14? More like page 8, Proposition 1.6.1? $\endgroup$ Commented May 27, 2017 at 19:18
  • $\begingroup$ @darijgrinberg , yes, you are right, thanks $\endgroup$
    – Nemo
    Commented May 28, 2017 at 8:27

You must log in to answer this question.

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