Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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$

However the answer is


Can anyone explain how/why please?

share|cite|improve this question

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.

share|cite|improve this answer

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.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.