A121464 Triangle read by rows: T(n,k) is the number of nondecreasing Dyck paths of semilength n, having k triangles (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.

0, 1, 0, 1, 1, 1, 1, 2, 1, 4, 2, 3, 3, 1, 12, 6, 5, 6, 4, 1, 33, 18, 11, 11, 10, 5, 1, 88, 51, 29, 22, 21, 15, 6, 1, 232, 139, 80, 51, 43, 36, 21, 7, 1, 609, 371, 219, 131, 94, 79, 57, 28, 8, 1, 1596, 980, 590, 350, 225, 173, 136, 85, 36, 9, 1, 4180, 2576, 1570, 940, 575, 398

Offset

0,8

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)=A001906(n).

Links

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

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,k)=binomial(n,k)+Sum(binomial(n-j,k)*fibonacci(2j-4), j=1..n-k). G.f.=G=G(t,z)=(1-2z)^2/[(1-3z+z^2)(1-z-tz)].

Example

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

Maple

with(combinat): T:=(n, k)->binomial(n, k)+add(binomial(n-j, k)*fibonacci(2*j-4), j=1..n-k): for n from 0 to 12 do seq(T(n, k), k=0..n) od; # yields sequence in triangular form

Crossrefs

Cf. A001519, A027941, A001906.

Sequence in context: A363301 A135941 A036998 * A090278 A256143 A352791

Adjacent sequences: A121461 A121462 A121463 * A121465 A121466 A121467

Keyword

nonn,tabl

Author

Emeric Deutsch, Aug 01 2006

Status

approved