Situation $2$:
For each selection of any $4$ points on the circumference, you can draw the diagram you have. The line segment that joins the adjacent circumference points, could instead join any of the $4$ pairs of adjacent circumference points, so we have $4$ different triangles for each choice of $4$ circumference points.
There are $\binom{n}{4}$ ways to choose the $4$ points, so Situation $2$ contributes:
$\qquad4 \binom{n}{4}$ triangles.
Situation $3$:
For each selection of any $5$ points on the circumference, you can draw the diagram you have. You could choose any of these $5$ points to be a vertex of a Situation $3$ triangle, so we have $5$ different triangles for each choice of $5$ circumference points.
There are $\binom{n}{5}$ ways to choose the $5$ points, so Situation $3$ contributes:
$\qquad5 \binom{n}{5}$ triangles.
Situation $4$:
For each selection of any $6$ points on the circumference, you can draw the diagram you have. There is only one way to construct that internal triangle given these $6$ circumference points.
There are $\binom{n}{6}$ ways to choose the $6$ points, so Situation $4$ contributes:
$\qquad \binom{n}{6}$ triangles.
First off, there is a missing case for $n = 3$ : the one where you pair $(2,3), (1,4), (6,5)$.
Now the recursion to count the number of pairing would go like this :
Let us take a fixed point $O$ among one of the $2n$ points on the circle.
A line going from this point would have to divide the circle into two regions, each containing an even number of points. There are thus $n$ possible choices for a chord leaving from $O$ (make a drawing).
Choosing one such cord will lead to unique divisions of the circle (two different cords leaving from $O$ will give different divisions). Reciprocally, any division of the circle would match with one of these cords. So we have correctly divided our problem into a set of disjoint subproblems.
Then, to get a recursive formula, we need to count how many points are on each side of the cord, for each possible cord : the regions have $(2k, 2(n-k-1))$ points, for $0\leq k \leq n-1$.
So finally, a recursive formula for $h(n)$ would be :
$h(n) = \sum_{k=0}^{n-1} h(k) \times h(n-k-1)$.
Best Answer
I do not think there is a better approach to find the number of parts (part ii) comparing to the Euler's formula. But to use it one should first find the number of vertices and edges, and for this task I do not see how the Euler's formula can help.
For simplicity we disregard the circle arcs and will consider only the graph consisting of line segments connecting the points.
Let $s$ be a segment connecting two points of the circle. The points split the circle in two parts. Let the number of points in one of the parts be $k$. Then the number of points in the other part is $(n-k-2)$. Every segment which connects a point lying in one part with a point lying in the other part will intersect the segment $s$, whereas any segment connecting two points lying in the same part will not intersect $s$. Therefore the overall number of intersection points of the segment $s$ with other segments is $k(n-2-k)$ and the overall number of intersection points on all segments drawn from each of the considered circle points is: $$ v''_n=\sum_{k=0}^{n-2}k(n-2-k)=\frac{(n-1)(n-2)(n-3)}6=\binom{n-1}3\tag1 $$ and the overall number of the intersection points inside the circle is $$ v'_n=\frac n4 v''_n=\binom n4,\tag2 $$ where factor 4 in the denominator accounts for the fact that while summing over all $n$ circle points every internal intersection point is counted 4 times.
To compute the overall number of vertices we shall add the number of the circle points to the obtained result: $$ v_n=v'_n+n=\frac{n(n+1)(n^2-7n+18)}{24}.\tag3 $$
The number of edges can be computed similarly. Observe that the segment $s$ is split by $n_s$ internal intersection points into $n_s+1$ edges therefore: $$ e''_n=\sum_{k=0}^{n-2}[k(n-2-k)+1]=\binom{n-1}3+\binom{n-1}1=\frac{(n-1)(n^2-5n+12)}6,\tag4 $$ and the overall number of the edges inside the circle is $$ e'_n=\frac n2 e''_n=\frac{n(n-1)(n^2-5n+12)}{12},\tag5 $$ where factor 2 in the denominator accounts for the fact that while summing over all $n$ circle points every chord is counted 2 times.
To compute the overall number of edges we shall add the number of arcs connecting the circle points to the obtained result: $$ e_n=e'_n+n=\frac{n^2(n^2-6n+17)}{12}.\tag6 $$ Finally we use the Euler's formula for computing the number of parts inside the circle: $$ f_n=e_n-v_n+1=\frac{n^4-6n^3+23n^2-18n+24}{24}.\tag7 $$
And indeed the latter formula describes - as it should - the OEIS sequence A000127.