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
http://mathforum.org/dr.math/
```
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
Math Forum Home || Math Library || Quick Reference || Math Forum Search