A129175 Triangle read by rows: MacMahon's q-analog of the Catalan numbers.

1, 1, 1, 0, 1, 1, 0, 1, 1, 1, 0, 1, 1, 0, 1, 1, 2, 1, 2, 1, 2, 1, 1, 0, 1, 1, 0, 1, 1, 2, 2, 3, 2, 4, 3, 4, 3, 4, 2, 3, 2, 2, 1, 1, 0, 1, 1, 0, 1, 1, 2, 2, 4, 3, 5, 5, 7, 6, 9, 7, 9, 8, 9, 7, 9, 6, 7, 5, 5, 3, 4, 2, 2, 1, 1, 0, 1, 1, 0, 1, 1, 2, 2, 4, 4, 6, 6, 9, 9, 13, 12, 16, 16, 19, 18, 22, 20, 23, 21, 23

Offset: 0

Author

Emeric Deutsch, Apr 20 2007

Keywords

• nonn
• tabf

Comments

Previous name: T(n,k) is the number of Dyck words of length 2n having major index k (n >= 0, k >= 0). A Dyck word of length 2n is a word of n 0's and n 1's for which no initial segment contains more 1's than 0's. The major index of a Dyck word is the sum of the positions of those 1's that are followed by a 0.

Representing a Dyck word p of length 2n as a Dyck path p', the major index of p is equal to the sum of the abscissae of the valleys of p'.

Row n has 1+n*(n-1) terms.

Row sums are the Catalan numbers (A000108).

T(n,k) = T(n,n^2-n-k) (i.e., rows are palindromic).

Alternating row sums are the central binomial coefficients binomial(n, floor(n/2)) = A001405(n).

Sum_{k=0..n*(n-1)} k*T(n,k) = A002740(n+1).

T(n,k) = A129174(n,n+k) (i.e., except for the initial 0's, rows of A129174 and A129175 are the same).

For another q-analog of the Catalan numbers, due to Carlitz and Riordan, that enumerates Dyck paths by an area statistic see A227543. - Peter Bala, Feb 28 2023

Examples

			T(4,8)=2 because we have 01001101 (with 10's starting at positions 2 and 6) and 00101011 (with 10's starting at positions 3 and 5).
Triangle starts:
  1;
  1;
  1,0,1;
  1,0,1,1,1,0,1;
  1,0,1,1,2,1,2,1,2,1,1,0,1;
  1,0,1,1,2,2,3,2,4,3,4,3,4,2,3,2,2,1,1,0,1;
		

References

• G. E. Andrews, The Theory of Partitions, Addison-Wesley, 1976.
• P. A. MacMahon, Combinatory analysis, Two volumes (bound as one), Chelsea Publishing Co., New York, 1960 (see p. 214).
• R. P. Stanley, Enumerative Combinatorics, Cambridge, Vol. 2, 1999; see p. 236, Exercise 6.34 b. [From Emeric Deutsch, Nov 05 2008]

Links

• Alois P. Heinz, Rows n = 0..32, flattened
• FindStat - Combinatorial Statistic Finder, The major index of a Dyck path.
• J. Furlinger and J. Hofbauer, q-Catalan numbers, J. Comb. Theory, A, 40, 248-264, 1985.
• M. Shattuck, Parity theorems for statistics on permutations and Catalan words, INTEGERS, Electronic J. of Combinatorial Number Theory, Vol. 5, Paper A07, 2005.

Crossrefs

Cf. A000108, A001405, A002740, A129174, A227543.

Programs

Maple

br:=n->sum(q^i,i=0..n-1): f:=n->product(br(j),j=1..n): cbr:=(n,k)->f(n)/f(k)/f(n-k): P:=n->sort(expand(simplify(cbr(2*n,n)/br(n+1)))): for n from 0 to 7 do seq(coeff(P(n),q,k),k=0..n*(n-1)) od; # yields sequence in triangular form
# second Maple program:
b:= proc(x, y, t) option remember; `if`(y<0 or y>x, 0, `if`(x=0, 1,
      expand(b(x-1, y-1, true)+b(x-1, y+1, false)*`if`(t, z^x, 1))))
    end:
T:= n-> (p-> seq(coeff(p, z, i), i=0..degree(p)))(b(2*n, 0, false)):
seq(T(n), n=0..8);  # Alois P. Heinz, Sep 15 2014

Mathematica

b[x_, y_, t_] := b[x, y, t] = If[y<0 || y>x, 0, If[x == 0, 1, Expand[b[x-1, y-1, True] + b[x-1, y+1, False]*If[t, z^x, 1]]]]; T[n_] := Function[{p}, Table[ Coefficient[p, z, i], {i, 0, Exponent[p, z]}]][b[2*n, 0, False]]; Table[T[n], {n, 0, 8}] // Flatten (* Jean-François Alcover, May 26 2015, after Alois P. Heinz *)
p[n_] := QBinomial[2n,n,q]/QBinomial[n+1,1,q]; Table[CoefficientList[p[n] // FunctionExpand, q], {n,0,9}] // Flatten (* Peter Luschny, Jul 22 2016 *)

Sage

from sage.combinat.q_analogues import q_catalan_number
def T(n): return list(q_catalan_number(n))
for n in (0..6): print(T(n)) # Peter Luschny, Jul 19 2016

Formula

The generating polynomial for row n is P[n](t) = binomial[2n,n]/[n+1], where [n+1]=1+t+t^2+...+t^n and binomial[2n,n] is a Gaussian polynomial (due to MacMahon).

Extensions

New name from Peter Luschny, Jul 24 2016