1, 2, 4, 8, 16, and Then Not 32

Put distinct points on the rim of a circle, draw a straight segment between every pair, and count the pieces inside the circle. These segments are called chords. One point draws no chord and leaves one region; two points draw one chord and leave two.

With no three chords crossing at the same interior point, three, four and five rim points give 4, 8 and 16 regions. That makes doubling a reasonable guess, but six points give 31, not 32. The early counts alone do not determine the counting rule.

The arrangement matters as well as the number of points. Six evenly spaced points give 30 regions because three chords pass through the centre together. Moving one point slightly separates that shared crossing and creates the 31st region.

The term general position here means that no three chords meet at one interior point. The laboratory compares that setting with the evenly spaced arrangement, so the conditions behind each count remain visible.

Draw the chords one at a time and watch what each one does. The plate above is this, and the laboratory is this.

A chord that crosses nothing splits one region into two, so it adds one region. A chord that crosses one existing chord passes through two regions and splits each of them, so it adds two. In general a chord that meets what is already drawn at $k$ separate points passes through $k+1$ regions and splits each one, so it adds $k+1$ regions.

Add all of that up. You start with one region. Every chord adds one. Every crossing adds one more. So

regions = 1 + (number of chords) + (number of crossings).

That is not an approximation and there is nothing left to estimate. The only question is how many chords and how many crossings there are.

The chords are easy: one for each pair of points, so $\left(\genfrac{}{}{0ex}{}{n}{2}\right)$ of them.

The crossings are the pretty part. Pick any four of the points. Those four have three ways of being paired off into two chords, and exactly one of those three pairings makes the two chords cross inside the circle: join the points that are opposite each other round the rim, not adjacent. So every four points give exactly one crossing. And every crossing comes from exactly one set of four points, since the two chords through it have four distinct ends. Four points, one crossing, no double counting: there are $\left(\genfrac{}{}{0ex}{}{n}{4}\right)$ crossings.

Now the doubling. Why did it work five times?

Because $\left(\genfrac{}{}{0ex}{}{n}{4}\right)+\left(\genfrac{}{}{0ex}{}{n}{2}\right)+1$ is the sum of the first five entries of row $n-1$ of Pascal's triangle, and $2^{n-1}$ is the sum of the whole row. A row with five entries or fewer has nothing left over, and the two agree: that is $n\le 5$. Row 5 is 1, 5, 10, 10, 5, 1, which has six entries, and the first five of them come to 31 while all six come to 32. The missing entry is the last 1, and that 1 is the whole of the surprise.

Two sentences carry this page, and the second is the one worth arguing about.

A sequence is not its first few terms. 1, 2, 4, 8, 16 is the start of the doubling sequence and also the start of at least one other sequence, and nothing inside those five numbers can separate them.

The usual moral stops there, and it is a good moral, but it is only half of what is going on. The other half is that this is not a case where the truth is unknowable or the pattern merely suspicious. The real count is provable, in a few lines, from a fact about drawings that anybody can check on the drawing in front of them. The doubling was never a rival theory. It was a guess that had never been asked to justify itself, sitting beside a count that can be.

That is worth separating from what the rest of this site is usually about. When Gilbreath's conjecture holds for millions of rows, the millions of rows are all there is; nobody can prove it and nobody can break it. Here the evidence and the proof point at the same answer, and the evidence was pointing at the wrong one until the sixth term.

A pattern that breaks is not the same as a pattern nobody can settle. This one breaks, and we know exactly why, at exactly which term, by exactly how much.

And then the second trap, which is the better one. The formula needs the points to be in general position, and the drawing you would make by hand is not. Six evenly spaced points look like the most natural way to draw six points on a circle, and they are the one arrangement that gives the wrong answer. Having just been told not to trust a pattern you can see, you are handed a picture whose symmetry is doing something the formula never claimed to cover.

Let $P$ be a set of $n$ distinct points on a circle, and draw the chord between every pair. Say $P$ is in general position if no three of those chords pass through a common point strictly inside the circle. Let $R(P)$ be the number of connected regions the chords cut the open disc into.

1. If $P$ is in general position then $$R(P)=\left(\genfrac{}{}{0ex}{}{n}{4}\right)+\left(\genfrac{}{}{0ex}{}{n}{2}\right)+1.$$ Proved, in layer 5.
2. $R(P)=\left(\genfrac{}{}{0ex}{}{n}{4}\right)+\left(\genfrac{}{}{0ex}{}{n}{2}\right)+1$ for $n=1,\dots ,8$ gives $1,2,4,8,16,31,57,99$. Proved, as an instance of 1, and computed again two other ways as a check.
3. $\left(\genfrac{}{}{0ex}{}{n}{4}\right)+\left(\genfrac{}{}{0ex}{}{n}{2}\right)+1=2^{n-1}$ exactly when $n\le 5$, and is strictly smaller for every $n\ge 6$. Proved, in layer 5.
4. For $P$ the six vertices of a regular hexagon, $R(P)=30$. Proved, in layer 5, by exhibiting the concurrency and recounting.
5. For the regular $n$-gon with $n=6,8,10,12$, $R(P)=30,88,230,456$. Exhaustively checked over exactly those four arrangements, by two computations that could each be wrong and are wrong in different ways. Not proved here.

