14
$\begingroup$

For $n \geq 4$, show that $\binom{\binom{n}{2}}{2} = 3 \binom{n}{3}+ 3 \binom{n}{4}$.

LHS: So we have a set of $\binom{n}{2}$ elements, and we are choosing a $2$ element subset.

RHS: We are choosing a $3$ element subset and a $4$ element subset (each from a set of $n$ elements). But we multiply by $3$ by the multiplication principle for some reason.

$\endgroup$
1

1 Answer 1

14
$\begingroup$

LHS: The $\binom{n}{2}$ is the number of pairs you can form of n distinct elements, so the LHS counts the number of ways to choose two distinct pairs.

RHS: Notice that you can choose two pairs that have a common element (but only one). If the two pairs are disjoint, then you need to choose four elements and then ask how you pair them. If the pairs have a common element, then you need to choose only three elements and then choose which is the common element.

$\endgroup$
0

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .