# Counting regions outside a convex hull

This problem is from Bay Area Math Olympiad 2016: The corners of a fixed convex (but not necessarily regular) $n$-gon are labeled with distinct letters. If an observer stands at a point in the plane of the polygon, but outside the polygon, they see the letters in some order from left to right, and they spell a word (that is, a string of letters; it does not need to be a word in any language). Determine, as a formula in terms of $n$, the maximum number of distinct $n$-letter words which may be read in this manner from a single $n$-gon. Do not count words in which some letter is missing because it is directly behind another letter from the viewer’s position.

The vertices determine $\binom{n}{2}$ lines and there is a one to one correspondence between the number of words and the number of regions outside the convex hull formed by the vertices. The final answer is tantalizingly simple: $2\binom{n}{2} + 2\binom{n}{4}$. While the official solution is available, is there a combinatorial argument to get the answer in a direct way?

• For those that want to look at the official solution, it can be found at this link (problem 5, the last problem). – Misha Lavrov Sep 10 '18 at 20:38

$2\binom n4$ counts the number of bounded regions outside the convex hull (which I'll call $H$). $2\binom n2$ counts the number of unbounded regions.
To count bounded regions: for each bounded region $\mathcal R$, let $f(\mathcal R)$ be the point of $\mathcal R$ furthest from $H$. Because the distance to $H$ is a convex function, $f(\mathcal R)$ must be a vertex of $\mathcal R$; because $\mathcal R$ contains points at distance $>0$ from $H$, this vertex is not one of the ones that lie on $H$. So $f(\mathcal R)$ is the intersection of two lines $AB \cap CD$, where $A,B,C,D$ are distinct vertices of $H$.
There are $\binom n4$ ways to choose $A,B,C,D$; each gives three intersection points $AB \cap CD$, $AC \cap BD$, and $AD \cap BC$, but one of these is inside $H$. So there are $2\binom n4$ values of $f(\mathcal R)$. Each one is achieved exactly once: given an intersection $AB \cap CD$, three of the regions have a point further from $H$ by moving along $AB$ or along $CD$.
To count unbounded regions: If we zoom out really far, all $\binom n2$ lines approximately intersect at a single point, and zooming out does not change the unbounded regions. It is easy to see that $N$ lines meeting at a point create $2N$ unbounded regions.