Combinatorial Geometric proof of $\binom{\binom{n}{2}}{3} > \binom{\binom{n}{3}}{2}$

The set we are counting

This is a geometric proof, so I'm avoiding e.g. set counting or any algebra. I started this proof before a comment appeared as well which was related to it, so it's quite natural to assume that this approach would have been taken by a few others.

Consider $n$ points in the plane ($\mathbb R^2$)such that they are the vertices of a regular $n$-gon, for $n \geq 4$. (For $n=3$ the RHS is $0$, so we are done anyway).

The quantity $\binom{n}{2}$ is the number of pairs of distinct vertices, and hence the number of distinct line segments that can be drawn between these points. $\binom{\binom{n}{2}}{3}$ counts the number of triples of distinct line segments between these points.

Similarly, $\binom{n}3$ counts the number of distinct triples of points, and hence the number of triangles. Then $\binom{\binom{n}3}{2}$ counts the number of pairs of distinct triangles. (Those that would differ by at least one edge).

So we have combinatorial interpretations for the quantities under consideration.

A couple of key observations

The important observation is this : whether it's three lines or two triangles, they will intersect at most six different vertices. Of course, a smaller number is possible.

This tells us that we should focus our attention on the situation when at most six vertices are involved. As it turns out, we will be able to carry our map to the more general situation.

We will also need a different method of counting. For example, consider four distinct points $\{a,b,c,d\}$, no three collinear. In how many ways can we get a distinct pair of triangles such that every point is a vertex of at least one of these triangles? Indeed, there are obviously $6$ ways, since there are four triangles and you have to choose from two of them.

But there's a different way of understanding these six triangles, and the idea is of "cyclicity". Each configuration of triangles yields itself to a symmetry, which is useful because our map is going to make use of this symmetry.

Definitions and notation

Let's create some general notation. Let the vertices of the given $n$-gon be $v_1,v_2,...,v_n$.

A line is denoted by $l_S$ where $S$ is a subset of size $2$ of $\{1,2,...,n\}$. For example if the two vertices are $v_4,v_5$ then $S = \{4,5\}$ and we write the corresponding line as $t_{4,5}$. Note that $t_{4,5} = t_{5,4}$ for example, the order doesn't matter. When we use variables, rather than write $l_{a,b}$ we write $l_{ab}$ for simplicity.

A triangle is denoted by $t_{S}$, where $S$ is a subset of size $3$ of $\{1,2,...,n\}$. For example if the three vertices are $v_1,v_3,v_7$ then $S = \{1,3,7\}$ then we write the corresponding triangle as $t_{1,3,7}$. Note that $t_{1,3,7} = t_{7,1,3}$ and so on, the order doesn't matter. When we use variables, rather than write $t_{a,b,c}$ we write $t_{abc}$ for simplicity.

We define a cyclicity map on a totally ordered set as follows : Suppose we have a set $S' = \{u_1,u_2,...,u_n\}$ with the total order on it specified by $u_i<u_j$ if $i<j$. then the cyclicity map $C : S' \to S'$ is given by $C(u_i) = u_{i+1}$ for $1 \leq i < n$, and $C(u_n) = u_1$. In other words, the cyclicity map cycles between the vertices.

Now, let $S_4,S_5,S_6$ be the set of all distinct pairs of triangles coming from line segments in the $n$-gon, where the vertices of the triangles form sets of size $4,5,6$ respectively. Let $L_4,L_5,L_6$ be the set of distinct triples of line segments in the $n$-gon, where the vertices intersected by at least one of these lines form sets of size $4,5,6$ respectively.

We will use the cyclic map to provide descriptions of $S_4,S_5,S_6$ and provide maps from $S_i$ to $L_i$ which are injective. This , along with the fact that every possible pair of distinct triangles will somehow come from $S_4,S_5$ or $S_6$ (not difficult to see actually) will complete the injection and the inequality.

Note that if we have a triangle $t_{abc}$ and $abc$ are part of some ordered set and hence admits a cyclicity map $C$, then we get a new triangle by cyclicity that we call $C(t_{abc})$ which is defined by $t_{C(a)C(b)C(c)}$. Basically, it just cyclic shifts the triangle.

