A054963 Number of cells in the first column of all directed column-convex polyominoes of area n+1.

1, 3, 9, 26, 72, 194, 515, 1357, 3563, 9340, 24466, 64068, 167749, 439191, 1149837, 3010334, 7881180, 20633222, 54018503, 141422305, 370248431, 969323008, 2537720614, 6643838856, 17393795977, 45537549099, 119218851345

Offset: 0

Author

Emeric Deutsch, Jun 16 2001

Keywords

• nonn

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,-8,5,-1).

Crossrefs

Cf. A000045.

Programs

PARI

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

Formula

a(n) = Fibonacci(2*n) + Fibonacci(2*n+2) - n = A002878(n)-n.

G.f.: (1-2x+2x^2)/((1-x)^2(1-3x+x^2)).

a(n) = 5*a(n-1) - 8*a(n-2) + 5*a(n-3) - a(n-4) for n >= 4. - Jinyuan Wang, Mar 10 2020