Suppose we are given a convex plane figure F, and a system of N segments, each of which splits the figure into two parts (the endpoints of the segments lie on the perimeter of the figure).

Denote by:
a - the total number of parts into which the segments divide the figure;
b - the number of pairs of segments intersecting in the interior of the figure;
T_k - the number of interior intersection points of the segments meeting exactly k segments, for k=2, 3, 4,... (These points are labeled in the links to A357007 as "2k ngons". Points related to T_2 are called "simple" there.)

It is easy to prove by induction that

a = 1 + N + T_2 + 2*T_3 + 3*T_4 + 4*T_5 + . . . (1)

Also, V. Korsukov proved that

b = T_2*Binomial(2,2) + T_3*Binomial(3,2) + T_4*Binomial(4,2) + T_5*Binomial(5,2) + . . . (2)

In the particular case where all interior intersection points are "simple", the formulas take the form

a = 1 + N + T_2
b = T_2

and

a = 1 + N + b.

In the big triangle from A356984, obviously we have N(n)=3n, and also b(n)=6*Binomial(n,2)=3*n*(n-1). (The edges of every two inscribed triangles intersect at 6 points, as shown by V. Korsukov.) Thus, in the particular case where all interior intersection points are "simple", we have the exact formula

A356984(n) = 1 + 3n + 3n(n-1) = 1 + 3*n^2.

Moving on to the general case, we substitute T_2 from (2) into (1) to obtain the following refined formula for the number of parts:

a = 1 + N + b – 2*1*T_3/2 – 3*2*T_4/2 – 4*3*T_5/2 - ...

and it follows that

A356984(n) = 1 + 3*n^2 – 2*1*T_3/2 – 3*2*T_4/2 – 4*3*T_5/2 - ...

It remains to calculate the number of "non-simple" interior intersection points of each type: T_3, T_4, T_5,...

The simplest algorithm for finding them, for small n, is as follows. The equations of all segments are written in some Cartesian coordinate system. The exact coordinates of the intersection points of all b pairs of segments are found by solving these equations. If some point is shared by k segments, then there are Binomial(k,2) pairs of segments meeting at this point, from which we can find k. (For example, if a point occurs 6 times, then it belongs to T_4.)

There is a faster algorithm for the triangles of A356984.

We color the edges of the inner triangles with three colors, determined by the pairs of edges of the big triangle they are connecting. Say, for n=5 we have the following picture:

We number the vertices of the inner triangles from 1 to n, so that the three vertices of every triangle receive the same number, see the picture. We notice the following two facts:

a. Three segments of the same color cannot intersect at the same point.

b. Three segments of different colors cannot intersect at the same point.

Thus, only the following two types of "non-simple" interior intersection points can occur:

a. Intersection points of two segments of the same color and one segment of another color.

b. Intersection points of two segments of the same color and two segments of another color.

Points of the first kind are of the type T_3. (There are 6 such points in the picture. One of them is the intersection point of the red segments 1 and 3 and the green segment 4.) Points of the second kind are of the type T_4; they first appear for n=11.

As for the T_k with k>4, they are all equal to zero.

Therefore (S. Vodovoz):

A356984(n) = 1 + 3*n^2 – T_3 – 3*T_4

Concerning the associated sequences A357007 and A357008 we remark that substituting in the obvious formula

A357007(n) = 3 + 3n + T_2 + T_3 + T_4

the value of T_2 from the formula (2), we get

A357007(n) = 3 + 3*n^2 – 2*T_3 – 5*T_4
 
and
 
A357008(n) = 3 + 6n + 2*T_2 + 3*T_3 + 4*T_4
A357008(n) = 3 + 6*n^2 – 3*T_3 – 8*T_4

Back to calculating T_3 and T_4. For a given n, we will look for the numbers u, v and w of two red and one green segment intersecting at the same point, such that 0 < u < v < w < n + 1. (Every red segment has an interior intersection point with all green segments of larger numbers.) It was also proved by S. Vodovoz that u < (n+1)/3.

