A121469 Triangle read by rows: T(n,k) is the number of directed column-convex polyominoes of area n having k 1-cell columns (0<=k<=n).

1, 0, 1, 1, 0, 1, 1, 3, 0, 1, 3, 4, 5, 0, 1, 6, 13, 7, 7, 0, 1, 14, 28, 27, 10, 9, 0, 1, 31, 70, 62, 45, 13, 11, 0, 1, 70, 164, 171, 108, 67, 16, 13, 0, 1, 157, 392, 429, 325, 166, 93, 19, 15, 0, 1, 353, 926, 1101, 862, 540, 236, 123, 22, 17, 0, 1, 793, 2189, 2766, 2355, 1499, 824

Offset: 0

Author

Emeric Deutsch, Aug 03 2006

Keywords

• nonn
• tabl

Comments

Also number of nondecreasing Dyck paths of semilength n and such that there are k ascents of length 1. A nondecreasing Dyck path is a Dyck path for which the sequence of the altitudes of the valleys is nondecreasing. Example: T(4,2)=5 because we have (U)D(U)DUUDD, (U)DUUDD(U)D, (U)DUUD(U)DD, UUDD(U)D(U)D and UUD(U)D(U)DD, where U=(1,1) and D=(1,-1); the ascents of length one are shown between parentheses (also the Dyck path UUDUDDUD has two ascents but it is not nondecreasing because the valleys have altitudes 1 and 0). Row sums are the odd-subscripted Fibonacci numbers (A001519). T(n,0)=A006356(n-3). Sum(k*T(n,k),k=0..n)=A094864(n-1).

Examples

			T(3,1)=3 because we have the three directed column-convex polyominoes: [(0,2),(0,1)], [(0,2),(1,2)] and [(0,1),(0,2)] (here the j-th pair within the square brackets gives the lower and upper levels of the j-th column of that particular polyomino).
Triangle starts:
  1;
  0,1;
  1,0,1;
  1,3,0,1;
  3,4,5,0,1;
  6,13,7,7,0,1;
		

Links

• E. Barcucci, A. Del Lungo, S. Fezzi and R. Pinzani, Nondecreasing Dyck paths and q-Fibonacci numbers, Discrete Math., 170, 1997, 211-217.
• E. Barcucci, R. Pinzani and R. Sprugnoli, Directed column-convex polyominoes by recurrence relations, Lecture Notes in Computer Science, No. 668, Springer, Berlin (1993), pp. 282-298.
• Emeric 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.

Crossrefs

Cf. A001519 (row sums), A006356, A094864.

Programs

Maple

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

Formula

G.f.: G(t,z) = (1-2*z)/(1-(t+2)*z+(2*t-1)*z^2-(t-1)*z^3).