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, 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
Keywords
Examples
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.
Crossrefs
Total number of left out regions is A347862.
Programs
-
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 *) -
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
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.
Comments