enumerative meaning of natural q-Catalan numbers

Question

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.

Answer 1

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).

Answer 2

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.

Answer 3

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.

Answer 4

NEWEST

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.

Answer 5

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)$.