A105929 Triangle read by rows: T(n,k) is the number of directed column-convex polyominoes of area n, having k columns of height 1 starting at level 0.

1, 0, 1, 1, 0, 1, 2, 2, 0, 1, 6, 3, 3, 0, 1, 16, 9, 4, 4, 0, 1, 43, 22, 13, 5, 5, 0, 1, 114, 58, 30, 18, 6, 6, 0, 1, 301, 151, 79, 40, 24, 7, 7, 0, 1, 792, 396, 202, 107, 52, 31, 8, 8, 0, 1, 2080, 1038, 526, 270, 143, 66, 39, 9, 9, 0, 1, 5456, 2722, 1370, 701, 358, 188, 82, 48, 10, 10

Offset

0,7

Comments

T(n,k) is the number of nondecreasing Dyck paths of semilength n, having k peaks at height 1. Example: T(4,2)=3 because we have UDUDUUDD, UDUUDDUD and UUDDUDUD, where U=(1,1) and D=(1,-1). sum(T(n,k),k=0..n)=fibonacci(2n-1) (A001519). sum(k*T(n,k),k=0..n)=fibonacci(2n-1) (A001519). T(n,0)=A027994(n-2) for n>=2.

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=0..75.

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

Formula

G.f.=(1-2z)^2/[(1-3z+z^2)(1-z-z^2-tz+tz^2)].

Example

Triangle begins:
1;
0,1;
1,0,1;
2,2,0,1;
6,3,3,0,1;

Maple

G:=(1-2*z)^2/(1-3*z+z^2)/(1-z-z^2-t*z+t*z^2):Gser:=simplify(series(G, z=0, 14)): P[0]:=1: for n from 1 to 12 do P[n]:=coeff(Gser, z^n) od: for n from 0 to 12 do seq(coeff(t*P[n], t^k), k=1..n+1) od; # yields sequence in triangular form

Crossrefs

Cf. A001519, A027994.

Sequence in context: A102404 A089246 A291684 * A065600 A029583 A011289

Adjacent sequences: A105926 A105927 A105928 * A105930 A105931 A105932

Keyword

nonn,tabl

Author

Emeric Deutsch, Apr 26 2005

Status

approved