Navigation 
 Home 
 Search 
 Site map 

 Contact Graeme 
 Home 
 Email 
 Twitter

 Skip Navigation LinksMath Help > Sequences and Series > Sequences > A000127

 . . . . . . this entry should be formatted a little better.

What is the maximal number of regions that can be obtained by joining n points around a circle by straight lines? The first few values of this sequence are 1,2,4,8,16,... Here's a hint: the next value is not 32.

Each intersection is associated with two chords, each of which are associated with two points - and since no two points are concurrent, all four are distinct. Therefore, the number of internal intersections (those within the circle, not on the circumference) is equal to the number of distinct 4-element subsets of the points around the circle. This is C(n,4).

Where there are no points (or but one), there is but one region: the entirety of the circle. Each chord adds one new region, and every time a chord intersects internally with another chord, yet another region is formed.

So, the number of regions is 1 + number of chords + number of internal intersections, which is

1 + C(n,2) + C(n,4)

The series, OEIS: http://www.research.att.com/~njas/sequences/A000127 , up to n=20 is as follows:

1, 2, 4, 8, 16, 31, 57, 99, 163, 256, 386, 562, 794, 1093, 1471, 1941, 2517, 3214, 4048, 5036, 6196, 7547, 9109, 10903, 12951, 15276, 17902, 20854, 24158, 27841, 31931, 36457, 41449, 46938, 52956, 59536, 66712, 74519, 82993, 92171, 102091.

Whenever you can take successive differences and get to a constant kth difference, you can find a degree k polynomial by first finding the n^k coefficient, and subtracting it from the original numbers to get constant (k-1)th differences, and then repeating the procedure. In this case, you can be certain this is a 4th degree polynomial because C(n,2)=n(n-1)/2, and C(n,4)=n(n-1)(n-2)(n-3)/24

In this case, you can be certain this is a 4th degree polynomial because C(n,2)=n(n-1)/2, and C(n,4)=n(n-1)(n-2)(n-3)/24.

1 + C(n,2) + C(n,4)
1 + n(n-1)/2 + n(n-1)(n-2)(n-3)/24
(n^4-6n^3+23n^2-18n+24)/24

(But if you didn't know how to turn combinations with constant second parameter into polynomials, but you knew the kth differences are constant, then you could follow this procedure: Whenever you can take successive differences and get to a constant kth difference, you can find a degree k polynomial by first finding the n^k coefficient, and subtracting it from the original numbers to get constant (k-1)th differences, and then repeating the procedure).


 

Internet references

OEIS: A000127

Related pages in this website

See also Recurrence Relation

 


The webmaster and author of this Math Help site is Graeme McRae.