Partitioning a Circle
N points are selected on a circle and connected by chords in all possible ways. The points are in a general position, in the sense that no three of those chords are concurrent, i.e., no three of them pass through the same point. Into how many region the chords partition the circle?
Let's denote the number of regions in a partition with N points R(N). As a quick inspection of a few small point sets shows
for a polyhedron with F faces, E edges and V vertices. Considering a polygon as a projection of a polyhedron with just one face hidden, the Euler's formula for polygons becomes:
This is the one we shall be referring to below. The formula remains valid if edges allowed to be curved so that it applies to general planar graphs.
I'll use the standard notation
For N points, there are exactly C(N, 4) intersections of chords inside the circle, since each set of 4 points gives rise to just one such intersection. Then the total number of vertices in the figure
which simplifies to C(N, 4) + C(N, 2) + 1.
- R. K. Guy, A Strong Law of Small Numbers, in The Lighter Side of Mathematics, R.K.Guy and R.E.Woodrow, eds, MAA, 1994
Copyright © 1996-2018 Alexander Bogomolny