# What's the formula from the number of sections $N$ in an $n$-polygon (where all vertices are connected to each other)? .. and Prove it

so... $n=3$ gives $N=1$ $n=4$ gives $N=4$ $n=5$ gives $N=11$ ... etc

I (by observation) assumed the answer to be: $N=2^{n-1} - n$

$+n$.

-

Well, three initial terms is not usually much to guess a sequence... :-) The complete proof must be quite difficult: for example

But at least you can guess that the number of regions grows as $n^4$, by -approximately- counting the number of crossings, then applying Euler formula.

For example (I just thought of this, perhaps there are more easy ways): fix a vertex, and consider a diagonal that leaves $k_1$ external vertices on one side and $k_2=n-2-k_1$ on the other. This diagonal will be crossed by $k_1 \times k_2$ diagonals; so, summing over all diagonals for this vertex, we have $$\sum_{k=1}^{n-3} k \; (n-2-k)=(n-3)(n-2)\left[\frac{n-2}{2}-\frac{2n-5}{6}\right] \approx \frac{1}{6}n^3$$

internal crossings associated with this vertex, (using this and this), and the same order of internal edges (one more for each diagonal, plus the two external, gives the above plus $n-1$). Now, to get the total number of crossings, we multiply by $n$ (each external vertex) and divide by 4 (because each crossing is associated to 4 external vertices. For counting the edges, we divide instead by two.

So $$V \approx \frac{1}{24} n^4$$ $$E \approx \frac{1}{12} n^4$$

Applying Euler formula, we get an estimate (asymptotic) of the number of regions as$$R = E - V + 1 \approx \frac{1}{24} n^4$$

which agrees with the exact formula. Of course, this counting method is approximate because it fails to take into account that some crossings are formed by more than two intersecting diagonals, but we can expect that this error becomes asymptotically negligible.

Update: computing all the terms of my approximation I get:

$$V(n) = \frac{1}{24}(n^4-6 n^3+11 n^2-6n)$$ $$E(n) = \frac{1}{12}(n^4-6 n^3+17 n^2-12 n)$$ $$R(n) = \frac{1}{24} (n^4-6 n^3+23 n^2-18n+24)$$

while the exact formula, according to WolframMath for even vertices, is

$$R(n) = \frac{1}{24} (n^4-6 n^3+23 n^2-42n+24)$$

I must confess I didn't expect such a good approximation, I was amply satisfied with a correct leading coefficient.

-

I consider a generic convex $n$-gon $P$. This means that no three diagonals meet in the same interior point. Let $f$, $e$, $v$ be the number of faces (not counting the exterior of $P$), edges and vertices in the resulting network. Any four vertices of $P$ determine one pair of intersecting diagonals, so there are exactly $v_i={n\choose 4}$ inner vertices, and one has $$v=v_i+n\ ,\qquad 2e=4v_i +n(n-1)\ .$$ Therefore we get by Euler's formula \eqalign{f&=e-v+1=2v_i+{n(n-1)\over2}-v_i-n+1=v_i+{n(n-3)\over2}+1\cr &={n(n-3)\over24}(n^2-3n+14)+1\ .\cr} For $n=3,4,5$ one obtains $f=1,4,11$, as expected.

-