Circle Chords

Date: Fri, 4 Nov 1994 17:56:30 -0500
From: Keroppi Chan
Subject: Please help!

Hi Dr. Math,

I have a math problem.  Would you help me?

Place n distinct points on the circumference of a circle and draw all 
possible chords through pairs of these points. Assume that no three of 
these chords pass through the same point. Find and solve the recurrence 
relation for the number of interior intersection points formed inside the 
circle.

Thank you very much!

Cheers,
Keroppi

Date: Tue, 8 Nov 1994 13:29:56 -0500
From: Lynn Stallings
Subject: Some data on circle chord problem

(Keroppi, I posted your question publicly and here's the first response.
-- Steve)

PROBLEM:
>(1) Place n distinct points on the circumference of a circle and draw all
>possible chords through pairs of these points. Assume that no three of
>these chords pass through the same point. Find and solve the recurrence
>relation for the number of interior intersection points formed inside the
>circle.

I've restricted myself to n evenly spaced points on the circumference of
the circle and come up with the following:

number of points        intersection points     interior regions

.....2...........................0.....................2
.....3...........................0.....................4
.....4...........................1.....................8
.....5...........................6....................16
.....6..........................13*...................30
.....7..........................35....................56
.....8..........................49**..................88

 * includes one w/ 3 chords passing thru 1 intersection point
** includes one w/ 4 chords passing thru 1 intersection point and
    one with w/ 8 chords passing thru 1 intersection point

Date: Tue, 8 Nov 1994 22:40:06 -0500
From: John Conway
Subject: Re: Some data on circle chord problem

The number of interior intersection points is n-choose-4, since
the two lines that define any such point have a total of 4 ends,
and any set of 4 points are the ends of just one pair of
intersecting lines.

This doesn't seem to agree with your figures, so one of us
is probably doing something wrong, but I send this note
on anyway.

I THOUGHT that the number of regions the circle is cut into
was the sum of the first 4 or 5 binomial coefficients from the
"n" row, but this also seems to be wrong.  I'll think again
on this!

John Conway

Date: Tue, 8 Nov 1994 22:40:12 -0500
From: Tom Kilkelly
Subject: Re: Recurrence relations and circle chords

points chords interior pts
  n     C(n)    I(n)
  1     0       0
  2     1       0
  3     3       0
  4     6       1
  5     10      5
  6     15      15
  7     21      35
  8     28      70

Recursively: C[n] = C[n-1] + n -1  and  I[n] = I[n-1] + (n^3 - 6n^2 + 11n - 6)/6

Explicitly:  C[n] = n(n-1)/2    and     I[n] = (n^4 - 6n^3 + 11n^2 - 6n)/24

Tom Kilkelly
St. Thomas Academy

Date: Wed, 9 Nov 1994 21:33:18 -0500
From: Stephen B Maurer

Let me give a hint .  

Start with a standard technique: ask a simpler question.  How many 
*chords* are generated by n points on a circle?

Answer: n choose 2, because each pair of points generates one chord.
So there is a one-to-one correspondence between pairs of points on
the circle and chords.  Now we ask: what sorts of sets of points on the
circle generate interior intersection points?  Well, each intersection
point is generated by two chords.  How many points on the circle 
generate those two chords?

If you finish this approach, you will get a formula for the number of
interior intersection points *without* getting a recurrence first. You 
can use the same methods to get a recurrence *afterward*, but this 
seems like unnecessary work.

Stephen B Maurer
Professor of Mathematics
Swarthmore College

Date: Sat, 12 Nov 1994 07:28:27 -0500
From: North Buncombe High Schl
Subject: Re: Recurrence relations and circle chords

This is a quartic nth term expression. Try using the ti-82 and its
statistics capabilities...it gives you a nice quartic expression using
quartic regression (curve fitting). Also, notice the odd/evenness of
the terms of the sequence.

From: Tom Kilkelly
Subject: Re: Recurrence relations and circle chords

Dear Doctor Ken,

It was great fun communicating about the number of interior 
points formed by chords connecting n points on a circle. So far I 
have five completely different formulas that all work!

A[n] =3D A[n-1] + (n^3 - 6n^2 + 11n - 6)/6

A[n] =3D (n^4 - 6n^3 + 11n^2 - 6n)/24

A[n] =3D 2A[n-1] - A[n-2] + =85i where i =3D 1..(n-3)

A[n] =3D (n/4)* C(n-1,n-4)

A[n] =3D n*A[n-1]/(n-4)

As you've probably gathered I really enjoy recursion-type problems, 
so if any good recursion problems come your way, I'd greatly 
appreciate receiving them.

Ciao! 

Tom Kilkelly
St. Thomas Academy