A121302 Number of directed column-convex polyominoes having at least one 1-cell column.

1, 1, 4, 10, 28, 75, 202, 540, 1440, 3828, 10153, 26875, 71021, 187421, 494013, 1300844, 3422509, 8998118, 23642479, 62088032, 162978242, 427648023, 1121766397, 2941697012, 7712415568, 20215976824, 52981414253, 138831400836

Offset

1,3

Comments

a(n) = Fibonacci(2n-1) - A121469(n,0) (obviously, since A121469(n,k) is the number of directed column-convex polyominoes of area n having k 1-cell columns). Column 1 of A121301.

Links

Table of n, a(n) for n=1..28.

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.

Index entries for linear recurrences with constant coefficients, signature (5,-6,-2,4,-1).

Formula

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

a(n) = A001519(n)-A077998(n-2), n>0. - R. J. Mathar, Jul 22 2022

Example

a(3)=4 because, with the exception of the 3-cell column, all the other four directed column-convex polyominoes of area 3 have a 1-cell column.

Maple

G:=z*(1-z)*(1-3*z+2*z^2)/(1-3*z+z^2)/(1-2*z-z^2+z^3): Gser:=series(G, z=0, 35): seq(coeff(Gser, z, n), n=1..32);

Prog

(PARI) Vec(z*(1-z)*(1-3*z+2*z^2)/((1-3*z+z^2)*(1-2*z-z^2+z^3)) + O(z^40)) \\ Michel Marcus, Feb 14 2016

Crossrefs

Cf. A121469, A121301.

Sequence in context: A203293 A111308 A348057 * A026150 A026123 A091468

Adjacent sequences: A121299 A121300 A121301 * A121303 A121304 A121305

Keyword

nonn,easy

Author

Emeric Deutsch, Aug 04 2006

Status

approved