|
Search: id:A129176
|
|
|
| A129176 |
|
Triangle read by rows: T(n,k) is the number of Dyck words of length 2n having k inversions (n>=0, k>=0). A Catalan 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. |
|
+0
2
|
|
| 1, 1, 1, 1, 1, 2, 1, 1, 1, 2, 3, 3, 3, 1, 1, 1, 2, 3, 5, 5, 7, 7, 6, 4, 1, 1, 1, 2, 3, 5, 7, 9, 11, 14, 16, 16, 17, 14, 10, 5, 1, 1, 1, 2, 3, 5, 7, 11, 13, 18, 22, 28, 32, 37, 40, 44, 43, 40, 35, 25, 15, 6, 1, 1, 1, 2, 3, 5, 7, 11, 15, 20, 26, 34, 42, 53, 63, 73, 85, 96, 106, 113, 118, 118
(list; graph; listen)
|
|
|
OFFSET
|
0,6
|
|
|
COMMENT
|
Representing a Dyck word p of length 2n as a superdiagonal Dyck path p', the number of inversions of p is equal to the area between p' and the path that corresponds to the Dyck word 0^n 1^n. Row n has 1+n(n-1)/2 terms. Row sums are the Catalan numbers (A000108). Alternating row sums for n>=1 are the Catalan numbers alternated with 0's (A097331). Sum(k*T(n,k),k>=0)=A029760(n-2). A modified form of A129182 (area under Dyck paths).
Comment from Alford Arnold, Jan 29 2008: This triangle gives the partial sums of the following triangle:
1
.1
....2...1
........2...3...3...1
............2...2...6...7...6...4...1
................2...2...4...8..12..15..17..14..10...5...1
etc.
|
|
REFERENCES
|
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 row generating polynomials P[n]=P[n](t) satisfy P[0]=1, P[n+1]=Sum(t^((i+1)(n-i))P[i]P[n-i],i=0..n).
|
|
EXAMPLE
|
T(4,5)=3 because we have 01010011, 01001101 and 00110101.
Triangle starts:
1;
1;
1,1;
1,1,2,1;
1,1,2,3,3,3,1;
1,1,2,3,5,5,7,7,6,4,1;
|
|
MAPLE
|
P[0]:=1: for n from 0 to 8 do P[n+1]:=sort(expand(sum(t^((i+1)*(n-i))*P[i]*P[n-i], i=0..n))) od: for n from 1 to 9 do seq(coeff(P[n], t, j), j=0..n*(n-1)/2) od; # yields sequence in triangular form
|
|
CROSSREFS
|
Cf. A000108, A097331, A029760, A129182.
Cf. A136624 A136625.
Sequence in context: A156070 A114731 A035389 this_sequence A134132 A030424 A145515
Adjacent sequences: A129173 A129174 A129175 this_sequence A129177 A129178 A129179
|
|
KEYWORD
|
nonn,tabf
|
|
AUTHOR
|
Emeric Deutsch (deutsch(AT)duke.poly.edu), Apr 11 2007
|
|
|
Search completed in 0.002 seconds
|
