In my last video, I posed the following question: if you take 𝑛 points on a circle then connect every pair of them with a line, how many sections do these lines cut the circle into?
What was strange is that when 𝑛 is less than six and when 𝑛 is 10 for some reason, the answer is always a power of two. But for all other values of 𝑛, the answer seems completely unrelated to powers of two.
What I love about this problem is that it brings together many disparate concepts: counting functions, graphs, one of Euler’s most famous equations, and Pascal’s triangle.
You might be wondering if changing the placement of points changes the number of sections. It actually can! For instance, watch how the small region in the middle disappears if we adjust things so the three lines go through the same point.
But if we add the restriction, then no three lines can go through the same point. The number of sections depends only on the number of points, not their placement, as you’re about to see.
I think it’s fair to call this a hard problem. And in solving hard problems, it’s a good idea to ask simpler questions about the same setup. In this case, I have two questions for you: 1) How many lines are there? and 2) at how many points do these lines intersect within the circle?
For the first question, every line corresponds uniquely with a pair of points. And likewise, every pair of points gives us a unique line.
Luckily, counting the number of pairs in a set is common enough in math that we have specific notation for it: “𝑛 choose two,” which we evaluate as 𝑛 times 𝑛 minus one divided by two.
To see where this formula comes from, notice that you have 𝑛 options for the first element of the pair, which we multiply by the 𝑛 minus one remaining options for the second element. But this would double count each pair, so we divide by two.
For instance, when 𝑛 equals seven, seven choose two is seven times six over two or 21. So there are 21 pairs of points and hence 21 lines.
We’d save a hundred points; counting lines directly would be a nightmare. But we can compute it as 100 choose two, which is 100 times 99 divided by two, or 4950.
The number of intersection points is a bit more subtle. While every intersection point corresponds with a unique pair of lines, there are many pairs of lines that don’t intersect within the circle. So we can’t just count the pairs of lines. What we can do though is associate each intersection point with a set of four points on the circle.
Since this association goes the other way around, in that every quadruplet of points gives a unique intersection point. Just look at that! Isn’t that elegant? This means the number of intersection points is the same as the number of quadruplets of our 𝑛 starting points.
The function 𝑛 choose four counts quadruplets in a set of size 𝑛. And we’ll evaluate it by taking 𝑛 times 𝑛 minus one times 𝑛 minus two times 𝑛 minus three, all divided by one times two times three times four.
The derivation of this formula is similar to that of 𝑛 choose two. You multiply 𝑛, the number of options you have for each successive entry. Then divide by the extent to which you’ve overcounted.
For instance, with 𝑛 equals four, four choose four is one. And indeed, there’s just one intersection point. Six choose four is 15. So when 𝑛 equals six, there are 15 intersection points. And if 𝑛 were 100, even though the prospect of counting intersection points is horrifying, we can nevertheless deduce that there will be 3,921,225 of them.
Now, how does this help us count sections in the circle? You might ask. Well, it will, once we consider graphs and Euler’s formula. No, no, not function graphs and not that 𝑒 to the 𝜋𝑖 stuff.
The word graph can also refer to a set of points, referred to as “vertices,” along with a set of lines connecting some of these points which we call “edges.” Notice if we count the number of vertices in this graph, then subtract the numbers of edges, then add the number of regions that this graph cuts space into, along with that outer region, we get two. If we do the same thing with this other graph, well, we get two again.
This isn’t a coincidence. You could do this with any graph. And as long as your edges don’t intersect each other, the answer is always two. If edges could intersect, then you could just change the number of regions without changing number of vertices and edges. So of course, it would be nonsense.
This relation is known as “Euler’s characteristic formula.” And it’s easy to see where the name comes from since “Euler’s” is German for beautiful.
If you’re curious, the reason we write 𝐹 for the number of regions is because the formula traditionally refers to the number of vertices, edges, and faces of 3D polyhedra. In another video, I’ll explain why this is true. But here, let’s just use it to solve our circle problem.
Our setup is already a graph with 𝑛 vertices and 𝑛 choose two edges, one between each pair of points. But we cannot apply Euler’s characteristic formula directly, since our edges intersect many times, 𝑛 choose four times to be exact.
However, if we consider each intersection point to be a vertex, meaning our original lines must be chopped up at these points, and if we also include the segments of the circle connecting our 𝑛 outer points as new edges, we’d have a graph perfectly suited for Euler’s formula.
In particular, the number of regions in this picture is the number of edges in our new graph minus the number of vertices plus two.
Since our new graph retains the 𝑛 original vertices and adds on another 𝑛 choose four for intersection points, we’ll replace the minus 𝑉 term with minus 𝑛 minus 𝑛 choose four.
To find the number of edges, note that the intersection points can be seen as adding two edges each, since each one takes two existing lines and then cuts them into four smaller pieces. For example, three lines intersecting at two points would be cut into three plus two times two equals seven smaller pieces. Four lines intersecting at three points would be cut into four plus two times three equals ten smaller pieces.
And in our circle diagram, our 𝑛 choose two lines intersecting at 𝑛 choose four points are cut into 𝑛 choose two plus two times 𝑛 choose four smaller pieces plus another 𝑛 for the circle segments we’re now considering to be edges.
Going back to our formula, we can replace 𝐸 with 𝑛 choose two plus two times 𝑛 choose four plus 𝑛. Combining like terms, we see that our graph cuts the 2D plane into two plus 𝑛 choose two plus 𝑛 choose four pieces. Since we’re concerned with counting the regions inside the circle, we can disregard that outer region and write our final answer as one plus 𝑛 choose two plus 𝑛 choose four.
Great! We found the answer. But why on earth does this formula relate to powers of two for 𝑛 less than six, then again when 𝑛 is 10? It’s not just a coincidence; it has to do with Pascal’s triangle. Pascal’s triangle is constructed like this: each term is the sum of the two terms above it. If you add up each row, you get a successive power of two. To convince yourself of this, notice that each term is added into the following row twice, so the sum of each row should be twice the sum of the row before it.
The function 𝑛 choose 𝑘 is closely related to this triangle, in that the 𝑘th entry of the 𝑛th row, where counting starts at zero, is always 𝑛 choose 𝑘. For instance, to find five choose three in the triangle, count down to the zero, one, two, three, four, fifth row; then go in zero, one, two, three. And indeed, five choose three equals 10. This means that the answer to our circle problem for 𝑛 point is the sum of the zeroth, second, and fourth entries of the 𝑛th row of Pascal’s triangle.
For instance, if 𝑛 equals five, we can see that we just have to add one, 10, and five. Since each term is the sum of the two above it, this is the same as adding the entire fourth row, which we know is a power of two. Likewise, for smaller values of 𝑛, the answer is gonna be the sum of the 𝑛 minus first row and hence a power of two.
However, when 𝑛 equals six and we will relate the terms to the fifth row, notice that we’re not adding the entire row since we missed that last term. So we only get 31. When 𝑛 equals 10, we’re summing precisely half of the ninth row. So the answer is half of two to the ninth, which is two to the eighth.
So to recap, first turn our diagram into a graph suitable for Euler’s characteristic formula by adding all of the intersection points as vertices and cutting up all the edges. Next, count the number of lines and intersection points by relating them to pairs and quadruplets of our starting points. And, finally use Euler’s formula to deduce the number of sections and then relate this to powers of two using Pascal’s triangle.