The Math Forum

Ask Dr. Math - Questions and Answers from our Archives
Associated Topics || Dr. Math Home || Search Dr. Math

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 
Associated Topics:
High School Permutations and Combinations

Search the Dr. Math Library:

Find items containing (put spaces between keywords):
Click only once for faster results:

[ Choose "whole words" when searching for a word like age.]

all keywords, in any order at least one, that exact phrase
parts of words whole words

Submit your own question to Dr. Math

[Privacy Policy] [Terms of Use]

Math Forum Home || Math Library || Quick Reference || Math Forum Search

Ask Dr. MathTM
© 1994- The Math Forum at NCTM. All rights reserved.