Carlitz-Riordan $q$-Catalan numbers $C_n(q)$

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

Polynomials

$n$

$C_n(q)$

q^3 + q^2 + 2*q + 1

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

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

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

q^21 + q^20 + 2*q^19 + 3*q^18 + 5*q^17 + 7*q^16 + 11*q^15 + 13*q^14 + 18*q^13 + 22*q^12 + 28*q^11 + 32*q^10 + 37*q^9 + 40*q^8 + 44*q^7 + 43*q^6 + 40*q^5 + 35*q^4 + 25*q^3 + 15*q^2 + 6*q + 1

q^28 + q^27 + 2*q^26 + 3*q^25 + 5*q^24 + 7*q^23 + 11*q^22 + 15*q^21 + 20*q^20 + 26*q^19 + 34*q^18 + 42*q^17 + 53*q^16 + 63*q^15 + 73*q^14 + 85*q^13 + 96*q^12 + 106*q^11 + 113*q^10 + 118*q^9 + 118*q^8 + 115*q^7 + 102*q^6 + 86*q^5 + 65*q^4 + 41*q^3 + 21*q^2 + 7*q + 1

q^36 + q^35 + 2*q^34 + 3*q^33 + 5*q^32 + 7*q^31 + 11*q^30 + 15*q^29 + 22*q^28 + 28*q^27 + 38*q^26 + 48*q^25 + 63*q^24 + 77*q^23 + 97*q^22 + 116*q^21 + 139*q^20 + 162*q^19 + 190*q^18 + 215*q^17 + 245*q^16 + 268*q^15 + 293*q^14 + 314*q^13 + 331*q^12 + 338*q^11 + 338*q^10 + 326*q^9 + 303*q^8 + 268*q^7 + 219*q^6 + 167*q^5 + 112*q^4 + 63*q^3 + 28*q^2 + 8*q + 1

10:

q^45 + q^44 + 2*q^43 + 3*q^42 + 5*q^41 + 7*q^40 + 11*q^39 + 15*q^38 + 22*q^37 + 30*q^36 + 40*q^35 + 52*q^34 + 69*q^33 + 87*q^32 + 111*q^31 + 138*q^30 + 171*q^29 + 207*q^28 + 249*q^27 + 295*q^26 + 348*q^25 + 405*q^24 + 466*q^23 + 531*q^22 + 598*q^21 + 665*q^20 + 734*q^19 + 801*q^18 + 862*q^17 + 918*q^16 + 958*q^15 + 990*q^14 + 1003*q^13 + 995*q^12 + 959*q^11 + 901*q^10 + 813*q^9 + 704*q^8 + 574*q^7 + 434*q^6 + 301*q^5 + 182*q^4 + 92*q^3 + 36*q^2 + 9*q + 1

11:

q^55 + q^54 + 2*q^53 + 3*q^52 + 5*q^51 + 7*q^50 + 11*q^49 + 15*q^48 + 22*q^47 + 30*q^46 + 42*q^45 + 54*q^44 + 73*q^43 + 93*q^42 + 121*q^41 + 152*q^40 + 193*q^39 + 237*q^38 + 295*q^37 + 356*q^36 + 431*q^35 + 513*q^34 + 611*q^33 + 714*q^32 + 837*q^31 + 964*q^30 + 1109*q^29 + 1257*q^28 + 1422*q^27 + 1588*q^26 + 1770*q^25 + 1947*q^24 + 2131*q^23 + 2307*q^22 + 2481*q^21 + 2636*q^20 + 2784*q^19 + 2900*q^18 + 2990*q^17 + 3037*q^16 + 3039*q^15 + 2992*q^14 + 2887*q^13 + 2717*q^12 + 2486*q^11 + 2203*q^10 + 1871*q^9 + 1515*q^8 + 1149*q^7 + 806*q^6 + 512*q^5 + 282*q^4 + 129*q^3 + 45*q^2 + 10*q + 1

Definition

The Carlitz-Riordan $q$-Catalan polynomial $C_n(q)$ [3] is $C_n(q,t)$ at $t=1$. Equivalently, it is the area generating function of Dyck paths of semilength $n$ in the convention of (4).

Parameters

$n$

— semilength (a nonnegative integer)

Formulas

(1)

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

(2)

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

(3)

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

Comments

(4)

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(12).subs(t=1)

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

$q,t$-Catalan numbers — stores the two-variable polynomial whose $t=1$ specialisation is this table. This table is the likely target for a reader holding the one-variable area or dinv distribution; a reader holding the full dinv-area polynomial wants T262.

MacMahon $q$-Catalan numbers — stores the other standard one-variable $q$-Catalan polynomial, $q^{\binom n2}C_n(q,q^{-1})$, while this table stores $C_n(q,1)$. Neither one-variable table determines the full $C_n(q,t)$.

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\leq11$; the omitted rows with $n\leq2$ are the closed forms in (3))

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] and then specialises at $t=1$.

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 (2) and the small cases in (3) over the stored range.