1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Combinatorics proof

  1. Sep 28, 2009 #1
    1. The problem statement, all variables and given/known data
    Give two proofs (algebraic and combinatorial) of the following formula:
    ((nchoose2) choose 2)=3(n choose 3) +3(n choose 4)


    2. Relevant equations



    3. The attempt at a solution

    Alright, I have part of the algebraic one but I get stuck, also I don't know how to approach the combinatorial proof... so any suggestions would be great...


    Algebraic proof:

    3(n choose3) +3(n choose 4) is equal to:
    3((nchoose3) +(nchoose4)) and by the additive property that equals:
    3((n+1 choose 4)

    which is equivalent to:
    (n+1)(n)(n-1)(n-2)/8

    This is where I get stuck.... i know that (n)(n-1)/2 equals n choose 2
    but then that leaves me with:
    (n choose 2)((n+1)(n-2)/4)

    any help would be great!!!
     
  2. jcsd
  3. Sep 28, 2009 #2

    Dick

    User Avatar
    Science Advisor
    Homework Helper

    (n+1)(n)(n-1)(n-2)/8 is correct for the right side. Since (n choose 2) is n(n-1)/2, the left side is (n(n-1)/2)*(n(n-1)/2-1)/2, isn't it? Just show they are equal. For the combinatorial proof the elements of ((n choose 2) choose 2) are pairs of pairs of elements in {1,2,...,n}. They fall into two groups, i) where the two pairs have an element in common and ii) where the two pairs have no elements in common.
     
  4. Sep 28, 2009 #3
    How should I go about doing that cause this is what I tried and it didn't work...

    For the two pairs without any elements in common:
    (n choose 2) because you first need to pick a pair
    ((n-2) choose 2) because then you need to choose another pair that is different from the first two.

    But multiplying that ends up being 6(nchoose4) when i need 3(nchoose4)

    Also this is what I tried for the repeats:
    (nchoose3) because I'm picking three elements, with no repeats
    (3choose1) because there are 3 ways to choose which element chosen is repeated.
    which when multiplied would equal 3(n choose 3) which is what I'm looking for, but would that be correct?
     
  5. Sep 28, 2009 #4

    Dick

    User Avatar
    Science Advisor
    Homework Helper

    Your last argument is correct. Once you have picked 3 elements you can make them into two pairs three different ways (as you say by choosing the repeated element). If you have four elements, you just need to pick the first pair. The second pair is whatever is left over. You don't have any choice about it. And yes, there are 6 ways to do that. But now think about it. If the elements are {1,2,3,4} then if I pick the first pair to be {1,2} I get the same split as if I pick the first pair to be {3,4}. The factor of 6 is twice too many.
     
  6. Sep 28, 2009 #5
    I'm not understanding what you mean by that....

    It can't just be (n choose 2) because there could be more than four elements in the set.

    Am I supposed to make it (n choose 2)* 1/2(n-2 choose 2)?
    If so, what is my argument on that?
     
  7. Sep 28, 2009 #6

    Dick

    User Avatar
    Science Advisor
    Homework Helper

    Now I'm not understanding what you are thinking. If I pick a set of 3 elements, I can make 2 pairs three different ways (which have an element in common). If I pick a set of 4 elements, I can make 2 pairs three different ways (which don't have an element in common). That's a way to think about the right side of your equation. Isn't it?
     
  8. Sep 28, 2009 #7
    yes I understand actual examples with numbers, but I don't know how to represent that using only n. I know that i would have to do (n choose 2) because I need to pick my first pair, but then I don't understand why the second part isn't (n-2 choose 2)
     
  9. Sep 28, 2009 #8

    Dick

    User Avatar
    Science Advisor
    Homework Helper

    The (n choose 3) and (n choose 4) parts take care of selecting either 3 or 4 elements. Then you only need worry about the number of ways to make two pairs out of those 3 or 4 elements. You don't need to know n for the second part.
     
  10. Sep 28, 2009 #9
    ahhhhh ok, that makes sense now. Alright, if i have four elements wouldn't I just multiply the (n choose 4) by (4 choose 2)? Because there are (4 choose 2) ways of picking 2 elements in the set without repeats but that doesn't equal three either.... that is 12...
     
  11. Sep 28, 2009 #10
    Oh wait, i'm sorry (4choose 2) is six, and if you pick one pair, that means you automatically pick the other to be a pair. I got it... thanks so much for your help!!!
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: Combinatorics proof
  1. Combinatorics Proof (Replies: 10)

Loading...