Similarly, given a set of triangles $B = \{t_1,...,t_n\}$ we define $C(B) = \{C(t_1),...,C(t_n)\}$. This just takes every triangle in the set to its cyclic shift.

The same as done for triangles above can be done for lines analogously, so $C(l_{ab})$ where $l_{ab}$ is a line, and $C(L)$ where $L$ is a set of lines are well defined now.

Finally, $\sqcup$ denotes the disjoint union of two sets, so $A \sqcup B = C$ means that $A \cup B = C$ and $A \cap B = \emptyset$.

The case $S_4$

So let's start with $S_4$. We define the set $\{a,b,c,d\}$ with order $a<b<c<d$. The following are two configurations of distinct pairs of triangles with vertices $\{a,b,c,d\}$, corresponding to $B_1 = \{t_{abc},t_{abd}\}$ and $B_2 =\{t_{abc},t_{adc}\}$ respectively.

Now, it is an easy enough check that $$ S_4 = \{C^k(B_1) : k=0,1,2,3\} \sqcup \{C^l(B_2) : k = 0,1\} $$

Define $\phi_4 : S_4 \to L_4$ as follows. We first ensure that $\phi_4(C(K)) = C(\phi_4(K))$ for all $K \in S_4$, so we only need to define $\phi(B_1),\phi(B_2)$. We define $\phi(B_1) = \{l_{ab},l_{ac},l_{bd}\}$. We define $\phi(B_2) = \{ab,ac,cd\}$.

One can easily check that $\phi_4$ is a well-defined injective map. Indeed, each image of $\phi_4$ lies in $L_4$ because all vertices come at least once, and the injectivity is clear once you draw the images out. Hence, $\phi_4$ is now established.

The case $S_5$

For $S_5$, we create the set $\{a,b,c,d,e\}$ with $a<b<c<d<e$. Now, what we will do is find out how we enumerate the cases. First of all, note that $5$ is a prime number, so we expect three generating pairs of triangles, after which cyclicity will take us all the way. With that , we assume that $abc$ is one of the triangles. Then, note that $de$ must be connected, because the second triangle has to include both of them. Now, $de$ can connect to each of $a$,$b$, which gives us two configurations (connecting to $c$ gives us a cyclic one to that connecting to $a$). The last one can be found by taking $t_{abd}$ instead. So let $B_1 = \{t_{abc},t_{ade}\}$, $B_2 = \{t_{abc},t_{bde}\}$,$B_3 = \{t_{abd},t_{ace}\}$. We draw these like so :

We can check that $$ S_4 = \{C^k(B_i) : k = 0,1,2,3,4, i = 0,1,2\} $$

Amazing drawings , isn't it!

Now, let's define $\phi_5 :S_5 \to L_5$ as follows. Once again we define it so that $\phi_5(C(K)) = C(\phi_5(K))$. Now define $\phi(B_1) = \{l_{ab},l_{cd},l_{ae}\}$, $\phi(B_3) = \{l_{bc},l_{cd},l_{de}\}$ and $\phi(B_2) = \{l_{ab},l_{ac},l_{de}\}$.

It's an elementary exercise to check that $\phi_5$ is an injective well-defined map. Hence, $S_5$ is complete.

The case $S_6$

For $S_6$ consider the set $\{a,b,c,d,e,f\}$ with $a<b<c<d<e<f$. Now we are going to talk about the pairs of triangles that must use all six points.

But I don't even need a diagram for this. You see , let $t_{xyz}$ be a triangle. Any other triangle has to use the other three vertices, so it's obvious that it has to be composed of the other vertices. For example, if $t_{abc}$ is a triangle, then $t_{def}$ has to be the other triangle, because $d,e,f$ have to be used by the triangle, but every triangle is determined by three vertices!

Hence, $S_6$ is truly in bijection with three-element subsets of $\{a,b,c,d,e,f\}$. We define the map $\phi_6:S_6 \to L_6$ as follows. Let $s \in S, s = \{t_{xyz},t_{x'y'z'}\}$ where $\{x,y,z,x',y',z'\} = \{a,b,c,d,e,f\}$ and $x<y<z,x'<y'<z'$. Then, $\phi_6(s) = \{l_{xy},l_{zx'},l_{y'z'}\}$.