To simplify further calculations, we transform the original equilateral triangle into an isosceles right triangle, keeping the division of its sides into n+1 equal parts:

Such a transformation does not change the relative positions of the interior intersection points, i.e., does not change the values ​​of T_2, T_3, and T_4.

If the lower left corner has coordinates (0,0), then the coordinates of the vertices of the inscribed triangles are:
(0,k), (k,n+1-k), (n+1-k,0) (k=1,2,...,n).

The equations of the two red and one green segments are

x(n+1-2u) – uy = - u^2
x(n+1-2v) – vy = - v^2
wx + (n+1-w)y = w(n+1-w)

For them to meet at one point, the determinant of the coefficient matrix must be equal to zero:

det(
 n+1-2u, -u, -u^2;
 n+1-2v, -v, -v^2;
 w, b+1-w, w*(n+1-w)
) = 0

After simple transformations, we obtain the necessary condition for the parameters u, v, w to satisfy:

(n+1)^2*(u+v-w) – (n+1)*(uw+vw+2uv-w^2) + 3uvw = 0  .... (3)

As a corollary, 3uvw is divisible by n+1. In particular, this is impossible if n+1 is a prime greater than 3, in which case

A356984(n) = 1 + 3*n^2

It can be shown that for n+1=2p (with p>3 prime) all intersection points are simple. Moreover, S. Vodovoz conjectures that this is also the case for n+1=p^k (p not equal to 3), and for n+1=2*p^2 (p>3).

On the other hand, the identity (3) is always true when n+1>3 is a multiple of 3, w=(n+1)*2/3, and u+v=w.

Finding for a given n those triples (u, v, w) satisfying equality (3), and determining whether the points found belong to T_3 or T_4, can be carried out by a brute force computation.

The first method.
For each pair (u, v), equality (3) becomes a quadratic equation in the unknown w. If there are two integer roots between v and n+1, then a point from T_4 is found. If there is only one such root, then (u, v, w) determines a point from T_3.

The second method.
This method is somewhat more complicated, but it works faster (at least if implemented in the MUMPS language). For each pair (u, w), we can consider (3) as a linear equation in the unknown v. A solution v is admissible if it is an integer greater than u and less than w. For a fixed u, the solution can occur once or twice, for two different values of w. Accordingly, the point found belongs to either T_3 or T_4.

Taking the symmetry into account, each point of type T_3 (found by either of the two methods) corresponds, in fact, to six such points, and each point of type T_4 corresponds to three such points.

A MUMPS program that calculates A356984(n), T_2(n), T_3(n), and T_4(n) for n=1000:

A356984	; Computing A356984(n), T2(n), T3(n) & T4(n) ; [ 04.10.2022 ]
	;--------------------------------------------*
	write "Begin: ",$zhl(1,"dd-Mon-yyyy"),$zhl(2," HH:mm:ss"),!!
	set n=1000
	do Comp(n)
	write $name(A356984(n))," = ",a,!
	write $name(T2(n))," = ",T2,!
	write $name(T3(n))," = ",T3,!
	write $name(T4(n))," = ",T4,!!
	write "End:   ",$zhl(1,"dd-Mon-yyyy"),$zhl(2," HH:mm:ss")
	quit
	;
Comp(n)	kill R
	set a=n**2*3+1,T2=n-1*n*3,(T3,T4)=0
	for u=1:1:n+1\3 for w=u+2:1:n do
	.set Q=n+1-(u*2)-w*(n+1)+(u*w*3) if Q'>0 quit
	.set v=w-u*(n+1-w)*(n+1) quit:v#Q
	.set v=v\Q
	.if v>u,v<w set R(u,v)=$get(R(u,v))+1
	set g="R" for  set g=$zorder(@g) quit:g=""  do
	.if @g=2 set a=a-9,T2=T2-18,T4=T4+3
	.else  set a=a-6,T2=T2-18,T3=T3+6
	quit

