Counting Regions Formed by Chords of a Circle

Date: 05/19/98 at 23:21:57
From: Jay Shah
Subject: Regions formed by connecting points on the circumference

Dear Doctor Math,

This is an extension of a problem we have been dealing with in class.  
I would like your help in understanding it, if possible. 

Let n be the number of points on the circumference of a circle, and 
let r be the maximum number of non-overlapping regions formed by 
connecting each of the n points, with a line segment, to every other 
point on the circle, including its two neighboring points. Let n = 1, 
2, 3, 4, 5, 6 .... Find a pattern relating n and r. Find an explicit 
or a recursive equation for r, and prove this formula.

I would like any help you can offer with this question. It seemed 
straightforward, but then it just changes; and finding the formula, 
and being able to prove it, are not so simple. I would appreciate any 
help you can give me. Thank you.
                                   
Lover of Math,
Jay Shah

Date: 05/20/98 at 15:07:02
From: Doctor Rob
Subject: Re: Regions formed by connecting points on the circumference

The formula is r(n) = C(n,4) + C(n,2) + 1. The values for 
n = 1, 2, 3, ... are:

   1, 2, 4, 8, 16, 31, 57, 99, 163, 256, ....

Here, C(n,k) = n!/[k!*(n - k)!]. This expression for r can also be 
expressed in the form:

   r(n) = (n^4 - 6*n^3 + 23*n^2 - 18*n + 24)/24

You can prove this by starting with n points, all connected, and 
adding one more point. Connecting it to its two neighbors adds 1 
region each. Connecting it to their neighbors adds 1*(n - 2) + 1 
regions each. Connecting it to their neighbors adds 2*(n - 3) + 1 
regions each. Connecting it to their neighbors adds 3*(n - 4) + 1 
each. Each line from the new point to an old vertex crosses 
k*(n - k - 1) lines connecting the k vertices on one side of the line 
to the remaining n - k - 1 vertices on the other side, and crossing m 
lines results in m + 1 new regions. That means the number of regions 
added is:

                   n-1
 r(n + 1) - r(n) = Sum [k*(n - k - 1) + 1]
                   k=0

                   n-1
                 = Sum [1 + n*k - k*(k + 1)]
                   k=0

                 = n + n*n*(n - 1)/2 - n*(n - 1)*(n + 1)/3

                 = (n^3 - 3*n^2 + 8*n)/6

                 = n*(n + 1)*(n + 2)/6 - 2*n*(n + 1)/2 + 2*n

Thus:

                 n
  r(n) = r(0) + Sum [r(k) - r(k - 1)]
                k=1

               n
        = 1 + Sum [(k - 1)*k*(k + 1)/6 - 2*(k - 1)*k/2 + 2*(k - 1)]
              k=1

        = 1 + (n - 1)*n*(n + 1)*(n + 2)/24 
          - 2*(n - 1)*n*(n + 1)/6 + 2*(n - 1)*n/2
  
        = 1 + n*(n - 1)*(n^2 + 3*n + 2 - 8*n - 8 + 24)/24

        = 1 + n*(n - 1)*(n^2 - 5*n + 18)/24

        = 1 + n*(n - 1)/2 + n*(n - 1)*(n - 2)*(n - 3)/24

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

-Doctor Rob, The Math Forum
Check out our web site! http://mathforum.org/dr.math/