Combinatorial Proof: Identity

Date: 02/10/2003 at 07:26:27
From: Catherine
Subject: Combinatorial Proof

I don't understand how it is meant to work.  I have read textbooks and 
it still makes no sense to me. 

Here is an example:

  C(2n,4) = 2C(n,4)+2C(n,3)C(n,1)+(C(n,2))^2  for all n in N; n >= 4

Date: 02/10/2003 at 10:38:14
From: Doctor Anthony
Subject: Re: Combinatorial Proof

We are using a combinatorial argument to prove the identity above.

The argument is clearer if we let n have a particular value, but the 
reasoning is perfectly general.

Suppose n = 5, so 2n = 10 and we require to find the number of ways 
that 4 things can be chosen from 10 different things. For convenience 
let the 10 things be the letters a,b,c,....i,j.

Then we divide the 10 things into two groups of 5, that is, letters 
a,b,c,d,e and f,g,h,i,j

    a,b,c,d,e | f,g,h,i,j      Number of selections
    ----------|-------------------------------------
     b,c,d,e  |              =  C(5,4)
              |
              | f,h,i,j      =  C(5,4)
              |
      b,c,e   | h            =  C(5,3) x C(5,1)
              |
          c   | f,h,j        =  C(5,1) x C(5,3)
              |
        a,d   | h,j          =  C(5,2) x C(5,2)

This covers all possible ways of selecting 4 things from 10 different 
things.  So

  C(10,4) = 2.C(5,4) + 2.C(5,3).C(5,1) + [C(5,2)]^2

and the identity is proved.

- Doctor Anthony, The Math Forum
  http://mathforum.org/dr.math/