Number of Regions in a Convex Polygon

Date: 04/29/2008 at 16:20:35
From: Fernando
Subject: Number of regions in a convex polygon 

How many regions is a convex polygon divided into by its diagonals, if
no three are concurrent?  

The solution is nC4 + (n-1)C2 for n >= 4.  What is the meaning of this
solution?  Why are no three diagonals concurrent?

Date: 05/02/2008 at 20:29:19
From: Doctor Jordan
Subject: Re: Number of regions in a convex polygon

Hi Fernando,

For a convex n-gon with vertices A_1,A_2,...,A_n, such that when all
the vertices are joined by diagonals no three diagonals intersect at a
single point in the interior of the n-gon, let f(n) be the number of
regions in the n-gon.  We will find a recurrence relation for f(n),
and when we solve the recurrence relation we will find that 

  f(n) = C(n,4) + C(n-1,2)

where C(i,j) is i choose j.

Indeed there are some convex n-gons where three diagonals will
intersect at a single point, but we are only considering the convex
n-gons where this does not happen.  It is not obvious that these 
exist, but we are assuming they do for this question.

Let us add a vertex A_{n+1} to get a convex (n+1)-gon such that when
all the vertices are joined by diagonals no three diagonals intersect
at a single point in the interior of the (n+1)-gon.

For each k=2,3,...,n-1, the diagonal from A_{n+1} to A_k is 
intersected by the diagonals from the vertices A_1,...,A_{k-1} to the
vertices A_{k+1},...,A_n.  There will be (k-1)*(n-k) points of
intersection on the diagonal A_{n+1}A_k, which will divide it into
(k-1)*(n-k)+1 segments.  Each of these segments adds 1 region; you
might need to draw a few examples to see this.

Furthermore, if we ignore the diagonals that include the point 
A_{n+1}, there are f(n)+1 regions, since we have all the regions that
were in the n-gon, and the new triangle with vertices A_1, A_{n+1} and
A_n.

Therefore

  f(n+1) = f(n) + 1 + sum_{k=2}^{n-1} ((k-1)(n-k)+1).

It takes a few lines but we work this out and get

  f(n) + (n-1) + C(n,3).

Play around with this a bit more to find

  f(n) = C(n,4) + C(n-1,2).

This solution follows the one on p.p. 249-250 of "Counting and
Configurations: Problems in Combinatorics, Arithmetic, and Geometry"
by Jiri Herman, Radan Kucera, Jaromír Šimša, and Karl Dikher.

It took me a while for this argument to make sense.  Please spend time
thinking about it, and maybe draw the convex 5-gon and convex 6-gon.
If it still doesn't make sense please write back.

- Doctor Jordan, The Math Forum
  http://mathforum.org/dr.math/