# What does the $q$-Catalan Numbers count?

I had completed a paper describing the $q$-Catalan numbers, which is the $q$-analog of the Catalan numbers.

The $n$-th Catalan numbers can be represented by:

$$C_n=\frac{1}{n+1}{2n \choose n}$$

and with the recurrence relation:

$$C_{n+1}=\sum^n_{i=0}C_i C_{n-i}\ \ \ \ \ \forall n\geq 0$$

Now, for the $q$-analog, I know the definition of that can be defined as:

$$\lim_{q\to 1}\frac{1-q^n}{1-q}=n$$

and we know that the definition of the $q$-analog, can be defined like this:

$$[n]_q=\frac{1-q^n}{1-q}=1+q+q^2+q^3+\cdots+q^{n-1}$$

which this is the $q$-analog of $n$.

and that for that $q$-analog of ${2n\choose n}$:

$$C_n(q)=\frac{1}{[n+1]_q}\begin{bmatrix}2n\\ n\end{bmatrix}_q$$

So, everything up to this point I know what I'm doing, and I'm not sure if I did everything correct after this

So, in order to generate the $q$-Catalan Numbers, I will need to use the Lagrange inversion formula.

And, then I got something like this:

$$G(X)=\sum^\infty_{i=0}C_i x^i$$

where $G(x)$ is the generating function, and that

$$G(x)=G_q(x)=\sum^\infty_{i=0}C_n(q)x^n=\sum^\infty_{i=0}C_nx^n=1+x+x^2(1+q)+\cdots$$

Since I know that for Catalan Numbers, it's true:

$$G(x)=(G(x))^2+1$$

So, the $q$-analog will just be:

$$G_q(x)=G(x)G_q(x)+1$$

So the recurrence relation for the $q$-analog Catalan Numbers:

$$C_{n+1}(q)=\sum^n_{i=0}C_i C_{n-1}q^i$$

It just doesn't sound right here...

Also, I don't have a clue that what does the $q$-Catalan Numbers count, can anyone help me with that or give me like a clue?

Help appreciated!

-
Off topic up to the last line for asking others to check your work for you, and off topic after that for asking others to do your googling for you. –  Steven Landsburg Apr 27 '13 at 6:11
and I don't think there is such a thing as 'the' q-analog –  Vasu vineet Apr 27 '13 at 6:58
I'm not sure the $q$-Catalan numbers "count things", since they are not integers –  Adrien Hardy Apr 27 '13 at 9:18
@Adrien Hardy: They might still have enumerative significance. For example, the $q$-binomial coefficient ${n\brack k}_q$, when $q$ is specialized to a prime power, counts the number of $k$-dimensional subspaces of $(\mathbb{F}_q)^n$. –  Brad Hannigan-Daley Apr 27 '13 at 12:21
Does math.upenn.edu/~jhaglund/books/qtcat.pdf Theorem 1.6 help? –  darij grinberg Apr 27 '13 at 12:54

• Your first q-Catalan numbers defined by the $q$-binomials is MacMahon's q-Catalan numbers which is (and I don't actually know many others) the major generating function on Dyck paths, where the descent set is given by the positions of the valleys.
• Your second $q$-Catalan numbers given by the recurrence is, on the other hand, the area generating function on Dyck paths.
Both are deeply related in the context of the $q,t$-Catalan numbers appearing in the theory of symmetric function as a bigraded Hilber series of (the alternating part of) the space of diagonal coinvariants.
As Darij mentions, both (and as well the $q,t$-Catalan numbers and the space of diagonal coinvariants) can be found e.g. in Jim Haglund's book http://www.math.upenn.edu/~jhaglund/books/qtcat.pdf. You actually find quite a bit as well in our online project http://www.findstat.org/DyckPaths/Area and http://www.findstat.org/DyckPaths/MajorIndex.
I just remembered that I gave a link to another statistic that gives MacMahon's $q$-Catalan numbers here: mathoverflow.net/questions/93136/… –  Christian Stump Apr 30 '13 at 15:20