

A121460


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


1



1, 1, 1, 2, 2, 1, 5, 4, 3, 1, 13, 9, 7, 4, 1, 34, 22, 16, 11, 5, 1, 89, 56, 38, 27, 16, 6, 1, 233, 145, 94, 65, 43, 22, 7, 1, 610, 378, 239, 159, 108, 65, 29, 8, 1, 1597, 988, 617, 398, 267, 173, 94, 37, 9, 1, 4181, 2585, 1605, 1015, 665, 440, 267, 131, 46, 10, 1, 10946, 6766
(list;
table;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

1,4


COMMENTS

Also the number of directed columnconvex polyominoes of area n, having k cells in the bottom row. Row sums are the oddsubscripted Fibonacci numbers (A001519). T(n,1)=fibonacci(2n3) for n>=2 (A001519). T(n,2)=1+fibonacci(2n4)=A055588(n2). T(n,3)=n3+fibonacci(2n5). Sum(k*T(n,k),k=1..n)=A061667(n1).


LINKS

Table of n, a(n) for n=1..68.
E. Barcucci, A. Del Lungo, S. Fezzi and R. Pinzani, Nondecreasing Dyck paths and qFibonacci numbers, Discrete Math., 170, 1997, 211217.
E. Barcucci, R. Pinzani and R. Sprugnoli, Directed columnconvex polyominoes by recurrence relations, Lecture Notes in Computer Science, No. 668, Springer, Berlin (1993), pp. 282298.
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) = binomial(n2,k2)+Sum(fibonacci(2j1)*binomial(n2j,k2), j=1..nk).
G.f.: G(t,z)=tz(12z)(1z)/[(13z+z^2)(1ztz)].


EXAMPLE

T(4,2)=4 because we have UUDDUUDD, UDUUUDDD, UUUDDDUD and UDUUDUDD, where U=(1,1) and D=(1,1) (the Dyck path UUDUDDUD does not qualify: it does have 2 returns to the xaxis but it is not nondecreasing since its valleys are at altitudes 1 and 0).
Triangle starts:
1;
1,1;
2,2,1;
5,4,3,1;
13,9,7,4,1;
34,22,16,11,5,1;


MAPLE

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


CROSSREFS

Cf. A001519, A055588, A061667.
Sequence in context: A127742 A110438 A184051 * A105292 A273342 A276067
Adjacent sequences: A121457 A121458 A121459 * A121461 A121462 A121463


KEYWORD

nonn,tabl


AUTHOR

Emeric Deutsch, Jul 31 2006


STATUS

approved



