Prove combination arguments $c(c(n,2),2) = 3c(n,3)+3c(n,4)$

Question

Provide combination (counting) arguments to prove the following statement. I would prefer solutions without algebraic manipulation.

$$\binom { \binom n2}2= 3\binom n3 + 3 \binom n4$$

Are there any such solutions? Thanks is advance!

Answer 1

Suppose we have a set $A = \{1,2,3,...,n\}$ with $|A| = n$. Then $\binom{n}{2}$ represents how many subsets of size $2$ that $A$ has and let set of these subsets is $B = \big\{\{1,2\},\{1,3\},...,\{n-1,n\}\big\}$. Now notice that left hand side is $$\binom{\binom{n}{2}}{2}$$ So this means we are choosing $2$ elements from $B$. Now there are two cases because in these subsets, we may have one repeated element (we cannot have two) or we may not have any repeated elements.

• If we have a repeated element (choosing $\{1,2\}$ and $\{1,3\}$ is an example where $1$ is the repeated element), then we can choose $3$ elements from $A$ with $\binom{n}{3}$ and choose the repeated element from $3$ elements with $3$ ways. So there are $3\binom{n}{3}$ ways of doing this.

• If we don't have repeated element (choosing $\{1,2\}$ and $\{3,4\}$ is an example), then we can choose $4$ elements from $A$ with $\binom{n}{4}$ and partition them as $2+2$ by $3$ ways again. So there are $3\binom{n}{4}$ ways of doing this.

So we have $$\binom{\binom{n}{2}}{2} = 3\binom{n}{3}+3\binom{n}{4}$$

Answer 2

$\binom{n}{2}$ is the number of ways for choosing a $2$-subset from $\{1,2,\ldots,n\}$ and $\binom{\binom{n}{2}}{2}$ is the number of ways for choosing an unordered couple of $2$-subsets from $\{1,2,\ldots,n\}$. Such a couple either covers $3$ or $4$ elements of $\{1,2,\ldots,n\}$. Going in the opposite direction, for any $3$-subset $\{a,b,c\}$ of $\{1,2,\ldots,n\}$ we may build the couples $\{\{a,b\},\{a,c\}\}, \{\{a,c\},\{b,c\}\}, \{\{a,b\},\{b,c\}\}$ and for any $4$-subset $\{a,b,c,d\}$ of $\{1,2,\ldots,n\}$ we may build the couples $\{\{a,b\},\{c,d\}\},\{\{a,c\},\{b,d\}\},\{\{a,d\},\{b,c\}\}$. This bijection proves $$ \binom{\binom{n}{2}}{2}=3\binom{n}{3}+3\binom{n}{4}$$ as wanted.