1,2

"On the grid lines" means that each corner is a grid point and neighbored corners are located on a common grid line. For n=1, the only polygon is a triangle: a(1)=1. For n=2, there are (additionally) 4 triangles, 3 parallelograms and 3 trapezes: a(2)=11, see examples. For n=3, there are (additionally) 8 triangles, 12 parallelograms, 15 trapezes, 3 pentagons and 1 hexagon:

a(3)=11+39=50. Other sorts of polygons do not occur for n>3. The derivation of the algorithm, used in the maxima code, and of the formula, see link "Convex polygons on a triangular grid". In the appendix, you find all a(3)-a(2)=39 polygons and a second algorithm for safety.

Gerhard Kirchner, Convex polygons on a triangular grid

Index entries for linear recurrences with constant coefficients, signature (6,-14,14,0,-14,14,-6,1).

a(n) = (n*(n + 2)*(2*n^4 + 32*n^3 + 201*n^2 + 138*n - 48) - h)/960 with h = 0 for even n and h = 15 for odd n.

From Stefano Spezia, Dec 29 2020: (Start)

G.f.: x*(1 + 5*x - 2*x^2 - 3*x^3 + 2*x^4)/((1 - x)^7*(1 + x)).

a(n) = 6*a(n-1) - 14*a(n-2) + 14*a(n-3) - 14*a(n-5) + 14*a(n-6) - 6*a(n-7) + a(n-8) for n > 8. (End)

a(2)=11 polygons (first polygon: a(1)=1)

-

o o o o

o o o o o o o o

. . . . o . o o . . o o

-

o . . .

o o o . o o o o

o o o o o . . o . o o .

-

. . .

o o . o o o

o o o . o o . o o

(Maxima)

block(nmax: 36, a: [], su:0,

/*returns the first nmax terms*/

for n from 1 thru nmax do

(for di from 1 thru n do

for k from 0 thru n-di do

for dk from 1 thru n-k do

(if dk<=di then

(ad: (dk+1) * (1+min(dk, n-di-k)),

if dk=di then ad: ad-1)

else

ad: (di+1) * (1+min(di, n-dk-k)),

su: su + ad),

a: append(a, [su])),

return(a));

Sequence in context: A185019 A212560 A341735 * A211920 A167423 A026618

Adjacent sequences: A340127 A340128 A340129 * A340131 A340132 A340133

nonn,easy

Gerhard Kirchner, Dec 29 2020

approved