back to table · edit · history · where entries came from · files
-Title: $q,t$-Catalan numbers $C_n(q,t)$, with the Carlitz and MacMahon $q$-Catalan- numbers+Title: $q,t$-Catalan numbers $C_n(q,t)$ Definition: The $q,t$-Catalan polynomial $C_n(q,t)$ CITE{GarsiaHaiman} is the Dyck-path generating function in CITE{formula-dinv}, using the area-sequence convention in- CITE{statistics}. The table also records the Carlitz-Riordan form $C_n(q)=C_n(q,1)$- and the MacMahon form $\widetilde C_n(q)=q^{\binom n2}C_n(q,q^{-1})$.+ CITE{statistics}. Keywords:-- q-Catalan numbers-- Carlitz-Riordan q-Catalan numbers-- MacMahon q-Catalan numbers+- q,t-Catalan numbers+- qt-Catalan numbers - Dyck paths - area statistic
display: $n$ constraints: a nonnegative integer- specialisation:- type: Symbolic- title: $q$-Catalan convention- display: convention- constraints: one of the three labelled forms- values:- qt: $C_n(q,t)$- carlitz: Carlitz-Riordan $C_n(q)$- macmahon: MacMahon $\widetilde C_n(q)$ Display properties:- number-header: Catalan polynomial+ number-header: $C_n(q,t)$ Comments: statistics: 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\}$.- conventions: Rows labelled $C_n(q,t)$ use variables $q$ and $t$. Rows labelled Carlitz-Riordan- $C_n(q)$ store $C_n(q,1)$; by CITE{formula-symmetry}, this is also the area generating- function of Dyck paths. Rows labelled MacMahon $\widetilde C_n(q)$ store $q^{\binom- n2}C_n(q,q^{-1})$, the Gaussian binomial quotient in CITE{formula-macmahon}. The- two one-variable forms are both called $q$-Catalan numbers, so the convention- column distinguishes them. Formulas: formula-dinv: $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$ CITE{Haglund}.- formula-carlitz: The Carlitz-Riordan specialisation is $C_n(q,1)$.- formula-macmahon: The MacMahon specialisation is $q^{\binom n2}C_n(q,q^{-1})=\frac{1}{[n+1]_q}{2n\brack- n}_q$. formula-catalan: $C_n(1,1)=\frac{1}{n+1}\binom{2n}{n}$. formula-symmetry: $C_n(q,t)=C_n(t,q)$.- formula-small: $C_0(q,t)=C_1(q,t)=1$ and $C_2(q,t)=q+t$; the corresponding Carlitz-Riordan- rows are $1,1,q+1$, and the corresponding MacMahon rows are $1,1,q^2+1$.+ formula-small: $C_0(q,t)=C_1(q,t)=1$ and $C_2(q,t)=q+t$.+Similar tables:+- table: HREF{T264}[Carlitz-Riordan $q$-Catalan numbers]+ relation: 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.+- table: HREF{T265}[MacMahon $q$-Catalan numbers]+ relation: 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. Links: SageCatalan:
bib: A. M. Garsia and M. Haiman, A remarkable q,t-Catalan sequence and q-Lagrange inversion, J. Algebraic Combin. 5 (1996), 191-244.+ CarlitzRiordan:+ bib: L. Carlitz and J. Riordan, Two element lattice permutation numbers and their+ q-generalization, Duke Math. J. 31 (1964), 371-388.+ MacMahon:+ bib: P. A. MacMahon, Combinatory Analysis, Vol. II, Cambridge University Press,+ Cambridge, 1916. Programs: program-sage: language: Sage- code: 'from sage.combinat.q_analogues import qt_catalan_number, q_catalan_number+ code: 'from sage.combinat.q_analogues import qt_catalan_number - qt_catalan_number(7) # C_7(q,t)-- qt_catalan_number(12).subs(t=1) # Carlitz-Riordan C_12(q)-- q_catalan_number(12) # MacMahon q-Catalan polynomial'+ qt_catalan_number(7)' Data properties: type: Z[] rigour: exact complete: 'no'- complete-note: it holds the two-variable rows for $3\leq n\leq6$ and the Carlitz-Riordan- and MacMahon rows for $3\leq n\leq11$; the omitted rows with $n\leq2$ are the- closed forms in CITE{formula-small}+ complete-note: it holds the rows for $3\leq n\leq6$; the omitted rows with $n\leq2$+ are the closed forms in CITE{formula-small} rigour details: 'Every entry is an exact polynomial with integer coefficients. The- generator computes $C_n(q,t)$ with Sage''s `qt_catalan_number` CITE{SageCatalan};- the one-variable rows are exact specialisations of those polynomials.+ generator computes $C_n(q,t)$ with Sage''s `qt_catalan_number` CITE{SageCatalan}. - Before the values were written, the two-variable rows were checked against an- independent enumeration of Dyck-path area sequences using the dinv and area statistics.- The Carlitz-Riordan rows were checked against the area distribution of the same- paths, and the MacMahon rows were checked against the Gaussian binomial quotient- in CITE{formula-macmahon}. The checks also verified CITE{formula-symmetry}, CITE{formula-catalan},- and the small cases in CITE{formula-small} over the stored range.'+ 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 CITE{formula-symmetry}, CITE{formula-catalan}, and the small cases in+ CITE{formula-small} over the stored range.' Numbers:- '3':- qt: q^3 + q^2*t + q*t^2 + t^3 + q*t- carlitz: q^3 + q^2 + 2*q + 1- macmahon: q^6 + q^4 + q^3 + q^2 + 1- '4':- qt: 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- carlitz: q^6 + q^5 + 2*q^4 + 3*q^3 + 3*q^2 + 3*q + 1- macmahon: q^12 + q^10 + q^9 + 2*q^8 + q^7 + 2*q^6 + q^5 + 2*q^4 + q^3 + q^2 +- 1- '5':- qt: 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- carlitz: 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- macmahon: q^20 + q^18 + q^17 + 2*q^16 + 2*q^15 + 3*q^14 + 2*q^13 + 4*q^12 + 3*q^11- + 4*q^10 + 3*q^9 + 4*q^8 + 2*q^7 + 3*q^6 + 2*q^5 + 2*q^4 + q^3 + q^2 + 1- '6':- qt: 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- carlitz: 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- macmahon: q^30 + q^28 + q^27 + 2*q^26 + 2*q^25 + 4*q^24 + 3*q^23 + 5*q^22 + 5*q^21- + 7*q^20 + 6*q^19 + 9*q^18 + 7*q^17 + 9*q^16 + 8*q^15 + 9*q^14 + 7*q^13 + 9*q^12- + 6*q^11 + 7*q^10 + 5*q^9 + 5*q^8 + 3*q^7 + 4*q^6 + 2*q^5 + 2*q^4 + q^3 + q^2- + 1- '7':- carlitz: 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- macmahon: q^42 + q^40 + q^39 + 2*q^38 + 2*q^37 + 4*q^36 + 4*q^35 + 6*q^34 + 6*q^33- + 9*q^32 + 9*q^31 + 13*q^30 + 12*q^29 + 16*q^28 + 16*q^27 + 19*q^26 + 18*q^25- + 22*q^24 + 20*q^23 + 23*q^22 + 21*q^21 + 23*q^20 + 20*q^19 + 22*q^18 + 18*q^17- + 19*q^16 + 16*q^15 + 16*q^14 + 12*q^13 + 13*q^12 + 9*q^11 + 9*q^10 + 6*q^9- + 6*q^8 + 4*q^7 + 4*q^6 + 2*q^5 + 2*q^4 + q^3 + q^2 + 1- '8':- carlitz: 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- macmahon: q^56 + q^54 + q^53 + 2*q^52 + 2*q^51 + 4*q^50 + 4*q^49 + 7*q^48 + 7*q^47- + 10*q^46 + 11*q^45 + 16*q^44 + 16*q^43 + 22*q^42 + 23*q^41 + 29*q^40 + 30*q^39- + 37*q^38 + 37*q^37 + 45*q^36 + 45*q^35 + 51*q^34 + 51*q^33 + 58*q^32 + 55*q^31- + 61*q^30 + 58*q^29 + 62*q^28 + 58*q^27 + 61*q^26 + 55*q^25 + 58*q^24 + 51*q^23- + 51*q^22 + 45*q^21 + 45*q^20 + 37*q^19 + 37*q^18 + 30*q^17 + 29*q^16 + 23*q^15- + 22*q^14 + 16*q^13 + 16*q^12 + 11*q^11 + 10*q^10 + 7*q^9 + 7*q^8 + 4*q^7 +- 4*q^6 + 2*q^5 + 2*q^4 + q^3 + q^2 + 1- '9':- carlitz: 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- macmahon: q^72 + q^70 + q^69 + 2*q^68 + 2*q^67 + 4*q^66 + 4*q^65 + 7*q^64 + 8*q^63- + 11*q^62 + 12*q^61 + 18*q^60 + 19*q^59 + 26*q^58 + 29*q^57 + 37*q^56 + 40*q^55- + 51*q^54 + 54*q^53 + 66*q^52 + 71*q^51 + 83*q^50 + 88*q^49 + 103*q^48 + 106*q^47- + 120*q^46 + 125*q^45 + 138*q^44 + 140*q^43 + 154*q^42 + 153*q^41 + 165*q^40- + 164*q^39 + 172*q^38 + 168*q^37 + 176*q^36 + 168*q^35 + 172*q^34 + 164*q^33- + 165*q^32 + 153*q^31 + 154*q^30 + 140*q^29 + 138*q^28 + 125*q^27 + 120*q^26- + 106*q^25 + 103*q^24 + 88*q^23 + 83*q^22 + 71*q^21 + 66*q^20 + 54*q^19 + 51*q^18- + 40*q^17 + 37*q^16 + 29*q^15 + 26*q^14 + 19*q^13 + 18*q^12 + 12*q^11 + 11*q^10- + 8*q^9 + 7*q^8 + 4*q^7 + 4*q^6 + 2*q^5 + 2*q^4 + q^3 + q^2 + 1- '10':- carlitz: 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- macmahon: q^90 + q^88 + q^87 + 2*q^86 + 2*q^85 + 4*q^84 + 4*q^83 + 7*q^82 + 8*q^81- + 12*q^80 + 13*q^79 + 19*q^78 + 21*q^77 + 29*q^76 + 33*q^75 + 43*q^74 + 48*q^73- + 62*q^72 + 68*q^71 + 85*q^70 + 94*q^69 + 113*q^68 + 124*q^67 + 148*q^66 + 160*q^65- + 186*q^64 + 201*q^63 + 229*q^62 + 244*q^61 + 276*q^60 + 290*q^59 + 322*q^58- + 337*q^57 + 368*q^56 + 381*q^55 + 412*q^54 + 421*q^53 + 449*q^52 + 456*q^51- + 480*q^50 + 481*q^49 + 502*q^48 + 497*q^47 + 512*q^46 + 504*q^45 + 512*q^44- + 497*q^43 + 502*q^42 + 481*q^41 + 480*q^40 + 456*q^39 + 449*q^38 + 421*q^37- + 412*q^36 + 381*q^35 + 368*q^34 + 337*q^33 + 322*q^32 + 290*q^31 + 276*q^30- + 244*q^29 + 229*q^28 + 201*q^27 + 186*q^26 + 160*q^25 + 148*q^24 + 124*q^23- + 113*q^22 + 94*q^21 + 85*q^20 + 68*q^19 + 62*q^18 + 48*q^17 + 43*q^16 + 33*q^15- + 29*q^14 + 21*q^13 + 19*q^12 + 13*q^11 + 12*q^10 + 8*q^9 + 7*q^8 + 4*q^7 +- 4*q^6 + 2*q^5 + 2*q^4 + q^3 + q^2 + 1- '11':- carlitz: 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- macmahon: q^110 + q^108 + q^107 + 2*q^106 + 2*q^105 + 4*q^104 + 4*q^103 + 7*q^102- + 8*q^101 + 12*q^100 + 14*q^99 + 20*q^98 + 22*q^97 + 31*q^96 + 36*q^95 + 47*q^94- + 54*q^93 + 70*q^92 + 79*q^91 + 100*q^90 + 113*q^89 + 138*q^88 + 156*q^87 +- 188*q^86 + 209*q^85 + 248*q^84 + 276*q^83 + 320*q^82 + 353*q^81 + 406*q^80 +- 442*q^79 + 502*q^78 + 544*q^77 + 608*q^76 + 655*q^75 + 725*q^74 + 771*q^73 +- 846*q^72 + 895*q^71 + 969*q^70 + 1017*q^69 + 1092*q^68 + 1135*q^67 + 1208*q^66- + 1247*q^65 + 1312*q^64 + 1345*q^63 + 1404*q^62 + 1424*q^61 + 1476*q^60 + 1487*q^59- + 1524*q^58 + 1524*q^57 + 1551*q^56 + 1536*q^55 + 1551*q^54 + 1524*q^53 + 1524*q^52- + 1487*q^51 + 1476*q^50 + 1424*q^49 + 1404*q^48 + 1345*q^47 + 1312*q^46 + 1247*q^45- + 1208*q^44 + 1135*q^43 + 1092*q^42 + 1017*q^41 + 969*q^40 + 895*q^39 + 846*q^38- + 771*q^37 + 725*q^36 + 655*q^35 + 608*q^34 + 544*q^33 + 502*q^32 + 442*q^31- + 406*q^30 + 353*q^29 + 320*q^28 + 276*q^27 + 248*q^26 + 209*q^25 + 188*q^24- + 156*q^23 + 138*q^22 + 113*q^21 + 100*q^20 + 79*q^19 + 70*q^18 + 54*q^17 +- 47*q^16 + 36*q^15 + 31*q^14 + 22*q^13 + 20*q^12 + 14*q^11 + 12*q^10 + 8*q^9- + 7*q^8 + 4*q^7 + 4*q^6 + 2*q^5 + 2*q^4 + q^3 + q^2 + 1+- params:+ n: '3'+ number: q^3 + q^2*t + q*t^2 + t^3 + q*t+- params:+ n: '4'+ number: 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+- params:+ n: '5'+ number: 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+- params:+ n: '6'+ number: 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
Sign in to restore an earlier version.