Understanding the combinatorial argument for $\binom{\binom{n}{2}}{2} = 3 \binom{n+1}{4}$.

Question

I was playing around the expression for $\binom{\binom{n}{2}}{2}$, and I discovered that it equals $3\binom{n+1}{4}$. I couldn't come up with any combinatorial argument, but found various ones on this site. I'm trying to understand a particular one.

In this comment, the user r9m gives the following combinatorial argument:

A direct combinatorial interpretation of the factor $3$ can be obtained by counting number of parallelograms in a equilateral triangle with side length $(n−1)$ and tiled with $(n−1)^2$ equilateral triangles with side length $1$(like this). Of course one way of counting is $\binom{\binom{n}{2}}{2}$. The other way is divide the parallelograms into $3$ cases (each parallelogram must have its diagonal parallel to one of the $3$ sides of the equilateral triangle) which is $3 \times \binom{n+1}{4}$.

I'm having trouble understanding both parts of this argument. In particular, I cannot think of the things to choose from for both binomial coefficients.

For the first half, what are the $\binom{n}{2}$ things, from which we need to choose $2$? I suspect that since a parallelogram is uniquely defined in this grid by its longer diagonal, they are the endpoints of the diagonal of a parallelogram. But there are some restrictions for choosing the endpoints of a diagonal: e.g. the line joining them cannot be parallel to any of the sides of the equilateral triangle.

For the second half, I understand the factor of $3$, and counting parallelograms with their shorter diagonal parallel of a particular side. However, I cannot see a "thing" that exists $n+1$ times in this figure. I suspect $4$ is the number of vertices of a parallelogram, but what is $n+1$?

Answer 1

Nice combinatoric demonstrations of the identity have already been described in the previous answers. I would only propose a possible explanation for what it seems one of the principal issues of the OP, i.e. the r9m's comment regarding the ${n\choose 2}$ "things" to be considered and from which we need to choose $2$.

Let us consider our equilateral triangle with side length $n−1$ tiled with $(n-1)^2$ equal and equilateral triangles with unit side. Let us orient our large triangle so that it has one vertex directed upward (just as in the figure provided in the link of the OP). It is not difficult to show that, among all small triangles, the number of those which have a vertex directed upward is $n(n-1)/2={n\choose 2}$. In our specific case of a triangle with side $4$, colouring the resulting $10$ up-directed triangles we obtain the following figure:

Now we can note that each parallelogram within the large triangle can be unambiguously identified by choosing a pair of these up-directed small yellow triangles. To clarify this, let us call $A $, $B $, $C $ the upper, lower left, and lower right vertex of the large triangle, respectively. Now let us consider the $15$ parallelograms whose two acute vertices are oriented left-down and right-up (i.e., those whose minor diagonal is parallel to $AC $). Each of them is uniquely identified by two small yellow triangles: the first is that whose lower left vertex is also the lower left vertex of the parallelogram, the second is that whose upper vertex is also the upper right vertex of the parallelogram.

We can now repeat these considerations after rotating the large triangle clockwise by $120^o $, so that its upper vertex is now $B $ and its base is $CA $. In this way, we can identify other $15$ pairs of small yellow triangles (note that these pairs are different from the previous ones) that unambiguously identify the $15$ parallelograms with minor diagonal parallel to $BA $.

Lastly, repeating these considerations after rotating again the large triangle clockwise by further $120^o $, so that its upper vertex is now $C $ and its base is $AB$, we can identify other $15$ pairs of small yellow triangles (again different from all previous ones) that uniquely identify the $15$ parallelograms with minor diagonal parallel to $CB $.

The final result is that all $45$ possible parallelograms correspond to a different pair of small up-directed triangles, with a one-to-one correspondence. Generalizing, this means that the number of parallelograms is given by all possible choices of two elements among a total of ${n\choose 2}$ up-directed small triangles, which means $ {{n\choose 2}\choose 2}$.

Answer 2

This provides one half of the answer: For the $3 \cdot \binom{n+1}{4}$ interpretation: consider the intersection points of the sides of the parallelogram with the side of the triangle that is not parallel to any side of the parallelogram. This yields $4$ or $3$ (if the parallelogram has a vertex on this side) different points that together determine the parallelogram. Consequently, for each side of the triangle there are $\binom{n}{4} + \binom{n}{3} = \binom{n+1}{4}$ parallelograms with no side parallel to this side.

Answer 3

I'm unable to comprehend r9m's comment concerning this question. But here is a combinatorial argument supporting the identity $$3{n+1\choose4}={{n\choose 2}\choose 2}\qquad(n\geq2)\ .\tag{1}$$ There are ${n+1\choose 4}$ ways to select a $4$-subset of $\{0,1,2,\ldots, n\}$, and the selected elements can then be paired off in $3$ ways each. Let $A_n$ be the resulting set of pairs of pairs. This set has $3{n+1\choose4}$ elements. On the other hand, let $B_n$ denote the set of edge-pairs of $K_n$, the complete graph on $\{1,2,\ldots,n\}$. The set $B_n$ has ${{n\choose 2}\choose 2}$ elements. We shall produce a bijection $\phi:\>A_n\to B_n$.

Let $p:=\bigl\{\{a,b\},\{c,d\}\bigr\}\in A_n$. If $0\notin\{a,b,c,d\}$ then $p$ can be viewed as a pair of disjoint edges of $K_n$, hence we define $\phi(p):=p$. If, e.g., $a=0$ then $\phi(p):=\bigl\{\{b,c\},\{b,d\}\bigr\}$ is a pair of different edges of $K_n$ sharing the common point $b$. The map $\phi:\>A_n\to B_n$ defined in this way is reversible: Any unordered pair $p:=\bigl\{\{a,b\},\{c,d\}\bigr\}$ of edges of $K_n$ either shares no vertex, in which case $p$ is a pairing of four elements of $\{1,2,\ldots, n\}$, or one has, e.g. $c=a$, in which case $p':=\bigl\{\{0,a\},\{b,d\}\bigr\}$ is a pairing of a $4$-subset of $\{0,1,2,\ldots, n\}$ containing $0$, and $\phi(p')=p$.