Proof of ((nchoose2) choose 2)=3(n choose 3) +3(n choose 4)

[dancergirlie]

Homework Statement

Give two proofs (algebraic and combinatorial) of the following formula:
((nchoose2) choose 2)=3(n choose 3) +3(n choose 4)

Homework Equations

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!

 

[Dick]

(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.

 

[dancergirlie]

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?

 

[Dick]

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?

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.

 

[dancergirlie]

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?

 

[Dick]

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?

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?

 

[dancergirlie]

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)

 

[Dick]

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)

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.

 

[dancergirlie]

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...

 

[dancergirlie]

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!