Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: Combinatorial proof?

  1. Feb 24, 2008 #1
    1. The problem statement, all variables and given/known data

    ((n choose 2) choose 2) = 3(n choose 4) + 3(n choose 3)

    Need a combinatorial proof...

    2. Relevant equations
    for example, (n choose k) means from a total of n people we choose a committe of size k.
    (though this may not be relevant equation)

    3. The attempt at a solution
    I'm thinking for the left hand side that out of a total of n people we find the all the possible committees of size 2. Then of all these committees we pick two of the duos picked? No idea how to do the right hand side - or make the left side equal
  2. jcsd
  3. Feb 25, 2008 #2


    User Avatar
    Science Advisor

    The crucial point, then, is "what does
    [tex]\left(\begin{array}{c}\left(\begin{array}{c} n \\ 2 \end{array}\right) \\ 2 \end{array}\right)[/tex]
    mean in terms of combinatorics"?
    It would be, apparently, the number of different ways to choose 2 people from a group of [tex]\left(\begin{array}{c} n \\ 2\end{array}\right)[/tex]
    Now, how would you interpret that [tex]\left(\begin{array}{c} n \\ 2\end{array}\right)[/tex] "combinatorically"?
  4. Feb 25, 2008 #3
    Well the left hand side [tex]\binom{\binom{n}{2}}{2}[/tex] counts the number of unordered pairs of unordered pairs. What exactly can one look like? Either it involves 4 distinct elements, or it involves 3 distinct elements, like {{a,b}, {a,c}}, but it can never involve 2 or 1 distinct elements (why)? I hope this is enough to push you in the right direction.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook