MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question

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

share|cite|improve this answer

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.

share|cite|improve this answer

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

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.

share|cite|improve this answer


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.


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.

share|cite|improve this answer
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)$.

share|cite|improve this answer
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

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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