OFFSET
3,4
COMMENTS
Alternatively, total number of regions left over when partitioning the set of vertices of a convex n-gon into nonintersecting polygons, each containing adjacent vertices of the n-gon.
FORMULA
For k >= 3, a(3*k) = 3, a(3*k+1) = 3*k+1, a(3*k+2) = 3 + a(3*k-2) + a(3*k-1), with a(3)=a(4)=a(5)=0 and a(6) = 3, a(7) = 7, a(8) = 12.
EXAMPLE
n = 18 is an 18-gon, which has 6 triangles each containing adjacent vertices of the 18-gon and the leftover region in each case is a 12-gon. Since there are only 3 orientations of partitioning, the total number of leftover regions is 3.
n = 19 is a 19-gon, which has 5 triangles and 1 quadrilateral each containing adjacent vertices of the 19-gon and the leftover regions in each case is a 12-gon. Since there are 19 orientations of partitioning, the total number of leftover regions is 19.
n = 20 is a 20-gon, which has 5 triangles with one pentagon or 4 triangles with 2 quadrilaterals. In the first case the number of leftover regions is 20 because it has 20 orientations, in the second case the number of leftover regions is 20 + 20 + 10 = 50 because it has 3 different permutations of 3,3,3,3,4,4 with 20 orientations, 3,3,3,4,3,4 with 20 orientations, and 3,3,4,3,3,4 with 10 orientations. Therefore the total is 70.
MATHEMATICA
Nest[Append[#1, Switch[Mod[#2, 3], 0, 3, 1, #2, 2, 3 + Total@ #1[[3 Quotient[#2, 3] - 4 ;; 3 Quotient[#2, 3] - 3]]]] & @@ {#, Length[#] + 3} &, ConstantArray[0, 3]~Join~{3, 7, 12}, 66] (* Michael De Vlieger, Feb 04 2022 *)
PROG
(PARI) a(n) = if (n==6, 3, if (n==7, 7, if (n==8, 12, my(x=n%3); if (x==0, 3, if (x==1, n, 3 + a(n-4) + a(n-3)))))); \\ Michel Marcus, Feb 01 2022
CROSSREFS
KEYWORD
nonn
AUTHOR
Janaka Rodrigo, Jan 31 2022
STATUS
approved