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

### How Many Regions are Generated?

Date: 05/29/2003 at 17:21:17
From: Sam
Subject: Discrete Math

Draw a circle and pick n points on it. Now join every point to every
other point and suppose that the points have been picked so that no
three chords go through one point (i.e. every intersection is the
intersection of exactly two chords). How many domains are generated?
The points on the circle can't be at even intervals.

Date: 05/29/2003 at 17:38:56
From: Doctor Anthony
Subject: Re: Discrete Math

With no lines the circle has just one region.  Now consider any
collection of lines. If you draw a new line across the circle that
does not cross any existing lines, then the effect is to increase the
number of regions by one. In addition, every time a new line crosses
an existing line inside the circle the number of regions is increased
by one again.

So in any such arrangement

number of regions = 1 + number of lines + number of interior
intersections

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

Note that the number of lines is the number of ways two points can be
chosen from n points = C(n,2). Also, the number of interior
intersections is the number of quadrilaterals ( = C(n,4)) that can be
formed from n points, since each quadrilateral produces just one
intersection where the diagonals of the quadrilateral intersect.

- Doctor Anthony, The Math Forum
http://mathforum.org/dr.math/
Associated Topics:
High School Permutations and Combinations

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