Why doesn't ${n \choose 4} = { {n \choose 2} \choose 2}$?

160 Views Asked by At

I've been thinking about the classic problem where you have to determine the maximum number of regions created when you place $n$ points around the circumference of a circle and connect every pair of points with a line segment. There is a classic argument using Euler's formula which shows that the maximum number of regions is $$ 1 + {n \choose 2} + {n \choose 4} $$

Along the way, it is argued that there well be $n\choose 2$ line segments. This is clear enough. It is also argued that there are $n \choose 4$ points of intersection between the segments, as any intersection is uniquely specified by the $2$ pairs of endpoints of the segments intersecting at that point.

It seems like we could just as well have uniquely specified any intersection point by the $2$ segments that intersect at that point. In other words, any choice of $2$ of the $n \choose 2$ line segments should also uniquely specify a point of intersection. Thus, it seems that ${{n \choose 2} \choose {2}}$ should also give the number of points of intersection between the segments.

But, of course $$ {n \choose 4} \neq {{n \choose 2}\choose 2} $$ so there must be a flaw in my reasoning. Can someone help me to identify it?

1

There are 1 best solutions below

1
On BEST ANSWER

If you look at the pairwise intersections of the $\binom n2$ lines of the form $A_j A_k$ (where $A_1,\ldots, A_n$ are the chosen points on the circle) then many of them are already just the $A_i$, since some pairs of lines look like $A_1A_2$ and $A_1A_3$. I reckon there are $n\binom{n-1}2$ pairs like this. But even when we have pairs of lines $A_i A_j$ and $A_k A_l$ with all the points distinct, then some of those pairs will intersect outside the circle. Each quartet of points will determine three pairs of lines, and only one of those pairs will intersect within the circle. Therefore the real identity is $$\binom{\binom n2}2=n\binom{n-1}2+3\binom n4.$$