

A121462


Triangle read by rows: T(n,k) is the number of nondecreasing Dyck paths of semilength n, having pyramid weight k (1<=k<=n).


5



1, 0, 2, 0, 1, 4, 0, 1, 4, 8, 0, 1, 5, 12, 16, 0, 1, 6, 18, 32, 32, 0, 1, 7, 25, 56, 80, 64, 0, 1, 8, 33, 88, 160, 192, 128, 0, 1, 9, 42, 129, 280, 432, 448, 256, 0, 1, 10, 52, 180, 450, 832, 1120, 1024, 512, 0, 1, 11, 63, 242, 681, 1452, 2352, 2816, 2304, 1024, 0, 1, 12, 75, 316
(list;
table;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

1,3


COMMENTS

A pyramid in a Dyck word (path) is a factor of the form U^h D^h, where U=(1,1), D=(1,1) and h is the height of the pyramid. A pyramid in a Dyck word w is maximal if, as a factor in w, it is not immediately preceded by a u and immediately followed by a d. The pyramid weight of a Dyck path (word) is the sum of the heights of its maximal pyramids.
Row sums are the oddsubscripted Fibonacci numbers (A001519). T(n,n)=2^(n1). Sum(k*T(n,k),k=1..n)=A030267(n)
Mirror image of triangle in A153342 . [From Philippe Deléham, Dec 31 2008]
Essentially triangle given by (0,1/2,1/2,0,0,0,0,0,0,0,...) DELTA (2,0,0,0,0,0,0,0,0,0,...) where DELTA is the operator defined in A084938.  Philippe Deléham, Oct 30 2011
A121462 is jointly generated with A208341 as an array of coefficients of polynomials u(n,x): initially, u(1,x)=v(1,x)=1; for n>1, u(n,x)=x*u(n1,x)+x*v(n1) and v(n,x)=x*u(n1,x)+(x+1)*v(n1,x). See the Mathematica section. [Clark Kimberling, Mar 11 2012]


LINKS

Table of n, a(n) for n=1..71.
E. Barcucci, A. Del Lungo, S. Fezzi and R. Pinzani, Nondecreasing Dyck paths and qFibonacci numbers, Discrete Math., 170, 1997, 211217.
A. Denise and R. Simion, Two combinatorial statistics on Dyck paths, Discrete Math., 137, 1995, 155176.
E. Deutsch and H. Prodinger, A bijection between directed columnconvex polyominoes and ordered trees of height at most three, Theoretical Comp. Science, 307, 2003, 319325.


FORMULA

T(n,k) = Sum(binomial(k1,j)*binomial(nk1+j,j1), j=0..k1) for 2<=k<=n; T(1,1)=1; T(n,1)=0 for n>=2.
G.f.=G=G(t,z)=tz(1z)/(12tzz+tz^2).
T(n+1,k+1) = A062110(n,k)*2^(2*kn) .  Philippe Deléham, Aug 01 2006


EXAMPLE

T(4,3)=4 because we have (UD)U(UD)(UD)D, U(UD)(UD)(UD)D, U(UD)(UUDD)D and U(UUDD)(UD)D, where U=(1,1) and D=(1,1) (the maximal pyramids are shown between parentheses).
Triangle starts:
1;
0,2;
0,1,4;
0,1,4,8;
0,1,5,12,16;
0,1,6,18,32,32;


MAPLE

T:=proc(n, k) if n=1 and k=1 then 1 elif k=1 then 0 elif k<=n then sum(binomial(k1, j)*binomial(nk1+j, j1), j=0..k1) else 0 fi end: for n from 1 to 13 do seq(T(n, k), k=1..n) od; # yields sequence in triangular form


MATHEMATICA

u[1, x_] := 1; v[1, x_] := 1; z = 16;
u[n_, x_] := x*u[n  1, x] + x*v[n  1, x];
v[n_, x_] := x*u[n  1, x] + (x + 1) v[n  1, x];
Table[Expand[u[n, x]], {n, 1, z/2}]
Table[Expand[v[n, x]], {n, 1, z/2}]
cu = Table[CoefficientList[u[n, x], x], {n, 1, z}];
TableForm[cu]
Flatten[%] (* A121462 *)
Table[Expand[v[n, x]], {n, 1, z}]
cv = Table[CoefficientList[v[n, x], x], {n, 1, z}];
TableForm[cv]
Flatten[%] (* A208341 *)
(* Clark Kimberling, Mar 11 2012 *)


CROSSREFS

Cf. A001519, A030267, A091866.
Sequence in context: A247489 A208756 A259873 * A271466 A218581 A307177
Adjacent sequences: A121459 A121460 A121461 * A121463 A121464 A121465


KEYWORD

nonn,tabl


AUTHOR

Emeric Deutsch, Jul 31 2006


STATUS

approved



