$q,t$-Catalan numbers $C_n(q,t)$

edit · history · discussion · files · long url · combinatorics polynomial

Polynomials

$n$

$C_n(q,t)$

q^3 + q^2*t + q*t^2 + t^3 + q*t

q^6 + q^5*t + q^4*t^2 + q^3*t^3 + q^2*t^4 + q*t^5 + t^6 + q^4*t + q^3*t^2 + q^2*t^3 + q*t^4 + q^3*t + q^2*t^2 + q*t^3

q^10 + q^9*t + q^8*t^2 + q^7*t^3 + q^6*t^4 + q^5*t^5 + q^4*t^6 + q^3*t^7 + q^2*t^8 + q*t^9 + t^10 + q^8*t + q^7*t^2 + q^6*t^3 + q^5*t^4 + q^4*t^5 + q^3*t^6 + q^2*t^7 + q*t^8 + q^7*t + 2*q^6*t^2 + 2*q^5*t^3 + 2*q^4*t^4 + 2*q^3*t^5 + 2*q^2*t^6 + q*t^7 + q^6*t + q^5*t^2 + 2*q^4*t^3 + 2*q^3*t^4 + q^2*t^5 + q*t^6 + q^4*t^2 + q^3*t^3 + q^2*t^4

q^15 + q^14*t + q^13*t^2 + q^12*t^3 + q^11*t^4 + q^10*t^5 + q^9*t^6 + q^8*t^7 + q^7*t^8 + q^6*t^9 + q^5*t^10 + q^4*t^11 + q^3*t^12 + q^2*t^13 + q*t^14 + t^15 + q^13*t + q^12*t^2 + q^11*t^3 + q^10*t^4 + q^9*t^5 + q^8*t^6 + q^7*t^7 + q^6*t^8 + q^5*t^9 + q^4*t^10 + q^3*t^11 + q^2*t^12 + q*t^13 + q^12*t + 2*q^11*t^2 + 2*q^10*t^3 + 2*q^9*t^4 + 2*q^8*t^5 + 2*q^7*t^6 + 2*q^6*t^7 + 2*q^5*t^8 + 2*q^4*t^9 + 2*q^3*t^10 + 2*q^2*t^11 + q*t^12 + q^11*t + 2*q^10*t^2 + 3*q^9*t^3 + 3*q^8*t^4 + 3*q^7*t^5 + 3*q^6*t^6 + 3*q^5*t^7 + 3*q^4*t^8 + 3*q^3*t^9 + 2*q^2*t^10 + q*t^11 + q^10*t + 2*q^9*t^2 + 3*q^8*t^3 + 4*q^7*t^4 + 4*q^6*t^5 + 4*q^5*t^6 + 4*q^4*t^7 + 3*q^3*t^8 + 2*q^2*t^9 + q*t^10 + q^8*t^2 + 2*q^7*t^3 + 3*q^6*t^4 + 3*q^5*t^5 + 3*q^4*t^6 + 2*q^3*t^7 + q^2*t^8 + q^7*t^2 + 2*q^6*t^3 + 2*q^5*t^4 + 2*q^4*t^5 + 2*q^3*t^6 + q^2*t^7 + q^4*t^4

Definition

The $q,t$-Catalan polynomial $C_n(q,t)$ [2] is the Dyck-path generating function in (1), using the area-sequence convention in (5).

Parameters

$n$

— semilength (a nonnegative integer)

Formulas

(1)

$C_n(q,t)=\sum_{D\in\operatorname{Dyck}_n} q^{\operatorname{dinv}(D)}t^{\operatorname{area}(D)}$, summed over Dyck paths $D$ of semilength $n$ [1].

(2)

$C_n(1,1)=\frac{1}{n+1}\binom{2n}{n}$.

(3)

$C_n(q,t)=C_n(t,q)$.

(4)

$C_0(q,t)=C_1(q,t)=1$ and $C_2(q,t)=q+t$.

Comments

(5)

For $n=0$ the area sequence is empty. For $n>0$, an area sequence is $(a_1,\ldots,a_n)$ with $a_1=0$ and $0\leq a_{i+1}\leq a_i+1$ for $1\leq i<n$. Its area is $\sum_i a_i$, and its dinv is the number of pairs $i<j$ with $a_i-a_j\in\{0,1\}$.

Programs

(P1)

Sage

from sage.combinat.q_analogues import qt_catalan_number

qt_catalan_number(7)

References

[1]

J. Haglund, The q,t-Catalan Numbers and the Space of Diagonal Harmonics, University Lecture Series 41, American Mathematical Society, Providence, RI, 2008.

[2]

A. M. Garsia and M. Haiman, A remarkable q,t-Catalan sequence and q-Lagrange inversion, J. Algebraic Combin. 5 (1996), 191-244.

[3]

L. Carlitz and J. Riordan, Two element lattice permutation numbers and their q-generalization, Duke Math. J. 31 (1964), 371-388.

[4]

P. A. MacMahon, Combinatory Analysis, Vol. II, Cambridge University Press, Cambridge, 1916.

Links

[5]

SageMath: q-analogues

Similar tables

Carlitz-Riordan $q$-Catalan numbers — stores the specialisation $C_n(q,1)$, equivalently the area generating function of Dyck paths. A reader holding that one-variable polynomial is likely to want the Carlitz-Riordan table; a reader holding the two-variable dinv-area polynomial wants this table.

MacMahon $q$-Catalan numbers — stores $\widetilde C_n(q)=q^{\binom n2}C_n(q,q^{-1})$, equivalently the Gaussian binomial quotient. A reader holding that one-variable quotient is likely to want the MacMahon table; a reader holding the full two-variable polynomial wants this table.

Data properties

Entries are of type: integral polynomial

How well the digits are known: exact

Table is complete: no (it holds the rows for $3\leq n\leq6$; the omitted rows with $n\leq2$ are the closed forms in (4))

How they were obtained:

Every entry is an exact polynomial with integer coefficients. The generator computes $C_n(q,t)$ with Sage's qt_catalan_number [5].

Before the values were written, the rows were checked against an independent enumeration of Dyck-path area sequences using the dinv and area statistics. The checks also verified (3), (2), and the small cases in (4) over the stored range.