The recurrence relation of the interior of a circle

[BMAD]

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.

[k-man]

  Reveal hidden contents

The total number of intersections for all chords formed by n points on the circle is n(n-1)(n-2)(n-3)/24.

  Reveal hidden contents

Let's say we have k points and all the chords connecting them. Each point has k-1 chords connecting it to other points. Let's add one more point and count how many new intersections it will produce.

The new point X will be between some other 2 points - let's call them A and B. A and B are the immediate neighbors of X, so the chords AX and BX will not produce any intersections.

Now let's consider the next pair of points C and D that are immediate neighbors of A and B respectively. Chord CX will intersect all chords connecting A with all other points except C and X, so it will produce k-2 intersections. The same is true for the chord DX - it will intersect all chords connecting B with all other points except D and X.

Going to the next pair of points (E and F) and applying the same logic we find that chords EX and FX produce 2*(k-3) intersections each. Then 3*(k-4), etc...

So, the total number of new intersections added by the point X is the sum 1*(k-2)+2*(k-3)+3*(k-4)+...+(k-3)*2+(k-2)*1 or sum[ m*(k-m-1) ] for m in (1..k-2). This sum evaluates to (k-2)*(k-1)*k/6.

So, to determine the total number of intersection produced chords connecting n points on the circle we need to find the sum of these sums with k ranging from 1 to n-1. This sum equates to the answer above.

[witzar]

  Reveal hidden contents

For (n+3) points on the circle, number of intersections for chords coming from one of the points equals:

C(n) = 1*n + 2*(n-1) + 3*(n-2) + ... + n*1
Let's call
S(n) = C(n) - C(n-1)
It is easy to see that
S(n) = 1 + 2 + ... + n = n(n+1)/2
So
C(n) = S(n) + S(n-1) + ... + S(1)
It is a known result that
C(n) = n*(n+1)(n+2)/6
Total number of intersections for (n+3) points equals
(n+3)*C(n)/4 = n*(n+1)(n+2)(n+3)/24