Begin: 04-Oct-2022 19:03:31

A356984(1000) = 2999875
T2(1000) = 2996676
T3(1000) = 72
T4(1000) = 18

End:   04-Oct-2022 19:03:32

Similar results can be obtained for the sequences A357058 (squares) and A357196 (hexagons). The following tables show the formulas associated with these sequences, including formulas that can be used to find quickly the triples (u, v, w) described above. The tables also give the first few members of the sequences T_2, T_3 and T_4.

Triangles	
A356984(n) = 1 + 3*n + T_2(n) + 2*T_3(n) + 3*T_4(n)	
A357007(n) = 3 + 3*n + T_2(n) + T_3(n) + T_4(n)	
A357008(n) = 3 + 6*n + 2*T_2(n) + 3*T_3(n) + 4*T_4(n)	
A356984(n) = 1 + 3*n^2 - T_3(n) - 3*T_4(n)	
A357007(n) = 3 + 3*n^2 - 2*T_3(n) - 5*T_4(n)	
A357008(n) = 3 + 6*n^2 - 3*T_3(n) - 8*T_4(n)	
v = n*(w-u)*(n-w) / (n*(n-2*u-w) + 3*u*w)	
T_2 = 0, 0, 6, 18, 36, 42, 90, 126, 132, 216, 270, 258, 396, 468, 474, 630, 720, 672, 918, 990, 1032, 1260, 1386, 1374, 1656, 1800, 1770, 2088, 2268, 2220, 2610, 2790, 2796, 3168, 3330, 3210, 3780, 3996, 4002, 4338, 4680, 4668, 5166, 5382, 5298, 5940, 6210, 6162, 6768, 7056, 7062,...	
T_3 = 0, 0, 0, 0, 0, 6, 0, 0, 12, 0, 0, 12, 0, 0, 24, 0, 0, 30, 0, 6, 36, 0, 0, 36, 0, 0, 36, 6, 0, 60, 0, 0, 60, 0, 6, 84, 0, 0, 72, 18, 0, 84, 0, 12, 96, 0, 0, 72, 0, 0, 96,...	
T_4 = 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 6, 0, 0, 0, 0, 0, 9, 0, 3, 0, 0, 0, 6, 0, 0, 12, 0, 0, 6, 0, 0, 0, 0, 3, 18, 0, 0, 0, 9, 0, 0, 0, 0, 15, 0, 0, 18, 0, 0, 0,...	

Squares	
A357058(n) = 1 + 4*n + T_2(n) + 2*T_3(n) + 3*T_4(n)	
A357060(n) = 4 + 4*n + T_2(n) + T_3(n) + T_4(n)	
A357061(n) = 4 + 8*n + 2*T_2(n) + 3*T_3(n) + 4*T_4(n)	
A357058(n) = 1 + 4*n^2 - T_3(n) - 3*T_4(n)	
A357060(n) = 4 + 4*n^2 - 2*T_3(n) - 5*T_4(n)	
A357061(n) = 4 + 8*n^2 - 3*T_3(n) - 8*T_4(n)	
v = n*(w-u)*(n-w) / (n*(n-u-w) + 2*u*w)	
T_2 = 0, 0, 8, 24, 48, 56, 120, 120, 224, 240, 360, 368, 528, 552, 728, 744, 960, 968, 1224, 1272, 1520, 1560, 1848, 1808, 2208, 2256, 2600, 2640, 3024, 3032, 3480, 3504, 3944, 4032, 4488, 4496, 5040, 5112, 5600, 5664, 6240, 6224, 6888, 6960, 7544, 7656, 8280, 8192, 9024, 9072, 9776,...	
T_3 = 0, 0, 0, 0, 0, 8, 0, 16, 0, 16, 0, 16, 0, 24, 0, 32, 0, 24, 0, 32, 0, 40, 0, 64, 0, 48, 0, 56, 0, 64, 0, 56, 8, 64, 0, 64, 0, 72, 8, 80, 0, 96, 0, 88, 8, 88, 0, 128, 0, 80, 8,...	
T_4 = 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 4, 0, 0, 0, 0, 0, 8, 0, 0, 0, 0, 0, 4, 0, 0, 0, 0, 0, 4, 0, 8, 0, 0, 0, 12, 0, 0, 0, 4, 0, 8, 0, 0, 0, 0, 0, 12, 0, 16, 0,...	

