Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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|improve this question
    
see also math.stackexchange.com/questions/430310 –  sdcvvc Jul 4 '13 at 23:01

1 Answer 1

up vote 9 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|improve this answer
1  
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

 
discard

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.