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/
Search the Dr. Math Library:
Ask Dr. MathTM
© 1994- The Math Forum at NCTM. All rights reserved.