Hexagons	
A357196(n) = 1 + 6*n + T_2(n) + 2*T_3(n) + 3*T_4(n)	
A357197(n) = 6 + 6*n + T_2(n) + T_3(n) + T_4(n)	
A357198(n) = 6 + 12*n + 2*T_2(n) + 3*T_3(n) + 4*T_4(n)	
A357196(n) = 1 + 6*n^2 - T_3(n) - 3*T_4(n)	
A357197(n) = 6 + 6*n^2 - 2*T_3(n) - 5*T_4(n)	
A357198(n) = 6 + 12*n^2 - 3*T_3(n) - 8*T_4(n)	
v = n*(w-u)*(n-w) / (n*(n-w) + u*w)	
T_2 = 0, 0, 12, 36, 72, 120, 180, 252, 336, 396, 540, 624, 792, 936, 1056, 1260, 1440, 1632, 1836, 1980, 2280, 2520, 2772, 2892, 3312, 3600, 3900, 4176, 4536, 4764, 5220, 5580, 5916, 6336, 6696, 6996, 7560, 7992, 8400, 8640, 9360, 9768, 10332, 10764, 11280, 11880, 12420, 12792, 13536, 14076, 14664,...	
T_3 = 0, 0, 0, 0, 0, 0, 0, 0, 0, 12, 0, 12, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 24, 0, 0, 0, 0, 0, 24, 0, 0, 12, 0, 12, 48, 0, 0, 12, 48, 0, 0, 0, 24, 12, 0, 0, 12, 0, 12, 12,...	
T_4 = 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 6, 0, 0, 0, 0, 12, 0, 0, 0, 12, 0, 0, 0, 6, 0, 6, 0, 0, 0, 0, 0, 0, 0, 0, 0, 18, 0, 12, 0, 0, 6, 0, 0, 24, 0, 0, 0,...	

Remarks.

1. Triangles, squares and hexagons have their different T_2, T_3 and T_4.
 
2. In all three cases T_3(n)=T_4(n)=0 when n+1 is prime.
 
3. The formulas given here for the OEIS sequences generalize easily to any m-gons:

m-gons	
Regions: 1 + m*n + T_2(n) + 2*T_3(n) + 3*T_4(n)	
Vertices: m + m*n + T_2(n) + T_3(n) + T_4(n)	
Edges: m + 2*m*n + 2*T_2(n) + 3*T_3(n) + 4*T_4(n)	
Regions: 1 + m*n^2 - T_3(n) - 3*T_4(n)	
Vertices: m + m*n^2 - 2*T_3(n) - 5*T_4(n)	
Edges: m + 2*m*n^2 - 3*T_3(n) - 8*T_4(n)	

S. Vodovoz proved that triples (u, v, w) defining non-simple vertices can exist for m-gons only if cos(2π/m) is rational. This proves the following conjectures of Scott R. Shannon:
Conjecture 1. The only m-gons that contain non-simple intersections are the 3-gon (triangle), 4-gon (square), and 6-gon (hexagon).
Conjecture 2. For m other than 3, 4, and 6, we have the following exact formulas:
Regions: 1 + m*n^2	
Vertices: m + m*n^2	
Edges: m + 2*m*n^2	

Thanks to Professor Vsevolod (Seva) Lev for editing and translating this article to English.