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, 0, 1

Offset: 0

Author

Emeric Deutsch, Apr 26 2005

Keywords

• nonn
• tabl

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.

Examples

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

Links

• Elena Barcucci, Alberto del Lungo, S. Fezzi, and Renzo Pinzani, Nondecreasing Dyck paths and q-Fibonacci numbers, Discrete Math., 170, 1997, 211-217.
• Emeric Deutsch and Helmut Prodinger, A bijection between directed column-convex polyominoes and ordered trees of height at most three, Theoretical Comp. Science, 307, 2003, 319-325.

Crossrefs

Cf. A001519, A027994.

Programs

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

Formula

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