A122133 Number of different polyominoes with maximum area of the convex hull.

1, 1, 1, 3, 5, 11, 9, 26, 22, 53, 36, 93, 64, 151, 94, 228, 143, 329, 195, 455, 271, 611, 351, 798, 460, 1021, 574, 1281, 722, 1583, 876, 1928, 1069, 2321, 1269, 2763, 1513, 3259, 1765, 3810, 2066, 4421, 2376, 5093, 2740, 5831, 3114, 6636, 3547, 7513, 3991

Offset: 1

Author

Sascha Kurz, Aug 21 2006

Keywords

• nonn
• easy

Links

• Colin Barker, Table of n, a(n) for n = 1..1000
• K. Bezdek, P. Brass and H. Harborth, Maximum convex hulls of connected systems of segments and of polyominoes, Beiträge Algebra Geom., Vol. 35(1) (1994), pp. 37-43.
• S. Kurz, Polyominoes with maximum convex hull, Diploma thesis, Bayreuth (2004).
• Index entries for linear recurrences with constant coefficients, signature (0,2,0,1,0,-4,0,1,0,2,0,-1).

Programs

Maple

A122133 := proc(n)
    if modp(n,4)= 0 then
        (n^3-2*n^2+4*n)/16 ;
    elif modp(n,4)= 1 then
        (n^3-2*n^2+13*n+20)/32 ;
    elif modp(n,4)= 2 then
        (n^3-2*n^2+4*n+8)/16 ;
    else
        (n^3-2*n^2+5*n+8)/32 ;
    fi;
end proc: # R. J. Mathar, May 19 2019

PARI

Vec(x*(1+x-x^2+x^3+2*x^4+4*x^5+2*x^6+5*x^7+2*x^8+x^9)/((1-x)^4*(1+x)^4*(1+x^2)^2) + O(x^80)) \\ Colin Barker, Oct 14 2016

Formula

a(n) = (n^3 - 2*n^2 + 4*n)/16 if n mod 4 = 0;

a(n) = (n^3 - 2*n^2 + 13*n + 20)/32 if n mod 4 = 1;

a(n) = (n^3 - 2*n^2 + 4*n + 8)/16 if n mod 4 = 2;

a(n) = (n^3 - 2*n^2 + 5*n + 8)/32 if n mod 4 = 3.

G.f.: (1 + x - x^2 - x^3 + 2*x^5 + 8*x^6 + 2*x^7 + 4*x^8 + 2*x^9 - x^10 + x^12)/((1-x^2)^2*(1-x^4)^2).

From Luce ETIENNE, Aug 14 2019: (Start)

a(n) = 4*a(n-4) - 6*a(n-8) + 4*a(n-12) - a(n-16).

a(n) = 2*a(n-2) + a(n-4) - 4*a(n-6) + a(n-8) + 2*a(n-10) - a(n-12).

a(n) = (3*n^3 - 6*n^2 + 17*n + 22 + (n^3 - 2*n^2 - n - 6)*(-1)^n - 4*(4*cos(n*Pi/2) - (2*n+3)*sin(n*Pi/2)))/64. (End)

E.g.f.: (1/64)*(-exp(-x)*(6 - 2*x - x^2 + x^3) + exp(x)*(22 + 14*x + 3*x^2 + 3*x^3) - 4*(4*cos(x) - 2*x*cos(x) - 3*sin(x))). - Stefano Spezia, Aug 14 2019