A105292 Triangle read by rows: T(n,k) is the number of directed column-convex polyominoes of area n, having leftmost column of height k.

1, 1, 1, 2, 2, 1, 5, 4, 3, 1, 13, 10, 6, 4, 1, 34, 26, 15, 8, 5, 1, 89, 68, 39, 20, 10, 6, 1, 233, 178, 102, 52, 25, 12, 7, 1, 610, 466, 267, 136, 65, 30, 14, 8, 1, 1597, 1220, 699, 356, 170, 78, 35, 16, 9, 1, 4181, 3194, 1830, 932, 445, 204, 91, 40, 18, 10, 1, 10946, 8362

Offset

1,4

Comments

T(n,k) is the number of nondecreasing Dyck paths of semilength n, having height of leftmost peak equal to k. Example: T(3,2)=2 because we have UUDDUD and UUDUDD, where U=(1,1) and D(1,-1). Sum of row n = fibonacci(2n-1) (A001519). T(n,1)=fibonacci(2n-3) (A001519). Column 2 yields A055819.

References

E. Deutsch and H. Prodinger, A bijection between directed column-convex polyominoes and ordered trees of height at most three, Theoretical Comp. Science, 307, 2003, 319-325.

Links

Table of n, a(n) for n=1..68.

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)=k*fibonacci(2n-2k-1) if k<n; T(n, n)=1. G.f.=tz(1-2z-tz+3tz^2-tz^3)/[(1-3z+z^2)(1-tz)^2].

Example

Triangle begins:
1;
1,1;
2,2,1;
5,4,3,1;
13,10,6,4,1;

Maple

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

Mathematica

Flatten[Join[{1}, #]&/@Table[k*Fibonacci[2n-2k-1], {n, 15}, {k, n-1}]] (* Harvey P. Dale, Aug 21 2013 *)

Crossrefs

Cf. A001519, A055819.

Sequence in context: A110438 A184051 A121460 * A273342 A276067 A125177

Adjacent sequences: A105289 A105290 A105291 * A105293 A105294 A105295

Keyword

nonn,tabl

Author

Emeric Deutsch, Apr 25 2005

Status

approved