

A121461


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


2



1, 1, 1, 3, 1, 1, 8, 3, 1, 1, 21, 8, 3, 1, 1, 55, 21, 8, 3, 1, 1, 144, 55, 21, 8, 3, 1, 1, 377, 144, 55, 21, 8, 3, 1, 1, 987, 377, 144, 55, 21, 8, 3, 1, 1, 2584, 987, 377, 144, 55, 21, 8, 3, 1, 1, 6765, 2584, 987, 377, 144, 55, 21, 8, 3, 1, 1, 17711, 6765, 2584, 987, 377, 144, 55, 21
(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 last column. Row sums are the oddsubscripted Fibonacci numbers (A001519). Sum_{k=1..n} k*T(n,k) = Fibonacci(2n) = A001906(n).


LINKS



FORMULA

T(n,k) = Fibonacci(2(nk)) if k < n; T(n,n)=1.
G.f.: G = G(t,z) = t*z*(1z)^2/((13z+z^2)*(1tz)).
Let M be the production matrix:
1, 1, 0, 0, 0, 0, ...
2, 0, 1, 0, 0, 0, ...
3, 0, 0, 1, 0, 0, ...
4, 0, 0, 0, 1, 0, ...
5, 0, 0, 0, 0, 1, ...
...
nth row of triangle A121461 = top row terms of (n1)th power of M. (End)


EXAMPLE

T(4,2)=3 because we have UUDD(UU)DD, UUD(UU)DDD and UDUD(UU)DD, where U=(1,1) and D=(1,1) (the last ascents are shown between parentheses).
Triangle starts:
1;
1, 1;
3, 1, 1;
8, 3, 1, 1;
21, 8, 3, 1, 1;
55, 21, 8, 3, 1, 1;
...


MAPLE

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


CROSSREFS



KEYWORD



AUTHOR



STATUS

approved



