Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question
see also – sdcvvc Jul 4 '13 at 23:01
up vote 11 down vote accepted

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.

share|cite|improve this answer
Distinct elements and distinct pairs. (You know this, but it should be clarified.) – Qiaochu Yuan Dec 25 '10 at 19:36
Fixed it, thanks – Prometheus Dec 25 '10 at 19:59

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.