In my last video, I posed the following question:

If you take n points on a circle, then connect every pair of them with a line,

how many sections to these lines cut the circle into?

What was strange is that when n is less than 6, and when n is 10 for some reason,

the answer is always a power of 2, but for all other values of n,

the answer seems completely unrelated powers of 2. What love about this problem

is that it brings together many disparate concept: counting functions,

graphs, one of Euler's famous equations, and Pascal's triangle.

You might be wondering if changing the placement of points change the number of

sections

It actually can! For instance, watch how this small region in the middle

disappears if we adjust things so that three lines go through the same point.

But if we add the restriction that no three lines can go to the same point,

the number 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 to these lines intersect within the circle?

For the first question, every line corresponds uniquely with the 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:

"n choose 2" which we evaluate as n

times (n -1) divided by 2. To see where this formula comes from,

notice that you have n options for the first element of the pair,

which we multiply by the (n -1) remaining options for the second element.

But this would double count each pair so we divide by two.

For instance, when n equals 7, 7 choose 2 is 7 times 6 over 2,

or 21, so there are 21 pairs of points, and hence

21 lines. With, say, a hundred points

counting lines directly would be a nightmare, but we can compute it

as 100 choose 2, which is 100 times 99 divided by 2,

or 4,950. The number 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 point 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 intersection points

is the same as the number quadruplets of our starting points.

The function "n choose 4" counts quadruplets in a set,

and we evaluate it by taking n times (n-1) times (n-2) times

(n-3)

all divided by 1 times 2 times 3 times 4. The derivation of this

formula is similar to that of n choose 2,

You multiply in the number of options you have for each successive entry,

Then divide by the extent to which you've over counted.

For instance, with n=4,

4 choose 4 is 1, and indeed there's just one intersection point.

6 choose 4 is 15, so when n=6 there are 15 intersection points.

And if n were 100, even though the prospect of counting intersection point

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

an Euler's formula. No, no, not function graphs, and not that e to the pi i 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 edges, then add the number

region this graph cuts space into, along with that outer region,

we get 2.

If we do the same thing with this other graph...well...we get

2 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 2. If edges could intersect,

then you could just change the number regions without changing the number of

vertices and edges,

so 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 "F" for the number 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 set up is already a

graph

with n vertices and n choose 2 edges, one between each pair of points.

But we cannot apply Euler's characteristic formula directly, since

the edges intersect many times; n choose 4 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 segment of the circle connecting these points

as new edges, we have a graph perfectly suited for Euler's formula.

In particular the number regions in this picture

is the numbers edges in the new graph minus the number vertices

plus 2

Since our new graph retains the n original vertices,

and ads on another n choose 4 for intersection points, we replace the minus

V term

with minus n minus n choose 4. To find the number

edges, note that the intersection points can be seen as

adding two edges each, since each one takes 2 existing lines

and then cuts them into four smaller pieces.

For example, three lines intersecting at 2 points

would be cut into 3+2*2 equals 7 smaller pieces.

Four lines intersecting at three points would be cut into 4+2*3

equals 10 smaller pieces. And in our circle diagram

n choose 2 lines intersecting at n choose four points

are cut into n choose 2 plus 2 times n choose 4 smaller pieces.

plus another n for the circle segments we're now considering to be

edges.

Going back to our formula, we can replace the "E"

with n choose 2, plus 2 times n choose 4, plus n.

Combining like terms we see that our graph cuts the 2d plane

into 2 plus n choose 2 plus n choose 4 smaller pieces.

Since we're concerned with counting the regions inside the circle

we can disregard that outer region and write our answer as 1

plus n choose 2 plus n choose 4. Great!

We found the answer! But why on earth does this formula relate to powers of 2

for n less than 6, then again when n is 10?

It's not just a coincidence, it has to do with Pascal 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 2.

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 n choose k is closely related to this triangle,

in that the the kth entry of the nth row, where counting start at 0,

is always n choose k. For instance, to find 5 chose 3 in the triangle,

count down to the 0, 1, 2, 3, 4, 5th row,

then go in 0, 1, 2, 3. And indeed,

5 choose 3 is 10. This means that the answer to our circle problem

for n is the sum of the 0th, 2nd,

and 4th entires in the nth row of Pascal's triangle. For instance,

If n equals 5, we can see that we just have to add 1

10 and 5. 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 2.

Likewise for smaller values of n, the answer is going to be the sum of the

(n-1)st row.

And hence a power of 2. However,

when n = 6, 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 n equals 10,

we're summing precisely half of the ninth row, so the answer is half of 2 to the 9th,

which is 2 to the 8th. So, to recap,

Turn our diagram into a graph suitable for Euler's characteristic formula

by adding all 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,

then relate this to powers of 2 using Pascal's triangle.