From: Fred Galvin Subject: Re: Regions of a circle Date: Sat, 20 Jan 2001 17:32:27 -0600 Newsgroups: sci.math Summary: Counting the regions formed by chords across a circle On Sat, 20 Jan 2001, charles silver wrote: > I'm teaching a baby math course in which the authors of the > text present an example to illustrate that a series of numbers > may seem to exemplify one pattern, but really exemplify another. > The example they use concerns the relationship of the number of > points on the circumference of a circle to the number of regions > cut out by chords joining those points. I realize this way of > putting it is probably unclear, so I'll use a couple of examples > to show what I mean. > > SUPPOSE YOU HAVE A CIRCLE: > ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ > 1) Put a single point on its circumference. Since there's > only a single point, no straight line can be drawn to another > point. So, the circle has but one region--the entire circle. > > 2) Now, instead of having one point on the circumference, put > two of them on it. Now, you can draw a straight line (a chord) > from one point to the other. So, two regions of the circle have > been cut out. > > 3) This time, draw three points on the circle. Then, draw > all possible chords using these 3 points. There are now 4 > regions. > > > The authors of the textbook present the following chart, and ask > the students to guess how many regions there would be for 6 > points: > > No. of pts No. of regions > ^^^^^^^^^ ^^^^^^^^^^^^^^ > 1..........................1 > 2..........................2 > 3..........................4 > 4..........................8 > 5.........................16 > 6.......................... ? > > > Now, it looks as though the number of regions doubles each > time. So, one might think that the number of regions for 6 > points is 32. Not so, say the authors. The next number is 31. > Then, they provide what seems to me to be a very complicated > formula relating the number of regions, R to the number of point, > n: > > ( n^4 -6n^3 +23n^2 -18n +24 ) /24 > > So, finally here's my problem. I have been wondering where this > complicated formula comes from. Why does one have to go to the > 4th power for this? Can anyone explain how to arrive at this > formula in some simple way, just using straightforward principles > about points, regions, and so forth? If so, I would be very > appreciative. Now, of course, the students couldn't care less > about this (2/3 of them openly admitted they hate math and are > taking this course only because they're forced to), but the > problem is bothering me. I've fiddled around with it a bit and > noticed a few trivial things, like it's more complicated than it > seems. But, I haven't been able to get very far. Any insights > at all would be appreciated, even if you can't solve the entire > problem. First off, the problem is not well stated, because, for n > 5, the number of regions depends on how the points are positioned on the circle. E.g., if the 6 points are vertices of a regular hexagon, then you get 30 regions, not 31. Here, one region is lost because of the 3 chords meeting in the center; perturb a point slightly to avoid the concurrency and the 31st region shows up. In fact, the problem of determining the number of regions formed by the chords of a regular n-gon has a very complicated solution: see Bjorn Poonen and Michael Rubinstein, The number of intersection points made by the diagonals of a regular polygon, SIAM J. Discrete Math. 11 (1998), 135-156; the first few values (starting with n = 3) are 4, 8, 16, 30, 57, 88, 163. But that's not the problem you're asking about; you want the number of regions when the n points are in "general position", so that no three chords meet at one point inside the circle. That is much easier! The formula in your book is correct, but it can be expressed more simply in terms of binomial coefficients: R(n) = C(n,4)+C(n,2)+1 where C(n,2) = n(n-1)/2 and C(n,4) = n(n-1)(n-2)(n-3)/24. Moreover, the derivation is simple enough that even your rotten students would be able to understand it, it they gave a damn. Let R(n) be the number of regions formed by putting n points in general position on a circle and drawing all the chords; also, let L(n) be the number of chords, and let P(n) be the number of points where two chords cross inside the circle. Clearly, L(n) = C(n,2), and P(n) = C(n,4). Now let's consider R(n)-R(n-1), the number of new regions we get when we add the nth point; and break it down further by imagining the new chords as drawn one at a time. The number of new regions created by drawing a single chord is equal to the number of existing regions that it crosses, which is one more than the number of interior points where it crosses existing chords. So, the number of new regions resulting from the nth point is equal to the number of new chords plus the number of new crossings; that is, R(n)-R(n-1) = L(n)-L(n-1)+P(n)-P(n-1). (We could simplify L(n)-L(n-1) to n-1 but that wouldn't help.) Summing the telescoping series, R(n)-R(0) = L(n)-L(0)+P(n)-P(0). Seeing as R(0) = 1 and L(0) = P(0) = 0, we have R(n) = P(n)+L(n)+1, Q.E.D. Alternatively, I suppose you could work out a derivation using Euler's E+2 = V+F (if your students happen to know that), but I don't think that would be any easier. -- It takes steel balls to play pinball. ============================================================================== From: Fred Galvin Subject: Re: Regions of a circle Date: Sat, 20 Jan 2001 22:36:43 -0600 Newsgroups: sci.math On Sat, 20 Jan 2001, Fred Galvin wrote: > ... you want the number of regions when the n points are in > "general position", so that no three chords meet at one point > inside the circle. ... The formula in your book is correct, but it > can be expressed more simply in terms of binomial coefficients: > R(n) = C(n,4)+C(n,2)+1 where C(n,2) = n(n-1)/2 and C(n,4) = > n(n-1)(n-2)(n-3)/24. Moreover, the derivation is simple enough It's even clearer if you generalize it. Instead of taking n points on the circumference and drawing chords from each to each, just draw chords at random. If you draw any (finite) number of chords in a circle, and if no three of them meet at one point inside the circle, then R = 1+L+P, where R is the number of regions, L is the number of chords, and P is the number of crossings. (The "chords" don't even have to be straight line segments, curves are OK.) PROOF: Draw the chords one by one. At the ith step you add 1 chord, some number x_i of crossings, and 1+x_i regions. If you stop after k steps, you have L = k, P = x_1+...+x_k, and R = 1+(1+x_1)+...+(1+x_k) = 1+L+P. Now, if you take n points in "general position" on the circumference and draw chords from each to each, then L = C(n,2) and P = C(n,4), and so R = 1+C(n,2)+C(n,4) which is the 4th degree polynomial in the book. -- It takes steel balls to play pinball.