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