login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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). 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 odd-subscripted Fibonacci numbers (A001519). T(n,0)=A006356(n-3). Sum(k*T(n,k),k=0..n)=A094864(n-1).

LINKS

Table of n, a(n) for n=0..71.

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.

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.

FORMULA

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

EXAMPLE

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;

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

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

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy .

Last modified February 24 14:41 EST 2018. Contains 299623 sequences. (Running on oeis4.)