Drexel dragonThe Math ForumDonate to the Math Forum

Ask Dr. Math - Questions and Answers from our Archives

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:


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:


parts of words whole words

Submit your own question to Dr. Math

[Privacy Policy] [Terms of Use]


Ask Dr. MathTM
© 1994-2015 The Math Forum