posted by nancy on .
find a formula that gives the maximum number of enclosed regions formed by n lines
n-2 works for triangles inside of a polygon.
Refer to question #4 at the end of this Stanford test:
A formula that seems to work for n = 3 (one area), n = 4 (three areas) and n= 5 (five areas) is :
A = 1 + 2(n-3) = 2n -5,
for n an integer greater than or equal to 3.
n is the number of lines, and A is the number of enclosed areas.
the number of regions developed within a triangle resulting from the creation of "n" lines being drawn from each vertex to "n" points on the opposite sides derives from N = 3n^2 + 3n + 1.
n lines will divide a circle up into Rn = 1 + n(n + 1)/2 = [n^2 + n + 2]/2 regions.
Regions in n-gons
The derivation of the number of regions created within different shaped figures comes in several forms. Consider the following variations.
1--Irregular convex polygons divided up by connecting each vertex with every other vertex by straight lines.
2--Circles divided up by connecting n randomly located points on the circumference with each other by straight lines. This is essentially joining all n points in sequence and creating all the diagonals between the points.
3--Circles divided up by a series of lines that cross one another within the circle without connecting the points on the circle and without any three lines passing through the same point. This is the same as the #2 variation with the exception that the points on the circumference are not joined to one another.
It becomes immediately obvious that the connection of n randomly located points by straight lines within the circle is simply the polygonal n-gon inscribed in a circle. Therefore, the number of regions created within the circle is really the number of regions defined within the n-gon plus the n arc/chord regions created when inscribing the n-gon within the circle. Lets tackle the polygonal n-gons, first.
What can we learn from the first set of n-gons. One thing that must be recognized is that all our n-gons are irregular where all the sides and internal angles are not equal to one another. The triangle is the first n-gon, ((n+2) = 3 sides) to be considered. Clearly, it has but one region within its three sides. Our second n-gon is obviously the quadrilateral, or 4-gon. Joining the opposite vertices clearly divides it up into 4 regions. Thirdly, comes the 5-gon which is clearly divided into 11 regions. Our patience is now tested a bit when we attempt to determine the number of regions within the 6-gon, 7-gon, 8-gon, and so on. After much enumeration and erasures, the 6-gon has 25 regions, the 7-gon, 50 regions, and the 8-gon, 91 regions. What can we learn from this information that would enable us to define the number of regions within any n-gon? Lets summarize the data derive so far.
n.....................1......2......3......4.......5......6 the nth n-gon in the sequence.
Sides..............3......4......5......6.......7......8 (n+2) sides on the n-gon
An expression can be derived enabling the definition the nth term (or the (n+2)-gon) of any finite difference series. The expression is a function of the number of successive differences required to reach the constant difference. If the first differences are constant, the expression is of the first order, i.e., N = an + b. If the second differences are constant, the expression is of the second order, i.e., N(n) = an^2 + bn + c. Similarly, constant third differences derive from N = an^3 + bn^2 + cn + d. Using the data points (n1, N1), (n2,N2), (n3,N3), etc., from our data, we substitute them into N = an^4 + bn^3 + cn^2 + dn + e. as follows:
(n1,N1) = (1,1) produces a(1^4) + b(1^3) + c(1^2) + d(1) + e = 1 or a + b + c + d + e = 1
(n2,N2) = (2,4) produces a(2^4) + b(2^3) + c(2^2) + d(2) + e = 4 or 16a + 8b + 4c + 2d + e = 4
(n3,N3) = (3,11) produces a(3^4) + b(3^3) + c(3^2) + d(3) + e = 11 or 81a + 27b + 9c + 3d + e = 11
(n4,N4) = (4,25) produces a(4^4) + b(4^3) + c(4^2) + d(4) + e = 25 or 256a + 64b + 16c + 4d +e = 25
(n5,N5) = (5,50) produces a(5^4) + b(5^3) + c(5^2) + d(5) + e = 50 or 625a + 125b + 25c + 5d + e = 50
Subtracting successive pairs ultimately leads to the solution of N(n) = [-n^4 + 22n^3 - 59n^2 + 110n - 48]/24 where N(n) = the nth term in the series with (n+2) sides to the n-gon.
As we observed earlier, the number of regions created by inscribing these n-gons within a circle, is simply n more than the number of regions within the n-gon itself. This translates into a slightly modified expression for the number of regions created by joining all the vertices of an inscribed n-gon within a circle to N(n) = [-n^4 + 22n^3 - 59n^2 + 134n - 48]/24 where N(n) = the nth term in the series with (n+2) sides to the inscribed n-gon.
It might be of some interest (without derivation) that the number of regions within an n-gon is also defined by
N = n/4 + (n-1)/2
which is the number of combinations on n things taken 4 at a time plus the number of combinations of (n-1) things taken 2 at a time.