

A121469


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


2



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
(list;
table;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

0,8


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 oddsubscripted Fibonacci numbers (A001519). T(n,0)=A006356(n3). Sum(k*T(n,k),k=0..n)=A094864(n1).


LINKS

Table of n, a(n) for n=0..71.
E. Barcucci, A. Del Lungo, S. Fezzi and R. Pinzani, Nondecreasing Dyck paths and qFibonacci numbers, Discrete Math., 170, 1997, 211217.
E. Barcucci, R. Pinzani and R. Sprugnoli, Directed columnconvex polyominoes by recurrence relations, Lecture Notes in Computer Science, No. 668, Springer, Berlin (1993), pp. 282298.
E. Deutsch and H. Prodinger, A bijection between directed columnconvex polyominoes and ordered trees of height at most three, Theoretical Comp. Science, 307, 2003, 319325.


FORMULA

G.f.: G(t,z)=(12z)/[1(t+2)z+(2t1)z^2(t1)z^3)].


EXAMPLE

T(3,1)=3 because we have the three directed columnconvex polyominoes: [(0,2),(0,1)], [(0,2),(1,2)] and [(0,1),(0,2)] (here the jth pair within the square brackets gives the lower and upper levels of the jth 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;


MAPLE

G:=(12*z)/(1(t+2)*z+(2*t1)*z^2(t1)*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


CROSSREFS

Cf. A001519, A006356, A094864.
Sequence in context: A169940 A279010 A121481 * A091867 A127158 A112367
Adjacent sequences: A121466 A121467 A121468 * A121470 A121471 A121472


KEYWORD

nonn,tabl


AUTHOR

Emeric Deutsch, Aug 03 2006


STATUS

approved



