OFFSET
1,2
COMMENTS
"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.
LINKS
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).
FORMULA
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)
EXAMPLE
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
PROG
(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));
CROSSREFS
KEYWORD
nonn,easy
AUTHOR
Gerhard Kirchner, Dec 29 2020
STATUS
approved