login
A351103
a(n) is the total number of polygons left over with maximum number of sides when partitioning the set of vertices of a convex n-gon into nonintersecting polygons.
0
0, 0, 0, 3, 7, 12, 3, 10, 22, 3, 13, 35, 3, 16, 51, 3, 19, 70, 3, 22, 92, 3, 25, 117, 3, 28, 145, 3, 31, 176, 3, 34, 210, 3, 37, 247, 3, 40, 287, 3, 43, 330, 3, 46, 376, 3, 49, 425, 3, 52, 477, 3, 55, 532, 3, 58, 590, 3, 61, 651, 3, 64, 715, 3, 67, 782, 3, 70, 852, 3, 73, 925
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
Total number of left out regions is A347862.
Sequence in context: A057992 A082600 A355314 * A332464 A256563 A349888
KEYWORD
nonn
AUTHOR
Janaka Rodrigo, Jan 31 2022
STATUS
approved