Statement 1 is what the page is for; 4 is what stops 1 from being read as more than it says. The condition in 1 cannot be dropped: for a general $P$ the equality becomes $\le$, and the deficit is what the concurrences cost.

Counting the chords and the crossings. There is one chord per pair of points, so there are $\left(\genfrac{}{}{0ex}{}{n}{2}\right)$ chords. For the crossings, define a map from crossings to 4-element subsets of $P$: a crossing lies on two chords, which between them have four distinct endpoints, since two chords sharing an endpoint meet on the circle and not inside it. That map is injective on a general-position figure, because two distinct crossings cannot lie on the same pair of chords. It is surjective, because any four points $a,b,c,d$ in cyclic order have the chords $ac$ and $bd$ crossing inside. So there are exactly $\left(\genfrac{}{}{0ex}{}{n}{4}\right)$ crossings. ∎

The count, by Euler. Treat the figure as a plane graph: the vertices are the $n$ points on the rim together with the $\left(\genfrac{}{}{0ex}{}{n}{4}\right)$ crossings inside; the edges are the $n$ arcs of the circle between neighbouring points, together with the pieces the chords are cut into. A chord carrying $c$ crossings is cut into $c+1$ pieces, and every crossing lies on exactly two chords in general position, so the chords contribute

edges in total. The graph is connected and drawn in the plane without crossings (the crossings are vertices now), so Euler's relation $V-E+F=2$ applies. With

we get

One of those faces is the unbounded region outside the circle. Removing it leaves $\left(\genfrac{}{}{0ex}{}{n}{4}\right)+\left(\genfrac{}{}{0ex}{}{n}{2}\right)+1$ regions inside the disc. ∎

Where the doubling comes from, and where it goes. The identity that matters is one about row $n-1$ of Pascal's triangle:

which is checked directly from Pascal's rule. Meanwhile $2^{n-1}={\sum }_{k\ge 0}\left(\genfrac{}{}{0ex}{}{n-1}{k}\right)$ is the sum of the entire row. The two therefore differ by ${\sum }_{k\ge 5}\left(\genfrac{}{}{0ex}{}{n-1}{k}\right)$, which is zero exactly when $n-1\le 4$, and strictly positive for every $n\ge 6$. At $n=6$ the missing term is $\left(\genfrac{}{}{0ex}{}{5}{5}\right)=1$, so 32 becomes 31. ∎

The regular hexagon. Label the vertices $0,\dots ,5$ round the rim. The chords $0\text{-}3$, $1\text{-}4$ and $2\text{-}5$ join opposite vertices, so each is a diameter and all three pass through the centre. Every other triple of chords meets in three distinct points, which is checked by inspection of the fifteen chords. So the figure has $\left(\genfrac{}{}{0ex}{}{6}{4}\right)-3+1=13$ crossings rather than 15, and the centre lies on three chords rather than two, so the chord pieces number $15+(12\times 2+1\times 3)=42$ rather than $15+2\times 15=45$. Then

and removing the outside leaves 30 regions. Moving one vertex off its place destroys the diameter through it, the three chords no longer share a point, and the general-position count of 31 applies again. ∎

What is not proved here. Statement 5 above. The counts 88, 230 and 456 for eight, ten and twelve equally spaced points are computations, not arguments: the laboratory finds the concurrences in the drawing using a numerical tolerance, and a separate raster of the picture is flooded and its patches counted. Both could be wrong, in opposite directions, and their agreeing is evidence rather than proof. The general theory of which diagonals of a regular polygon are concurrent is a substantial piece of work and it is cited rather than reproduced.

What this laboratory computes. Up to fourteen points, which is ninety-one chords and 1,001 crossings. The formula is evaluated in exact whole-number arithmetic and could be taken as far as you like; what limits the page is the drawing, not the arithmetic. Crossings are found in ordinary double-precision floating point, and two of them are treated as the same point when they fall within $10^{-9}$ of one another on a disc of radius 1. That tolerance is the one number on this page that could quietly change an answer, so it is stated here, exported from the kernel, and tested from both sides: an exact concurrency is found to about $10^{-16}$, and no two genuinely distinct crossings in any figure the page draws come within a thousand tolerances of each other.

The raster count, and what it is worth. The third count on this page inks the chords onto a grid and counts the connected patches of paper. It knows nothing about binomial coefficients, nothing about Euler, and nothing about concurrency, which is exactly why it is worth running. It is also the weakest of the three: a region narrower than a cell or two is inked over and lost, and patches of fewer than six cells are discarded as artefacts of the ink having a width. Its only defence is that raising the resolution does not change its answer, and that is a defence rather than a proof.

Where the mathematics is still moving. Not here. The general-position count is settled and has been for a long time. The live question is the one this page only touches: what happens when the points are symmetric. Counting the regions of a regular $n$-gon means knowing exactly which sets of three diagonals are concurrent, and that turns out to be a genuinely hard problem in its own right, solved with a long case analysis rather than a formula you could put on a card. The four counts this page prints for equal spacing are small instances of it, computed rather than derived.

Read this next to Pascal Modulo m. The whole business of the doubling holding five times and then failing is a fact about a row of Pascal's triangle being long enough to have something left over. Seeing the triangle itself makes the coincidence stop looking like one.