OFFSET
0,7
COMMENTS
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.
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).
This triangle is A129182 (area under Dyck paths), reflected and compressed (0's removed). Equivalently, A239927 rotated by Pi/2 clockwise and compressed.
This is also the number of Catalan paths of length n and area k. - N. J. A. Sloane, Nov 28 2011
From Alford Arnold, Jan 29 2008:
This triangle gives the partial sums of the following triangle A136624:
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.
LINKS
Alois P. Heinz, Rows n = 0..40, flattened
Brian Drake, Limits of areas under lattice paths, Discrete Math. 309 (2009), no. 12, 3936-3953.
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 and
P[n+1] = Sum_{i=0..n} P[i] P[n-i] t^((i+1)*(n-i)).
EXAMPLE
T(4,5) = 3 because we have 01010011, 01001101 and 00110101.
Triangle starts:
[0] 1;
[1] 1;
[2] 1, 1;
[3] 1, 1, 2, 1;
[4] 1, 1, 2, 3, 3, 3, 1;
[5] 1, 1, 2, 3, 5, 5, 7, 7, 6, 4, 1;
[6] 1, 1, 2, 3, 5, 7, 9, 11, 14, 16, 16, 17, 14, 10, 5, 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
# 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, t)*z^t+b(x-1, y-1, t+1))))
end:
T:= n-> (p-> seq(coeff(p, z, i), i=0..degree(p)))(b(2*n, 0$2)):
seq(T(n), n=0..10); # Alois P. Heinz, Jun 10 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, t]*z^t + b[x-1, y-1, t+1]]]]; T[n_] := Function[{p}, Table[Coefficient[p, z, i], {i, 0, Exponent[p, z]}]][b[2*n, 0, 0]]; Table[T[n], {n, 0, 10}] // Flatten (* Jean-François Alcover, May 26 2015, after Alois P. Heinz *)
PROG
(SageMath)
from sage.combinat.q_analogues import qt_catalan_number
for n in (0..9): print(qt_catalan_number(n).substitute(q=1).coefficients())
# Peter Luschny, Mar 10 2020
(PARI)
P(x, n) =
{
if ( n<=1, return(1) );
return( sum( i=0, n-1, P(x, i) * P(x, n-1 -i) * x^((i+1)*(n-1 -i)) ) );
}
for (n=0, 10, print( Vecrev( P(x, n) ) ) ); \\ Joerg Arndt, Jan 23 2024
(PARI) \\ faster with memoization:
N=11;
VP=vector(N+1); VP[1] =VP[2] = 1; \\ one-based; memoization
P(n) = VP[n+1];
for (n=2, N, VP[n+1] = sum( i=0, n-1, P(i) * P(n-1 -i) * x^((i+1)*(n-1-i)) ) );
for (n=0, N, print( Vecrev( P(n) ) ) ); \\ Joerg Arndt, Jan 23 2024
CROSSREFS
KEYWORD
AUTHOR
Emeric Deutsch, Apr 11 2007
STATUS
approved