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

Author

Emeric Deutsch, Aug 04 2006

Keywords

• nonn
• easy

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.

Examples

			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.
		

Links

• 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).

Crossrefs

Cf. A121469, A121301.

Programs

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);

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

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