This map is well defined and injective!

Hence, the case $S_6$ is also complete.

Solving our question

Consider two disjoint triangles in the $n$-gon from $v_1,...,v_n$. Suppose that the set of vertices that intersect at least one of the triangles is given by $\{v_{i_1},...,v_{i_k}\}$ where $i_1<...<i_k$ and $k=4,5,6$.

Now , this triangle clearly belongs in $S_k$ and is carried by $\phi_k$ to an element of $L_k$.

It is clear that each $\phi_j$ is injective. Furthermore, obviously the $L_j$ are disjoint. It follows that the map $\phi : S_4 \sqcup S_5 \sqcup S_6 \to L_4 \sqcup L_5 \sqcup L_6$ given by $\phi(s) = \phi_k(s)$ where $s \in S_k, k=4,5,6$, is an injective map.

Since $S_4 \sqcup S_5 \sqcup S_6$ is in fact the set of all pairs of distinct triangles in the $n$-gon, we conclude that the mapping $\phi$ provides an injective map from this set to the set of all triples of distinct lines made from line segments with vertices of the $n$-gon.

Furthermore, because a set of three lines forming a triangle is not part of the image of $\phi$ but belongs in the appropriate co-domain, the above map is non-surjective , and hence the inequality is strict.

Thus, our task is complete.

But there is more!

Consider the quantities $\binom{\binom{n}{2}}{3}$ and $\binom{\binom{n}3}{2}$. We can expand the binomials and write them as polynomials in $n$ of degree $6$.

When we do this, we realize that there is a nice basis of polynomials of degree less than or equal to $6$, that we can combinatorially exploit.

Indeed, this is the following basis of seven polynomials : $\binom{n}{k}, k=0,1,...,6$.

Every polynomial of degree at most $6$ is (uniquely) a linear combination of these polynomials. This can be proven by proving that the above polynomials are linearly independent.

You can prove that they are linearly independent using the following logic : if $\sum_{k=0}^6 c_k\binom{n}{k} = 0$, then evaluate the LHS at the points $n=0,1,2,...,6$ and see the result!

Finding the coefficients in the basis is a simple matter of substitution of $n=0,1,...,6$ and yields the following identities :

$$ \binom{\binom{n}{2}}{3} = \binom{n}{3} + 16\binom{n}{4} + 30 \binom{n}{5} + 455 \binom{n}{6} \\ \binom{\binom{n}{3}}{2} = 6\binom{n}{4} + 15\binom{n}{5} + 10 \binom{n}{6} $$

from where the inequality is actually immediately obvious! So we've obtained an algebraic proof.

The idea of the binomial coefficient expansion is the following. We've already seen that whether it's a set of three lines or two triangles, it is quite easy to see that at most six points from the collection will be involved in the creation of these sets, as the vertices for the lines/triangles involved.

It turns out that the coefficients in the binomial expansion reflect the number of possible constructions that would use only and exactly those many points as in the lower index of the binomial coefficient. How magniloquently superelegant is that!?

Want an example? Let's take the case when the lower index is $3$.

Let's take three particular points and fix them. How many sets of three distinct lines can be drawn which involve all these points? Answer : one. When the three lines form a triangle. And is the coefficient of $\binom{n}{3}$ in $\binom{\binom{n}{2}}{3}$?

How many pairs of distinct triangles can be drawn which involve all these points? Answer : None. And is the coefficient of $\binom{n}{3}$ in $\binom{\binom{n}{3}}{2}$?

Fix four points. How many ways can you choose three distinct lines so that each of the four points is part of at least one of the lines? Indeed, the answer is $16$. Use cyclicity to make your job easier.

Similarly, from four points, using each one at least once you will get exactly six distinct pairs of triangles. To see this , find $|S_4|$ from its description!

For the examples above, note the coefficients in the respective expansions.

Therefore, we realize that the binomial expansion logic allows us to experiment combinatorially with the number of set ups, using a fixed number of points.

I would expect that this should generalize to some other numbers. But, well, I don't know. I also hope there are no errors, but I've double checked so I'm doubly confident that things should work out.

EDIT : It works! You can read it at ease.

I've asked a more general question to the above here, everyone is welcome to see it and attempt to copy what I've tried above for the situation there.