A121465 Triangle read by rows: T(n,k) is the number of nondecreasing Dyck paths of semilength n such that the sum of the heights of their triangles is k (0<=k<=n). A triangle in a Dyck path is a subpath of the form U^h D^h, starting at the x-axis; here U=(1,1), D=(1,-1), h being the height of the triangle.

1, 0, 1, 0, 0, 2, 1, 0, 0, 4, 4, 1, 0, 0, 8, 12, 4, 2, 0, 0, 16, 33, 12, 8, 4, 0, 0, 32, 88, 33, 24, 16, 8, 0, 0, 64, 232, 88, 66, 48, 32, 16, 0, 0, 128, 609, 232, 176, 132, 96, 64, 32, 0, 0, 256, 1596, 609, 464, 352, 264, 192, 128, 64, 0, 0, 512, 4180, 1596, 1218, 928, 704, 528

Offset

0,6

Comments

Row sums are the odd-subscripted Fibonacci numbers (A001519). T(n,0)=fibonacci(2n-3)-1=A027941(n-2). Sum(k*T(n,k),k=0..n)=fibonacci(2n+1)-1=A027941(n).

Links

Table of n, a(n) for n=0..71.

E. Barcucci, A. Del Lungo, S. Fezzi and R. Pinzani, Nondecreasing Dyck paths and q-Fibonacci numbers, Discrete Math., 170, 1997, 211-217.

Formula

T(n,0)=fibonacci(2*n-3)-1; T(n,k)=2^(k-1)*(fibonacci(2n-2k-3)-1) for 1<=k<=n. G.f.=G=G(t,z)=(1-2z)^2*(1-tz)/[(1-3z+z^2)(1-z)(1-2tz)].

Example

T(5,2)=2 because we have (UD)(UD)UUDUDD and (UUDD)UUDUDD, where U=(1,1) and D=(1,-1) (the triangles are shown between parentheses).
Triangle starts:
1;
0,1;
0,0,2;
1,0,0,4;
4,1,0,0,8;
12,4,2,0,0,16;

Maple

with(combinat): T:=proc(n, k) if k=0 then fibonacci(2*n-3)-1 elif k<=n then 2^(k-1)*(fibonacci(2*n-2*k-3)-1) else 0 fi end: for n from 0 to 12 do seq(T(n, k), k=0..n) od; # yields sequence in triangular form

Crossrefs

Cf. A001519, A027941.

Sequence in context: A317554 A089975 A034366 * A192396 A094449 A274776

Adjacent sequences: A121462 A121463 A121464 * A121466 A121467 A121468

Keyword

nonn,tabl

Author

Emeric Deutsch, Aug 01 2006

Status

approved