|
|
|
. . . . . . 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).
OEIS: A000127
See also Recurrence Relation
The webmaster and author of this Math Help site is Graeme McRae.