# 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?

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?

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.

-

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.

-

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)\ .$$

-

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!

-