# enumerative meaning of natural q-Catalan numbers

Define $[n]=(1-q^n)/(1-q)$ and $[n]!=[1][2][3] \cdots [n]$, so that $[2n]!/[n]![n+1]!$ is a polynomial in $q$ (the most algebraically natural $q$-analogue of the Catalan numbers); what enumerative interpretation(s) does it have, vis-a-vis the standard members of the "Catalan zoo"? I would be especially interested in answers pertaining directly to triangulations of polygons, without any intervening bijections.

-

These $q$-Catalan numbers have been studied mainly as the generating function of statistics on Dyck paths, such as the Major index. They are also a special case of the q,t-Catalan numbers of Garsia and Haiman, related by $$\frac{1}{[n+1]_q}\left[{2n\atop n}\right]_q=q^{\binom{n}{2}}C_n(q,1/q),$$ so they can be related to the bounce and area statistics as well as some statistics on parking functions which have been investigated in the context of these general polynomials.

As far as statistics on triangulations, I believe there is some interest from the folks who work on cyclic sieving phenomena. In fact, the triple $$(\mathcal T_{n+2},C_{n+2},\frac{1}{[n+1]_q}\left[{2n\atop n}\right]_q)$$ exhibits a cyclic sieving phenomenon, in the sense that plugging in primitive $d$-roots of unity in the $q$-Catalan numbers counts triangulations with $d$-fold symmetry. The main obstacle in finding a combinatorial proof of this fact (originally due to Reiner-Stanton-White) is precisely finding a weight on triangulations on $n+2$-gons so that $$\sum _{T\in \mathcal T _{n+2}}w(T)=\frac{1}{[n+1]_q}\left[{2n\atop n}\right]_q$$ and $w$ is natural in the sense that it is well behaved with respect to rotations. See these slides of Sagan-Roichman for more information on this. In particular, I don't think there is a very satisfactory answer to your question known at the moment (but I hope I'm wrong).

-

You can find one answer in Enumerative Combinatorics II by R. Stanley; see Excercise 34 (b) in Chapter 6. This would need to be translated to triangulations of polygons.

-

Another less known interpretation of MacMahon's $q$-Catalan numbers is

$$\sum_{\pi \in \mathcal{S}_n(231)} q^{\operatorname{maj}(\pi) + \operatorname{imaj}(\pi)} = \frac{1}{[n+1]_q} \begin{bmatrix} 2n \newline n \end{bmatrix}_q,$$ where $\mathcal{S}_n(231)$ is the set of all permutations of length $n$ avoiding the pattern $231$, and where $\operatorname{maj}(\pi)$ is the major index, and where $\operatorname{imaj}(\pi) := \operatorname{maj}(\pi^{-1})$ is the inverse major index (see http://arxiv.org/abs/0803.3706).

I would actually be very surprised if there where a known direct statistic on triangulations giving MacMahon's $q$-Catalan numbers. I agree with Gjergji that the cyclic sieving interpretation seems to be the best known combinatorial interpretation directly in terms of triangulations.

-

Seem my random speculations below. It never hurts to look in the OEIS and it would appear that the coefficient of $q^k$ in $\frac{1}{[n+1]}\left[{2n\atop n}\right]_q$ is the number of Dyck words of length 2n having major index k . I have not had time to look into translating that into triangulations.

OLDER

We do know that the $q$-binomial coefficient $$\left[{m\atop k}\right]_q=\frac{[m]!}{[k]![m-k]!}$$ is a polynomial (with non-negative integer coefficients) equal to $\binom{m}{k}$ when $q=1$ and that the coeffcient of $q^d$ is the number of ordered lists of type $0^k1^{m-k}$ having $d$ inversions. Equivalently, the number of lattice paths from $(0,0)$ to $(k,m-k)$ which enclose an region of area $d$ (with the $x$-axis and $x=k$).

Each of the lattice paths counted by $\binom{2n}{n}$ has an excedence $0 \le e \le n$ which is the number of horizontal edges above the diagonal. Each value of $e$ occurs $\frac{1}{n+1}\binom{2n}{n}$ times and the Catalan numbers count the paths of excedence $0.$

These $q$-Catalan polynomials $\frac{1}{[n+1]}\left[{2n\atop n}\right]_q$ again have non-negative integer coefficients and for $q=1$ equal the Catalan numbers which the excedence $0$ lattice paths from $(0,0)$ to $(2n,n)$. One could dream that there is an interpretation of the coefficient of $q^d$ but I certainly can't find one. A recurrence relation might be helpful in back constructing an interpretation.

The obvious greedy guess fails. For that one would have a recurrence $C_q(n+1)=\sum q^{(k+1)(n-k)}C_q(k)C_q(n-k).$ Those polynomials do not have a strong claim on being a natural q-analogue.

-
The statistic on Dyck paths is is actually "well known", see for example the paper by Christian Stump already mentioned. (I believe it also appears in papers of Christian Krattenthaler.) – Martin Rubey Apr 19 '12 at 4:55

To build on Bruce's answer, if we unwind the standard bijection between Dyck paths and triangulations, we get the following:

We'll write a chord as $(ij)$, meaning that it joins vertices $i$ and $j$. For every chord $(i,j)$, there are two triangles $(ijk)$ and $(ji \ell)$ containing $(ij)$. If $i < k < j < \ell$, we'll say that this chord is up-flippable; if $k < i < \ell < j$, we will say that the chord is down-flippable. As you probably know, the Tamari lattice is the poset structure on triangulations generated by up-flips.

The valleys of a Dyck path are in bijection with the down-flippable chords. If I have not made any errors, given a down-flippable chord $(ij)$, the index of that valley is $$2 \# \{ (abc) \in T : a<b \leq i<j \leq c\} + \# \{ (abc) \in T : a\leq i < j \leq b< c \}$$ where $T$ is the set of triangles in the triangulation.

So the final answer is to sum the above quantity over all down-flippable $(ij)$.

-
David, I don't think this works for n=2; your statistic is trivially 0 on both triangulations of the 4-gon, but the q-polynomial we're after is q^0+q^2, not 2q^0. Right? – James Propp Apr 16 '12 at 7:43
Sorry, try it now. – David Speyer Apr 16 '12 at 16:00
For $n=2$, the triangulation with chord (13) is supposed to give 0, because the chord is upflippable; the triangulation with (24) is supposed to give 2 because of 124. – David Speyer Apr 16 '12 at 16:03