Math Is Fun Forum

clooneyisagenius

Member

Registered: 2007-03-25

Posts: 56

Combinatorial Proof

I need a cominatorial proof of:
((n choose 2) choose 2) = 3(n choose 4) + 3(n choose 3)

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)

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

blingbunni

Member

Registered: 2008-02-26

Posts: 5

Re: Combinatorial Proof

I need a cominatorial proof of:
((n choose 2) choose 2) = 3(n choose 4) + 3(n choose 3)

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)

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

weel i need help from u. how do yo do common denominators, also explain urs better:o

---

ps. rockon

                -blingbunni:)

clooneyisagenius

Member

Registered: 2007-03-25

Posts: 56

Re: Combinatorial Proof

It's cool. 

Common denominator: see the follow: http://en.wikipedia.org/wiki/Common_denominator

And stop posting on other peoples. I've seen you put this sort of thing on a few different posts.

mathsyperson

Moderator

Registered: 2005-06-22

Posts: 4,900

Re: Combinatorial Proof

I need a cominatorial proof of:
((n choose 2) choose 2) = 3(n choose 4) + 3(n choose 3)

The only way I can think of to do that would be to write both sides in their factorial forms and do stuff until they become equal. I've tried it and it's possible to do it that way, but quite messy and I'm not sure what a combinatorial proof is so it might not be allowed anyway.

---

Why did the vector cross the road?
It wanted to be normal.

Ricky

Moderator

Registered: 2005-12-04

Posts: 3,791

Re: Combinatorial Proof

That is an algebraic proof.  Combinatorial proofs are used to get algebraic theorems through non-algebraic ways.

Given your two subsets of 2, you can either have 3 or 4 people in them (why not 2?).  This is C(n, 3) + C(n, 4).  However, there is something else going on.  Where does that * 3 come from?

---

"In the real world, this would be a problem.  But in mathematics, we can just define a place where this problem doesn't exist.  So we'll go ahead and do that now..."