login
Number of convex polygons on the lines of a triangular grid with edge length n.
1

%I #12 Jan 01 2021 12:57:21

%S 1,11,50,157,398,876,1742,3208,5561,9179,14548,22281,33138,48048,

%T 68132,94728,129417,174051,230782,302093,390830,500236,633986,796224,

%U 991601,1225315,1503152,1831529,2217538,2668992,3194472,3803376,4505969,5313435,6237930,7292637

%N Number of convex polygons on the lines of a triangular grid with edge length n.

%C "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:

%C 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.

%H Gerhard Kirchner, <a href="/A340130/a340130.pdf">Convex polygons on a triangular grid</a>

%H <a href="/index/Rec#order_08">Index entries for linear recurrences with constant coefficients</a>, signature (6,-14,14,0,-14,14,-6,1).

%F 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.

%F From _Stefano Spezia_, Dec 29 2020: (Start)

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

%F 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)

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

%e -

%e o o o o

%e o o o o o o o o

%e . . . . o . o o . . o o

%e -

%e o . . .

%e o o o . o o o o

%e o o o o o . . o . o o .

%e -

%e . . .

%e o o . o o o

%e o o o . o o . o o

%o (Maxima)

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

%o /*returns the first nmax terms*/

%o for n from 1 thru nmax do

%o (for di from 1 thru n do

%o for k from 0 thru n-di do

%o for dk from 1 thru n-k do

%o (if dk<=di then

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

%o if dk=di then ad: ad-1)

%o else

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

%o su: su + ad),

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

%o return(a));

%K nonn,easy

%O 1,2

%A _Gerhard Kirchner_, Dec 29 2020