|
Search: id:A129175
|
|
|
| A129175 |
|
Triangle read by rows: 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. |
|
+0
3
|
|
| 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
(list; graph; listen)
|
|
|
OFFSET
|
0,17
|
|
|
COMMENT
|
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 binom(n,floor(n/2))=A001405(n). Sum(k*T(n,k),k=0..n(n-1))=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).
|
|
REFERENCES
|
G. E. Andrews, The Theory of Partitions, Addison-Wesley, 1976.
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.
|
|
FORMULA
|
The generating polynomial for row n is P[n](t) = binom[2n,n]/[n+1], where [n+1]=1+t+t^2+...+t^n and binom[2n,n] is a Gaussian polynomial.
|
|
EXAMPLE
|
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;
|
|
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
|
|
CROSSREFS
|
Cf. A000108, A001405, A002740, A129174.
Adjacent sequences: A129172 A129173 A129174 this_sequence A129176 A129177 A129178
Sequence in context: A047885 A072731 A129174 this_sequence A063053 A063050 A057557
|
|
KEYWORD
|
nonn,tabf
|
|
AUTHOR
|
Emeric Deutsch (deutsch(AT)duke.poly.edu), Apr 20 2007
|
|
|
Search completed in 0.002 seconds
|
