Associated Topics || Dr. Math Home || Search Dr. Math

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

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

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/
```
Associated Topics:
High School Conic Sections/Circles
High School Geometry
High School Sequences, Series

Search the Dr. Math Library:

 Find items containing (put spaces between keywords):   Click only once for faster results: [ Choose "whole words" when searching for a word like age.] all keywords, in any order at least one, that exact phrase parts of words whole words

Submit your own question to Dr. Math
Math Forum Home || Math Library || Quick Reference || Math Forum Search