Drexel dragonThe Math ForumDonate to the Math Forum

Ask Dr. Math - Questions and Answers from our Archives
_____________________________________________
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

[Privacy Policy] [Terms of Use]

_____________________________________
Math Forum Home || Math Library || Quick Reference || Math Forum Search
_____________________________________

Ask Dr. MathTM
© 1994-2013 The Math Forum
http://mathforum.org/dr.math/