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/
Search the Dr. Math Library:
Ask Dr. MathTM
© 1994- The Math Forum at NCTM. All rights reserved.