Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

What is the maximum number of regions produced, i.e. $f(n)$, by joining all vertexes with line segments of a convex polygon with $n$ sides?

enter image description here

For example, for the hexagon on the left, number of regions is 24, but the one on right is 25, which I think is in fact $f(n)$ for the case $n=6$.

So is there any way to find the general equation for $f(n)$?

Thank you.

share|improve this question

3 Answers 3

up vote 2 down vote accepted

It should be fairly obvious to you (as seen from your two diagrams) that the maximum number of interior regions are generated when no three or more diagonals have a common intersection point. The proof is fairly simple for this. Now, we will consider the number of regions that are created when no three or more diagonals have a common intersection point. We show this by recursively adding an extra node:

Let the maximum number of interior regions in a convex polygon having $n$ sides be $f(n)$. For the base case, consider $f(4) = 4$, which is trivial.

Let us add an extra vertex $P_{n+1}$ to an $n$-sided polygon, to make it an $n+1$ sided polygon. It will have $n-2$ new diagonals originating from it. Let the vertices in the original polygon that are closest to the new vertex be labeled $P_1$ and $P_n$. Then, the side $P_1P_n$ is also a new diagonal in the new polygon. We note that once any of the new diagonal originating from the vertex $P_{n+1}$ enters the smaller polygon, when it moves from its intersection of any diagonal of the new polygon (including $P_1P_n$) to any other diagonal or termination vertex, it divides the region into two parts, thus creating an extra region. What this translates to is that the number of extra regions created inside the old polygon, is equal to the number of times any newly created diagonal originating from $P_{n+1}$ intersects another diagonal (including $P_1P_n$). The number of different ways this can happen can be found by fixing the ending point of the diagonal originating from $P_{n+1}$, and the possible ending points of the other diagonal. All three points will be among the vertices of the original polygon, i.e., among $P_1 ... P_n$. Thus, we have to choose 3 integers out of $1 ... n$, which is $n\choose3$.

Also note that the newly formed $\triangle$$P_1P_nP_{n+1}$ will be divided into $n-1$ regions by the $n-2$ new diagonals originating from $P_{n+1}$. Thus, the total increase in regions is $n\choose3$$+ (n-1)$, giving the recurrence relation:

$f(n+1) = f(n) + {n\choose3} + (n-1)$

Solving this recurrence relation gives the following closed form expression:

$f(n) = \frac{1}{24}n(n-3)[n(n-3) + 14] + 1$

Another solution giving identical (but expressed differently) result can be found here.

share|improve this answer

Let $v$ be the number of vertices, $e$ the number of edges and $f$ the number of faces (not counting the exterior of the given $n$-gon $P$) in the resulting configuration. Then by Euler's formula $$v+f = e+1\ .$$ On the other hand the number of vertices is given by $$v=n+{n\choose 4}\ ,$$ because any four vertices of $P$ determine a unique vertex in the interior of $P$. Finally the number of edges satisfies $$2e=n(n-1)+4{n\choose 4}\ ,$$ because each vertex of $P$ has degree $n-1$ and each inner vertex has degree $4$.

Solving these three equations for $f$ we get $$f={n(n-1)\over2}+2{n\choose 4}-n-{n\choose 4}+1={1\over24}(n^4-6n^3+23n^2-42n+24)\ .$$

share|improve this answer

Probably

A006522 4-dimensional analogue of centered polygonal numbers. Also number of regions created by sides and diagonals of n-gon. (Formerly M3413) 12

1, 0, 0, 1, 4, 11, 25, 50, 91, 154, ...

See its references, notes and formula's, for example it is the sum of several binomials.

FORMULA a(n)=binomial(n, 4)+ binomial(n-1, 2)+ binomial(n,2)+binomial(n,3)+binomial(n,4), n>=-1.

Nice tool, The On-Line Encyclopedia of Integer Sequences!

share|improve this answer

Your Answer

 
discard

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.